Description
Elephants form two types of formations during migration:
- Sorted by Age: Ensures that older elephants can correctly lead the group to their destination.
- Sorted by Height: Ensures that elephants at the rear can see every elephant in front of them.
Elephants prefer using merge sort. Please help them sort by age and height separately and print the results. If there are identical values while sorting, the original relative order of index should be preserved (stable sort).
This is a partial judge problem. You only need to implement merge_by_age() and merge_by height() functions, the output function has already been provided for you.
Input
The first line contains a single integer n - the number of elephants.
2 ≤ n ≤ 105
The following n lines each line contain two integer a, h - the age and height of i-th elephant.
1 ≤ a, h ≤ 109
(Elephants are tall and long-lived animals.)
Output
Output the result of the index in each merge section, the format has already been implemented in the given function.