Programming Contest II

Time Limit : 2 sec, Memory Limit : 262144 KB

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

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

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

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

Input

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

N C
command1
command2
:
commandC

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

0 t p

または

1 m

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

Output

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

Sample Input 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 

Sample Output 1

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

Sample Input 2

5 2
1 1
1 2

Sample Output 2

1 0
2 0

Source: PC Koshien 2016 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2016-9-10
http://web-ext.u-aizu.ac.jp/pc-concours/