Conveyor#5332
General Grievous has a more realistic view on the quality of droids compared to Emperor Palpatine. He believes that the newer a droid, the better it is.
You are given droids on a conveyor belt. To satisfy Grievous, sort the droids in ascending order of their year of manufacture (which may be negative). The sorting must be stable; in other words, if two droids have the same year, they must appear in the sorted array in the same order as they appeared initially.
The first line contains an integer (2 \le N \le 10^5) — the number of droids. Each of the next lines contains a description of a droid: a string of exactly four characters (the name of the droid), and an integer whose absolute value does not exceed 2\cdot10^9 (the year of manufacture).
Output the names of the droids in order, sorted by their year of manufacture. Among droids with the same year, those that appeared earlier in the input should come first.
Example 1