You need to implement the merge$-$sort algorithm to sort a list of cities, but the sorting should only consider the population of the cities. No other criteria should be used in the sorting process. However, if two cities have the same population, they should maintain their original order as in the input. This is commonly referred to as a $$stable sort$.$ An O$($nlogn$)-$time algorithm is sufficient to pass any feasible test cases.

Input You need to read the input from the console. The input consists of n lines of data. Each line i contains two positive integers: ai$,$ which is the index of the city, and pi$,$ representing the population of the city. You can assume that $1<=$ ai $<=1000$ and $1000<=$ pi $<=1000000.$

Output You need to output to console. The output from line $1$ to line n$,$ you need to output the cities in ascending order of population.

Example: Below are examples of input and output:

Example input: Example output:

$210000210000$

$110000110000$

$4200001010000$

$520000420000$

$630000520000$

$342000630000$

$986000342000$

$1010000750000$

$7500001167000$

$1167000986000$

$12100000893000$

$89300012100000$