#include <bits/stdc++.h>
using namespace std;
int N;
struct POINT {
  int x, y;
  int ind;
} P[1000000];
vector<POINT> p1, p2, p3, p4;
vector<int> ans;
void dfs(int s, int e, int x1, int y1, int x2, int y2) {
  if (e < s) return;
  if (s == e) {
    ans.push_back(P[s].ind);
    return;
  }
  int xm = (x1 + x2) >> 1;
  int ym = (y1 + y2) >> 1;
  p1.clear(), p2.clear(), p3.clear(), p4.clear();
  for (int i = s; i <= e; i++) {
    int x = P[i].x;
    int y = P[i].y;
    if (xm < x && ym < y) {
      p1.push_back(P[i]);
    } else if (x <= xm && ym < y) {
      p2.push_back(P[i]);
    } else if (x <= xm && y <= ym) {
      p3.push_back(P[i]);
    } else {
      p4.push_back(P[i]);
    }
  }
  int c = s;
  for (auto p : p1) P[c++] = p;
  for (auto p : p2) P[c++] = p;
  for (auto p : p3) P[c++] = p;
  for (auto p : p4) P[c++] = p;
  int s1 = p1.size(), s2 = p2.size(), s3 = p3.size(), s4 = p4.size();
  dfs(s, s + s1 - 1, xm + 1, ym + 1, x2, y2);
  s += s1;
  dfs(s, s + s2 - 1, x1, ym + 1, xm, y2);
  s += s2;
  dfs(s, s + s3 - 1, x1, y1, xm, ym);
  s += s3;
  dfs(s, s + s4 - 1, xm + 1, y1, x2, ym);
  s += s4;
}
int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%d%d", &P[i].x, &P[i].y);
    P[i].ind = i;
  }
  dfs(0, N - 1, 0, 0, 1000000, 1000000);
  for (auto n : ans) printf("%d ", n + 1);
  return 0;
}

### Prompt

Develop a solution in CPP 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;
struct POINT {
  int x, y;
  int ind;
} P[1000000];
vector<POINT> p1, p2, p3, p4;
vector<int> ans;
void dfs(int s, int e, int x1, int y1, int x2, int y2) {
  if (e < s) return;
  if (s == e) {
    ans.push_back(P[s].ind);
    return;
  }
  int xm = (x1 + x2) >> 1;
  int ym = (y1 + y2) >> 1;
  p1.clear(), p2.clear(), p3.clear(), p4.clear();
  for (int i = s; i <= e; i++) {
    int x = P[i].x;
    int y = P[i].y;
    if (xm < x && ym < y) {
      p1.push_back(P[i]);
    } else if (x <= xm && ym < y) {
      p2.push_back(P[i]);
    } else if (x <= xm && y <= ym) {
      p3.push_back(P[i]);
    } else {
      p4.push_back(P[i]);
    }
  }
  int c = s;
  for (auto p : p1) P[c++] = p;
  for (auto p : p2) P[c++] = p;
  for (auto p : p3) P[c++] = p;
  for (auto p : p4) P[c++] = p;
  int s1 = p1.size(), s2 = p2.size(), s3 = p3.size(), s4 = p4.size();
  dfs(s, s + s1 - 1, xm + 1, ym + 1, x2, y2);
  s += s1;
  dfs(s, s + s2 - 1, x1, ym + 1, xm, y2);
  s += s2;
  dfs(s, s + s3 - 1, x1, y1, xm, ym);
  s += s3;
  dfs(s, s + s4 - 1, xm + 1, y1, x2, ym);
  s += s4;
}
int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%d%d", &P[i].x, &P[i].y);
    P[i].ind = i;
  }
  dfs(0, N - 1, 0, 0, 1000000, 1000000);
  for (auto n : ans) printf("%d ", n + 1);
  return 0;
}

```