Given a list of employees including employee ID and sales for a month. Let's sort the above list using the Insertion Sort algorithm by sales.

Input

Each Testcase consists of several lines:

• The first line is an integer ~N~ (~1~ ≤ ~N~ ≤ ~3*10^{4}~) which is the number of employees.

• The ith line of the next ~N~ lines contains the integer ~mi~, which is the employee number, and the integer ~ai~, the month's sales (~0~ ≤ ~mi~, ~ai~ ≤ ~10^{9}~).

Output

• Output ~N~ lines, each line includes employee code and corresponding sales in sorted order.

Sample Input:

5
1001 5
1002 4
1003 1
1006 0
1009 3

Sample Output:

1006 0
1003 1
1009 3
1002 4
1001 5