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 listing 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