No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Points on Plane

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOn a plane are *n* points (*x*_{i}, *y*_{i}) with integer coordinates between 0 and 10^{6}. The distance between the two points with numbers *a* and *b* is said to be the following value: (the distance calculated by such formula is called Manhattan distance).

We call a hamiltonian path to be some permutation *p*_{i} of numbers from 1 to *n*. We say that the length of this path is value .

Find some hamiltonian path with a length of no more than 25 × 10^{8}. Note that you do not have to minimize the path length.

Input

The first line contains integer *n* (1 ≤ *n* ≤ 10^{6}).

The *i* + 1-th line contains the coordinates of the *i*-th point: *x*_{i} and *y*_{i} (0 ≤ *x*_{i}, *y*_{i} ≤ 10^{6}).

It is guaranteed that no two points coincide.

Output

Print the permutation of numbers *p*_{i} from 1 to *n* — the sought Hamiltonian path. The permutation must meet the inequality .

If there are multiple possible answers, print any of them.

It is guaranteed that the answer exists.

Examples

Input

5

0 7

8 10

3 4

5 0

9 12

Output

4 3 1 2 5

Note

In the sample test the total distance is:

(|5 - 3| + |0 - 4|) + (|3 - 0| + |4 - 7|) + (|0 - 8| + |7 - 10|) + (|8 - 9| + |10 - 12|) = 2 + 4 + 3 + 3 + 8 + 3 + 1 + 2 = 26

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/18/2021 11:40:18 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|