#include <bits/stdc++.h>
using namespace std;
long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1ll;
  long long _tmp = mypow(_a, _x / 2, _mod);
  _tmp = (_tmp * _tmp) % _mod;
  if (_x & 1) _tmp = (_tmp * _a) % _mod;
  return _tmp;
}
bool equal(double _x, double _y) { return _x > _y - 1e-9 && _x < _y + 1e-9; }
int __ = 1, cs;
long long sum, n, x[1000010], y[1000010];
vector<int> v[1001 + 10][1001 + 10];
void build() {}
vector<int> ans;
long long dis(int tu, int tv) {
  return abs(x[tu] - x[tv]) + abs(y[tu] - y[tv]);
}
void init() {
  n = getint();
  for (int i = 1; i <= n; i++) {
    x[i] = getint();
    y[i] = getint();
    v[x[i] / 1001][y[i] / 1001].push_back(i);
  }
  for (int i = 0; i <= 1000010 / 1001; i++)
    if (i & 1) {
      for (int j = 0; j <= 1000010 / 1001; j++)
        for (int k = 0; k < (int)v[i][j].size(); k++) ans.push_back(v[i][j][k]);
    } else {
      for (int j = 1000010 / 1001; j >= 0; j--)
        for (int k = 0; k < (int)v[i][j].size(); k++) ans.push_back(v[i][j][k]);
    }
  for (int i = 1; i < n; i++) sum += dis(ans[i - 1], ans[i]);
}
void solve() {
  srand(514514);
  while (sum > 2500000000ll) {
    int tx = ((long long)rand() * (long long)rand()) % n;
    int ty = ((long long)rand() * (long long)rand()) % n;
    if (tx == ty) continue;
    long long tsum = sum;
    if (tx) tsum -= dis(ans[tx - 1], ans[tx]);
    if (tx < n - 1) tsum -= dis(ans[tx], ans[tx + 1]);
    if (ty && tx != ty - 1) tsum -= dis(ans[ty - 1], ans[ty]);
    if (ty < n - 1 && tx != ty + 1) tsum -= dis(ans[ty], ans[ty + 1]);
    swap(ans[tx], ans[ty]);
    if (tx) tsum += dis(ans[tx - 1], ans[tx]);
    if (tx < n - 1) tsum += dis(ans[tx], ans[tx + 1]);
    if (ty && tx != ty - 1) tsum += dis(ans[ty - 1], ans[ty]);
    if (ty < n - 1 && tx != ty + 1) tsum += dis(ans[ty], ans[ty + 1]);
    if (tsum >= sum)
      swap(ans[tx], ans[ty]);
    else
      sum = tsum;
  }
  for (int i = 0; i < n; i++) printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}

### Prompt

Your challenge is to write a Cpp solution to 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 getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1ll;
  long long _tmp = mypow(_a, _x / 2, _mod);
  _tmp = (_tmp * _tmp) % _mod;
  if (_x & 1) _tmp = (_tmp * _a) % _mod;
  return _tmp;
}
bool equal(double _x, double _y) { return _x > _y - 1e-9 && _x < _y + 1e-9; }
int __ = 1, cs;
long long sum, n, x[1000010], y[1000010];
vector<int> v[1001 + 10][1001 + 10];
void build() {}
vector<int> ans;
long long dis(int tu, int tv) {
  return abs(x[tu] - x[tv]) + abs(y[tu] - y[tv]);
}
void init() {
  n = getint();
  for (int i = 1; i <= n; i++) {
    x[i] = getint();
    y[i] = getint();
    v[x[i] / 1001][y[i] / 1001].push_back(i);
  }
  for (int i = 0; i <= 1000010 / 1001; i++)
    if (i & 1) {
      for (int j = 0; j <= 1000010 / 1001; j++)
        for (int k = 0; k < (int)v[i][j].size(); k++) ans.push_back(v[i][j][k]);
    } else {
      for (int j = 1000010 / 1001; j >= 0; j--)
        for (int k = 0; k < (int)v[i][j].size(); k++) ans.push_back(v[i][j][k]);
    }
  for (int i = 1; i < n; i++) sum += dis(ans[i - 1], ans[i]);
}
void solve() {
  srand(514514);
  while (sum > 2500000000ll) {
    int tx = ((long long)rand() * (long long)rand()) % n;
    int ty = ((long long)rand() * (long long)rand()) % n;
    if (tx == ty) continue;
    long long tsum = sum;
    if (tx) tsum -= dis(ans[tx - 1], ans[tx]);
    if (tx < n - 1) tsum -= dis(ans[tx], ans[tx + 1]);
    if (ty && tx != ty - 1) tsum -= dis(ans[ty - 1], ans[ty]);
    if (ty < n - 1 && tx != ty + 1) tsum -= dis(ans[ty], ans[ty + 1]);
    swap(ans[tx], ans[ty]);
    if (tx) tsum += dis(ans[tx - 1], ans[tx]);
    if (tx < n - 1) tsum += dis(ans[tx], ans[tx + 1]);
    if (ty && tx != ty - 1) tsum += dis(ans[ty - 1], ans[ty]);
    if (ty < n - 1 && tx != ty + 1) tsum += dis(ans[ty], ans[ty + 1]);
    if (tsum >= sum)
      swap(ans[tx], ans[ty]);
    else
      sum = tsum;
  }
  for (int i = 0; i < n; i++) printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}

```