#include <bits/stdc++.h>
using namespace std;
int N, x[(1 << 20)], y[(1 << 20)], L, R, T, B, S;
int LR[(1024) + 1], BT[(50) + 1];
struct it {
  it(int i) : i(i) {}
  int i;
  bool operator<(const it& r) const { return x[i] + y[i] < x[r.i] + y[r.i]; }
};
vector<it> p[(1024)][(50)];
int ftx(int x) {
  for (int i(0); i < (1024); ++i)
    if (LR[i] > x) return i - 1;
  return (1024) - 1;
}
int fty(int y) {
  for (int i(0); i < (50); ++i)
    if (BT[i] > y) return i - 1;
  return (50) - 1;
}
int main(void) {
  scanf("%d", &N);
  for (int i(0); i < N; ++i)
    scanf("%d%d", x + i, y + i), L = min(L, x[i]), R = max(R, x[i]),
                                 T = max(T, y[i]), B = min(B, y[i]);
  R += (1024) + 1, T += (50) + 1;
  int sx((R - L) / (1024)), sy((T - B) / (50));
  for (int i(L), j(0); j < (1024); ++j, i += sx) LR[j] = i;
  for (int k(B), j(0); j < (50); ++j, k += sy) BT[j] = k;
  LR[(1024)] = R, BT[(50)] = T;
  for (int i(0); i < N; ++i) p[ftx(x[i])][fty(y[i])].push_back(it(i));
  for (int j(0); j < (1024); ++j)
    for (int k(0); k < (50); ++k) sort(p[j][k].begin(), p[j][k].end());
  for (int j(0); j < (1024) >> 1; ++j) {
    for (int k(0); k < (50); ++k)
      for (auto i : p[j << 1][k])
        printf("%d%c", i.i + 1, ++S == N ? '\n' : ' ');
    for (int k((50) - 1); ~k; --k)
      for (auto i : p[(j << 1) + 1][k])
        printf("%d%c", i.i + 1, ++S == N ? '\n' : ' ');
  }
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int N, x[(1 << 20)], y[(1 << 20)], L, R, T, B, S;
int LR[(1024) + 1], BT[(50) + 1];
struct it {
  it(int i) : i(i) {}
  int i;
  bool operator<(const it& r) const { return x[i] + y[i] < x[r.i] + y[r.i]; }
};
vector<it> p[(1024)][(50)];
int ftx(int x) {
  for (int i(0); i < (1024); ++i)
    if (LR[i] > x) return i - 1;
  return (1024) - 1;
}
int fty(int y) {
  for (int i(0); i < (50); ++i)
    if (BT[i] > y) return i - 1;
  return (50) - 1;
}
int main(void) {
  scanf("%d", &N);
  for (int i(0); i < N; ++i)
    scanf("%d%d", x + i, y + i), L = min(L, x[i]), R = max(R, x[i]),
                                 T = max(T, y[i]), B = min(B, y[i]);
  R += (1024) + 1, T += (50) + 1;
  int sx((R - L) / (1024)), sy((T - B) / (50));
  for (int i(L), j(0); j < (1024); ++j, i += sx) LR[j] = i;
  for (int k(B), j(0); j < (50); ++j, k += sy) BT[j] = k;
  LR[(1024)] = R, BT[(50)] = T;
  for (int i(0); i < N; ++i) p[ftx(x[i])][fty(y[i])].push_back(it(i));
  for (int j(0); j < (1024); ++j)
    for (int k(0); k < (50); ++k) sort(p[j][k].begin(), p[j][k].end());
  for (int j(0); j < (1024) >> 1; ++j) {
    for (int k(0); k < (50); ++k)
      for (auto i : p[j << 1][k])
        printf("%d%c", i.i + 1, ++S == N ? '\n' : ' ');
    for (int k((50) - 1); ~k; --k)
      for (auto i : p[(j << 1) + 1][k])
        printf("%d%c", i.i + 1, ++S == N ? '\n' : ' ');
  }
  return 0;
}

```