#include <bits/stdc++.h>
using namespace std;
struct node {
  double x, y;
  int no;
};
vector<node> pt;
vector<node> part;
vector<int> res;
bool cmp1(node a, node b) { return a.x < b.x; }
bool cmp2(node a, node b) { return a.y < b.y; }
int main() {
  int i, j, k;
  double x, y;
  int n, p, cur;
  node point;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%lf%lf", &x, &y);
    point.x = x;
    point.y = y;
    point.no = i + 1;
    pt.push_back(point);
  }
  sort(pt.begin(), pt.end(), cmp1);
  p = 0;
  cur = 1;
  for (i = 0; i < 1000; i++) {
    double l, r;
    l = i * 1000;
    r = l + 1000;
    part.clear();
    for (; p < n && pt[p].x <= r; p++) {
      point = pt[p];
      point.y = point.y * cur;
      part.push_back(point);
    }
    sort(part.begin(), part.end(), cmp2);
    cur = cur * -1;
    for (j = 0; j < part.size(); j++) res.push_back(part[j].no);
  }
  printf("%d", res[0]);
  for (i = 1; i < n; i++) printf(" %d", res[i]);
  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;
struct node {
  double x, y;
  int no;
};
vector<node> pt;
vector<node> part;
vector<int> res;
bool cmp1(node a, node b) { return a.x < b.x; }
bool cmp2(node a, node b) { return a.y < b.y; }
int main() {
  int i, j, k;
  double x, y;
  int n, p, cur;
  node point;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%lf%lf", &x, &y);
    point.x = x;
    point.y = y;
    point.no = i + 1;
    pt.push_back(point);
  }
  sort(pt.begin(), pt.end(), cmp1);
  p = 0;
  cur = 1;
  for (i = 0; i < 1000; i++) {
    double l, r;
    l = i * 1000;
    r = l + 1000;
    part.clear();
    for (; p < n && pt[p].x <= r; p++) {
      point = pt[p];
      point.y = point.y * cur;
      part.push_back(point);
    }
    sort(part.begin(), part.end(), cmp2);
    cur = cur * -1;
    for (j = 0; j < part.size(); j++) res.push_back(part[j].no);
  }
  printf("%d", res[0]);
  for (i = 1; i < n; i++) printf(" %d", res[i]);
  return 0;
}

```