0746 - プログラミングコンテスト II

問題

白虎大学では毎年プログラミングコンテストを開催しています。コンテストは全てのチームの得点が 0の状態から開始し、解答状況に応じて得点が加算されていきます。このコンテストでは、得点の高い順に順位付けが行われます。チームの総数を N としたとき、チームには 1 から N の番号がそれぞれ割り当てられています。得点が同じ場合は番号がより小さい方が上位になります。

白虎大学では、コンテストを盛り上げるために観戦用のランキングシステムを開発しています。開発チームの一員であるあなたは、このシステムの一部であるプログラムの作成を任されています。

与えられた命令に従って、得点の更新と、指定された順位のチームの番号と得点を報告するプログラムを作成せよ。

入力

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

N C
command1
command2
:
commandC

１行目にチーム数 N (2 ≤ N ≤ 100000) と命令の数 C (1 ≤ C ≤ 100000)が与えられる。続く C 行に、１行ずつ命令が与えられる。各命令は以下の形式で与えられる。

0 t p

または

1 m

最初の数字が0のとき更新命令、1のとき報告命令を表す。更新命令では指定された番号 t (1 ≤ t ≤ N) のチームに、整数で与えられる得点 p (1 ≤ p ≤ 10⁹) を加算する。報告命令では指定された順位 m (1 ≤ m ≤ N) のチームの番号と得点を報告する。ただし、報告命令は少なくとも１回現れるものとする。

出力

各報告命令に対して、指定された順位のチームの番号と得点を空白区切りで１行に出力する。

入出力例

入力例 1

3 11
0 2 5
0 1 5
0 3 4
1 1
1 2
1 3
0 3 2
1 1
0 2 1
1 2
1 3 

出力例 1

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

入力例 2

5 2
1 1
1 2

出力例 2

1 0
2 0