EIU Programming Practices and Exams

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.

Example

Input:
5
1001 5
1002 4
1003 1
1006 0
1009 3

Output:
1006 1006 01006 0
1006 0
1003 1
1009 3
1002 4
1001 5 

1003 11009 3
002 4
1001 5