Uolevi is bored in class and is scribbling an incoherent shape in his notebook. He keeps his pen on the paper at all times and connects dots that he drew earlier with straight lines. On each dot he is going to make at least a 90^\circ turn to the next dot. There are n dots numbered 1,2,\dots,n. The i-th dot's position on the paper is (x_i, y_i). Find a way to connect the dots in this zig-zag pattern. It can be proven that such a pattern always exists.

Input

The first line contains a single integer n. The i-th of next n following lines contains two integers x_i and y_i.

Output

Print the order in which the dots are connected on a single line. If there are multiple answers, print any as follows:

ans_1\,\,ans_2\,\,\dots\,\,ans_n

Constraints

• 2 \leq n \leq 2000
• 1 \leq x_i, y_i \leq 10^9
• (x_i, y_i) \neq (x_j, y_j) if i \neq j
• All input values are integers.
• 1 \leq ans_i \leq n
• ans_i \neq ans_j if i \neq j

Example 1

Input:

4
1 1
1 2
2 2
2 1

Output:

1 2 3 4

Example 2

Input:

6
1 4
2 1
3 6
3 4
3 3
5 1

Output:

2 4 1 3 6 5