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: <image> (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 <image>.

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 <image>.

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:

<image>

(|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
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
long long x[N], y[N], i, j, n;
bool p;
vector<int> vct[1010];
vector<int>::iterator it;
vector<int>::reverse_iterator rit;
inline int read() {
  int s = 0;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    ;
  do {
    s = s * 10 + c - '0';
  } while ((c = getchar()) >= '0' && c <= '9');
  return s;
}
inline int abs(int a) { return a > 0 ? a : -a; }
bool cmp(const int &a, const int &b) { return y[a] < y[b]; }
int main() {
  n = read();
  for (i = 1; i <= n; i++) {
    x[i] = read(), y[i] = read();
    vct[x[i] / 1000].push_back(i);
  }
  for (i = 0; i <= 1000; i++) {
    if (vct[i].empty()) continue;
    p ^= 1;
    sort(vct[i].begin(), vct[i].end(), cmp);
    if (p)
      for (rit = vct[i].rbegin(); rit != vct[i].rend(); rit++)
        printf("%d ", (*rit));
    else
      for (it = vct[i].begin(); it != vct[i].end(); it++) printf("%d ", (*it));
  }
  return 0;
}
