Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Jason is feeling rather hungry today. As such, he decides to raid his fridge. Upon arriving at his fridge, he realized that he could either eat his favourite snacks, or the most filling snacks. Help Jason decide on what he should eat by list the foods from least tasty to most tasty, and from least filling to most filling.

Input Specification

The first line has an integer N (1 \le N \le 100\,000), the number of foodstuffs in Jason's fridge.
The next N lines will have two integers, a_i and b_i (1 \le a_i, b_i \le 10^9), how filling and tasty the i^{th} foodstuff is, respectively. A foodstuff i is more filling than foodstuff j if a_i > a_j, and more tasty if b_i > b_j.

It is guaranteed that no two foodstuffs will be equally filling or tasty.

Output Specification

The output should consist of 2 lines.
The first line should contain N integers, with the i^{th} integer being the i^{th} least filling.
The second line should also contain N integers, with the i^{th} integer being the i^{th} least tasty.

Sample Input 1

5
1 5
2 4
3 3
4 2
5 1

Sample Output 1

1 2 3 4 5
5 4 3 2 1

Sample Input 2

5
5 3
3 5
6 7
1 4
8 1

Sample Output 2

4 2 1 3 5
5 1 4 2 3

Comments

There are no comments at the moment.