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 <class T>
T __sqr(const T x) {
  return x * x;
}
template <class T, class X>
inline T __pow(T a, X y) {
  T z = 1;
  for (int i = 1; i <= y; i++) {
    z *= a;
  }
  return z;
}
template <class T>
inline T gcd(T a, T b) {
  a = abs(a);
  b = abs(b);
  if (!b) return a;
  return __gcd(b, a % b);
}
template <class T>
inline T lcm(T a, T b) {
  a = abs(a);
  b = abs(b);
  return (a / __gcd(a, b)) * b;
}
inline bool ispow2(int x) { return (x != 0 && (x & (x - 1)) == 0); }
template <class T>
void UpdateMin(T &x, T y) {
  if (y < x) {
    x = y;
  }
}
template <class T>
void UpdateMax(T &x, T y) {
  if (x < y) {
    x = y;
  }
}
template <class T, class X, class Y>
inline T bigmod(T n, X m, Y mod) {
  unsigned long long ret = 1, a = n % mod;
  while (m) {
    if (m & 1) ret = (ret * a) % mod;
    m >>= 1;
    a = (a * a) % mod;
  }
  ret %= mod;
  return (T)ret;
}
template <class T, class Y>
inline T modinv(T n, Y mod) {
  return bigmod(n, mod - 2, mod);
}
template <class T, class X>
int getbit(T s, X i) {
  return (s >> i) & 1;
}
template <class T, class X>
T onbit(T s, X i) {
  return s | (T(1) << i);
}
template <class T, class X>
T offbit(T s, X i) {
  return s & (~(T(1) << i));
}
template <class T>
inline void read(T &n) {
  char c;
  for (c = getchar(); !(c >= '0' && c <= '9'); c = getchar())
    ;
  n = c - '0';
  for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - '0';
}
void extended_euclid(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1, y = 0;
    return;
  }
  long long first, second;
  extended_euclid(b, a % b, first, second);
  x = second;
  y = first - (a / b) * second;
}
pair<long long, pair<long long, long long> > extendedEuclid(long long a,
                                                            long long b) {
  long long x = 1, y = 0;
  long long xLast = 0, yLast = 1;
  long long q, r, m, n;
  while (a != 0) {
    q = b / a;
    r = b % a;
    m = xLast - q * x;
    n = yLast - q * y;
    xLast = x, yLast = y;
    x = m, y = n;
    b = a, a = r;
  }
  return make_pair(b, make_pair(xLast, yLast));
}
const long long mod[] = {0,          1000000007, 1000000009,
                         1000000021, 1000000033, 1000000097,
                         1000000093, 1000000097, 1000000103};
const long long base[] = {0,       1000003, 1000033, 1000037, 1000039,
                          1000081, 1000099, 1000117, 1000121};
struct DT {
  int x, y, idx;
  bool operator<(const DT &b) const {
    if ((x / 1000) == (b.x / 1000)) {
      int res = x / 1000;
      if (res & 1)
        return y > b.y;
      else
        return y < b.y;
    }
    return (x / 1000) < (b.x / 1000);
  }
} p[(1000000 + 20)];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i <= n - 1; i++) {
    scanf("%d%d", &p[i].x, &p[i].y);
    p[i].idx = i;
  }
  sort(p, p + n);
  for (int i = 0; i <= n - 1; i++) {
    printf("%d%c", p[i].idx + 1, i == (n - 1) ? '\n' : ' ');
  }
  return 0;
}
