The results of the Olympiad

During the contest, each participant received a unique identification number - a positive integer. Need to sort a list of participants of the Olympiad on the number of points scored.

Input

The first line contains the number N (1 ≤ N ≤ 1000) - the number of participants. In each following line gives an identification number and dialed the number of points corresponding to the participant. All numbers in the input file does not exceed 10^5.

Output

The output file output source list in descending order of points. If some participants in the same score, they each want to sort in ascending order of ID number.

Examples