Surf Smelt Fishing Contest II

Time Limit : 1 sec, Memory Limit : 65536 KB

ワカサギ釣り大会 2

桧原湖でワカサギ釣り大会が行われました。今回はキャッチ&リリースが推奨されているようです。

参加者番号と釣った匹数またはリリースした匹数を1つのイベントとして順番に読み込み、各イベントの直後に最も多くのワカサギを手元に獲得している参加者番号と匹数を出力するプログラムを作成してください。最も多く獲得している参加者が複数いる場合(あるいは全ての参加者が 0 匹の場合)は、その中で参加者番号が最も小さい一人を出力してください。

入力

入力は以下の形式で与えられる。

n q
a1 v1
a2 v2
: 
aq vq

n (1 ≤ n ≤ 1000000) は参加者の数、q (1 ≤ q ≤ 100000)はイベントの数を表す。ai (1 ≤ ain)   vi ( -100 ≤ vi ≤ 100) は、i 番目のイベントで参加者 aivi 匹獲得あるいはリリースしたことを示す。vi は正の値が獲得、負の値がリリースを示し、0 が与えられることはない。

出力

各イベントごとに、最も多くのワカサギを手元に獲得している参加者の参加者番号と匹数を1つの空白区切りで1行に出力する。

入力例1

3 5
1 4 
2 5 
1 3
3 6
2 7

出力例1

1 4
2 5
1 7
1 7
2 12

入力例2

3 5
1 4 
2 5 
2 -3
3 4
1 -1

出力例2

1 4
2 5
1 4
1 4
3 4

Source: PC Koshien 2005 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2005
(modified version)
http://www.pref.fukushima.jp/pc-concours/