#include <bits/stdc++.h>
using namespace std;
long long big = 1000000007ll;
long long bp = 1168195727ll;
std::vector<int> A;
std::vector<int> B;
std::vector<int> X;
std::vector<int> Y;
int n;
void rek(int x1, int x2, int y1, int y2, int l, int r) {
  int xh = (x1 + x2) / 2;
  int yh = (y1 + y2) / 2;
  int n1, n2, n3, n4;
  n1 = 0;
  n2 = 0;
  n3 = 0;
  n4 = 0;
  if (l == r) {
    return;
  }
  int c;
  for (c = l; c <= r; c++) {
    B[c] = A[c];
  }
  long long xt, yt;
  long long lt = l;
  long long k = 0;
  for (c = l; c <= r; c++) {
    xt = X[B[c]];
    yt = Y[B[c]];
    if (xt <= xh && yt <= yh) {
      n1++;
      lt++;
      A[l + k] = B[c];
      k++;
    }
  }
  for (c = l; c <= r; c++) {
    xt = X[B[c]];
    yt = Y[B[c]];
    if (xt > xh && yt <= yh) {
      n2++;
      lt++;
      A[l + k] = B[c];
      k++;
    }
  }
  for (c = l; c <= r; c++) {
    xt = X[B[c]];
    yt = Y[B[c]];
    if (xt > xh && yt > yh) {
      n3++;
      lt++;
      A[l + k] = B[c];
      k++;
    }
  }
  for (c = l; c <= r; c++) {
    xt = X[B[c]];
    yt = Y[B[c]];
    if (xt <= xh && yt > yh) {
      n4++;
      lt++;
      A[l + k] = B[c];
      k++;
    }
  }
  if (n1 != 0) {
    rek(x1, xh, y1, yh, l, l + n1 - 1);
  }
  if (n2 != 0) {
    rek(xh + 1, x2, y1, yh, l + n1, l + n1 + n2 - 1);
  }
  if (n3 != 0) {
    rek(xh + 1, x2, yh + 1, y2, l + n1 + n2, l + n1 + n2 + n3 - 1);
  }
  if (n4 != 0) {
    rek(x1, xh, yh + 1, y2, l + n1 + n2 + n3, l + n1 + n2 + n3 + n4 - 1);
  }
  return;
}
int main() {
  long long c1, c2, c3, c4, c5, c6;
  long long T;
  int a, b;
  scanf("%d", &n);
  for (c1 = 0; c1 < n; c1++) {
    scanf("%d %d", &a, &b);
    X.push_back(a);
    Y.push_back(b);
    A.push_back(c1);
    B.push_back(c1);
  }
  rek(0, 1000000, 0, 1000000, 0, n - 1);
  for (c1 = 0; c1 < n - 1; c1++) {
    printf("%d ", A[c1] + 1);
  }
  printf("%d\n", A[n - 1] + 1);
  return 0;
}

### Prompt

Create a solution in CPP for the following problem:

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;
long long big = 1000000007ll;
long long bp = 1168195727ll;
std::vector<int> A;
std::vector<int> B;
std::vector<int> X;
std::vector<int> Y;
int n;
void rek(int x1, int x2, int y1, int y2, int l, int r) {
  int xh = (x1 + x2) / 2;
  int yh = (y1 + y2) / 2;
  int n1, n2, n3, n4;
  n1 = 0;
  n2 = 0;
  n3 = 0;
  n4 = 0;
  if (l == r) {
    return;
  }
  int c;
  for (c = l; c <= r; c++) {
    B[c] = A[c];
  }
  long long xt, yt;
  long long lt = l;
  long long k = 0;
  for (c = l; c <= r; c++) {
    xt = X[B[c]];
    yt = Y[B[c]];
    if (xt <= xh && yt <= yh) {
      n1++;
      lt++;
      A[l + k] = B[c];
      k++;
    }
  }
  for (c = l; c <= r; c++) {
    xt = X[B[c]];
    yt = Y[B[c]];
    if (xt > xh && yt <= yh) {
      n2++;
      lt++;
      A[l + k] = B[c];
      k++;
    }
  }
  for (c = l; c <= r; c++) {
    xt = X[B[c]];
    yt = Y[B[c]];
    if (xt > xh && yt > yh) {
      n3++;
      lt++;
      A[l + k] = B[c];
      k++;
    }
  }
  for (c = l; c <= r; c++) {
    xt = X[B[c]];
    yt = Y[B[c]];
    if (xt <= xh && yt > yh) {
      n4++;
      lt++;
      A[l + k] = B[c];
      k++;
    }
  }
  if (n1 != 0) {
    rek(x1, xh, y1, yh, l, l + n1 - 1);
  }
  if (n2 != 0) {
    rek(xh + 1, x2, y1, yh, l + n1, l + n1 + n2 - 1);
  }
  if (n3 != 0) {
    rek(xh + 1, x2, yh + 1, y2, l + n1 + n2, l + n1 + n2 + n3 - 1);
  }
  if (n4 != 0) {
    rek(x1, xh, yh + 1, y2, l + n1 + n2 + n3, l + n1 + n2 + n3 + n4 - 1);
  }
  return;
}
int main() {
  long long c1, c2, c3, c4, c5, c6;
  long long T;
  int a, b;
  scanf("%d", &n);
  for (c1 = 0; c1 < n; c1++) {
    scanf("%d %d", &a, &b);
    X.push_back(a);
    Y.push_back(b);
    A.push_back(c1);
    B.push_back(c1);
  }
  rek(0, 1000000, 0, 1000000, 0, n - 1);
  for (c1 = 0; c1 < n - 1; c1++) {
    printf("%d ", A[c1] + 1);
  }
  printf("%d\n", A[n - 1] + 1);
  return 0;
}

```