Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.
On a plane are n points (xi, yi) with integer coordinates between 0 and 106. 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 pi 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 × 108. Note that you do not have to minimize the path length.
Input
The first line contains integer n (1 ≤ n ≤ 106).
The i + 1-th line contains the coordinates of the i-th point: xi and yi (0 ≤ xi, yi ≤ 106).
It is guaranteed that no two points coincide.
Output
Print the permutation of numbers pi from 1 to n — the sought Hamiltonian path. The permutation must meet the inequality .
If there are multiple possible answers, print any of them.