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
#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
int print_value(A title, B val) {
  cout << title << " = " << val << "\n";
  return 1;
}
int break_point() {
  char c;
  while ((c = getchar()) != '\n')
    ;
  return 0;
}
template <typename A>
int logg(A v) {
  cout << v << "\n";
  return 0;
}
void read_intq(int &r) {
  r = 0;
  char c;
  while (1) {
    c = getchar();
    if (c != ' ' && c != '\n') {
      r = c - '0';
      break;
    }
  }
  while (1) {
    c = getchar();
    if (c == ' ' || c == '\n') return;
    r = r * 10 + (c - '0');
  }
}
void read_llq(long long &r) {
  r = 0;
  char c;
  while (1) {
    c = getchar();
    if (c != ' ' && c != '\n') {
      r = c - '0';
      break;
    }
  }
  while (1) {
    c = getchar();
    if (c == ' ' || c == '\n') return;
    r = r * 10 + (c - '0');
  }
}
char get_char() {
  char c;
  while (1) {
    c = getchar();
    if (c != '\n' && c != ' ') return c;
  }
}
void run();
int main() {
  srand(time(NULL));
  do {
    run();
    if (0) {
      0 ? printf("-------------------------------\n") : 0;
      0 ? printf("-------------------------------\n") : 0;
    }
  } while (0);
  return 0;
}
struct point {
  int x, y;
  int m;
  int idx;
  bool operator<(const point &p) const {
    if (m & 1)
      return y < p.y;
    else
      return y > p.y;
  }
};
int dist(point &p1, point &p2) { return abs(p1.x - p2.x) + abs(p1.y - p2.y); }
priority_queue<point> q[1001];
void run() {
  int n;
  scanf("%d", &n);
  point p;
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &p.x, &p.y);
    p.m = p.x / 1000;
    p.idx = i + 1;
    q[p.m].push(p);
  }
  for (int i = 0; i < 1001; i++) {
    while (!q[i].empty()) {
      printf("%d", q[i].top().idx);
      putchar(' ');
      q[i].pop();
    }
  }
  putchar('\n');
}
