Programming Contest II

Every year, Byakko University holds a programming contest. The contest starts with all teams having zero points, and points are added according to their answers. In this contest, the teams are ranked in order of their scores. When the total number of teams is N, each team is assigned a number from 1 to N. If the teams have the same score, the team with the smaller number will be ranked higher.

Byakko University is developing a ranking system for spectators to make the contest more exciting. As a development team member, you are asked to make a program that is part of this system.

Make a program to update the scores, and report the numbers and scores of the teams in a given rank, according to the given command.

Input

The input is given in the following format.

N C
command1
command2
:
commandC

In the first line, the number of teams N (2 ≤ N ≤ 100000) and the number of commands C (1 ≤ C ≤ 100000) are given. In the following C lines, commands are given. Each command is given in the following format.

 
0 t p

or

1 m

When the first number is 0, it indicates an update command, and when it is 1, it indicates a report command. In the update command, add the score p (1 ≤ p ≤ 10⁹), given as an integer, to the team with the given number t (1 ≤ t ≤ N). In the report command, report the number and score of the team in a given rank m (1 ≤ m ≤ N). However, the report command must appear at least once.

Output

For each report command, output the number and score of the team in a given rank in a line, separated by space.

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

---