#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
inline void smin(T &a, const U &b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, const U &b) {
  if (a < b) a = b;
}
template <typename T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T, class T1>
inline void gn(T &first, T1 &second) {
  gn(first);
  gn(second);
}
template <class T, class T1, class T2>
inline void gn(T &first, T1 &second, T2 &z) {
  gn(first);
  gn(second);
  gn(z);
}
template <typename T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <typename T>
inline void println(T first) {
  print(first), putchar('\n');
}
template <typename T>
inline void printsp(T first) {
  print(first), putchar(' ');
}
template <class T, class T1>
inline void print(T first, T1 second) {
  printsp(first), println(second);
}
template <class T, class T1, class T2>
inline void print(T first, T1 second, T2 z) {
  printsp(first), printsp(second), println(z);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = (long long)a * a % m)
    if (b & 1) ans = (long long)ans * a % m;
  return ans;
}
struct point {
  int first, second, id;
  point(int first = 0, int second = 0, int id = 0)
      : first(first), second(second), id(id) {}
  point operator-(point a) { return point(first - a.first, second - a.second); }
  point operator+(point a) { return point(first + a.first, second + a.second); }
  point operator*(int a) { return point(first * a, second * a); }
  point operator/(int a) { return point(first / a, second / a); }
  point operator&(point a) {
    return point(first * a.first - second * a.second,
                 first * a.second + second * a.first);
  }
  point rotate(double al) { return *this & point(cos(al), sin(al)); }
  long long operator^(point a) {
    return 1LL * first * a.second - 1LL * second * a.first;
  }
  long long operator*(point a) {
    return 1LL * first * a.first + 1LL * second * a.second;
  }
  point conj() { return point(-second, first); }
  double nor() { return sqrt(*this * *this); }
  long long nor2() { return *this * *this; }
  double al() { return atan2(second, first); }
  bool operator<(const point &a) const {
    if (first != a.first) return first < a.first;
    return second < a.second;
  }
  bool operator>(const point &a) const {
    if (first != a.first) return first > a.first;
    return second > a.second;
  }
  bool operator==(const point &a) const {
    return (first == a.first && second == a.second);
  }
  bool operator!=(const point &a) const {
    return (first != a.first || second != a.second);
  }
  void input(int u) {
    gn(first, second);
    id = u;
  }
  void print() { printf("%d %d\n", first, second); }
};
point p[1000010];
bool cmp(point a, point b) { return a.second < b.second; }
int main() {
  int n;
  gn(n);
  for (int i = 1; i <= n; i++) p[i].input(i);
  sort(p + 1, p + n + 1);
  int pre = 1, dir = 1;
  p[++n] = point(0x3f3f3f3f, 0);
  for (int i = 2; i <= n; i++)
    if (p[i].first - p[pre].first > 1000) {
      sort(p + pre, p + i, cmp);
      if (dir) {
        for (int j = pre; j < i; j++) {
          printsp(p[j].id);
        }
      } else {
        for (int j = i; j-- > pre;) {
          printsp(p[j].id);
        }
      }
      dir ^= 1;
      pre = i;
    }
}

### Prompt

In Cpp, your task is to solve 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;
template <typename T, typename U>
inline void smin(T &a, const U &b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, const U &b) {
  if (a < b) a = b;
}
template <typename T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T, class T1>
inline void gn(T &first, T1 &second) {
  gn(first);
  gn(second);
}
template <class T, class T1, class T2>
inline void gn(T &first, T1 &second, T2 &z) {
  gn(first);
  gn(second);
  gn(z);
}
template <typename T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <typename T>
inline void println(T first) {
  print(first), putchar('\n');
}
template <typename T>
inline void printsp(T first) {
  print(first), putchar(' ');
}
template <class T, class T1>
inline void print(T first, T1 second) {
  printsp(first), println(second);
}
template <class T, class T1, class T2>
inline void print(T first, T1 second, T2 z) {
  printsp(first), printsp(second), println(z);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = (long long)a * a % m)
    if (b & 1) ans = (long long)ans * a % m;
  return ans;
}
struct point {
  int first, second, id;
  point(int first = 0, int second = 0, int id = 0)
      : first(first), second(second), id(id) {}
  point operator-(point a) { return point(first - a.first, second - a.second); }
  point operator+(point a) { return point(first + a.first, second + a.second); }
  point operator*(int a) { return point(first * a, second * a); }
  point operator/(int a) { return point(first / a, second / a); }
  point operator&(point a) {
    return point(first * a.first - second * a.second,
                 first * a.second + second * a.first);
  }
  point rotate(double al) { return *this & point(cos(al), sin(al)); }
  long long operator^(point a) {
    return 1LL * first * a.second - 1LL * second * a.first;
  }
  long long operator*(point a) {
    return 1LL * first * a.first + 1LL * second * a.second;
  }
  point conj() { return point(-second, first); }
  double nor() { return sqrt(*this * *this); }
  long long nor2() { return *this * *this; }
  double al() { return atan2(second, first); }
  bool operator<(const point &a) const {
    if (first != a.first) return first < a.first;
    return second < a.second;
  }
  bool operator>(const point &a) const {
    if (first != a.first) return first > a.first;
    return second > a.second;
  }
  bool operator==(const point &a) const {
    return (first == a.first && second == a.second);
  }
  bool operator!=(const point &a) const {
    return (first != a.first || second != a.second);
  }
  void input(int u) {
    gn(first, second);
    id = u;
  }
  void print() { printf("%d %d\n", first, second); }
};
point p[1000010];
bool cmp(point a, point b) { return a.second < b.second; }
int main() {
  int n;
  gn(n);
  for (int i = 1; i <= n; i++) p[i].input(i);
  sort(p + 1, p + n + 1);
  int pre = 1, dir = 1;
  p[++n] = point(0x3f3f3f3f, 0);
  for (int i = 2; i <= n; i++)
    if (p[i].first - p[pre].first > 1000) {
      sort(p + pre, p + i, cmp);
      if (dir) {
        for (int j = pre; j < i; j++) {
          printsp(p[j].id);
        }
      } else {
        for (int j = i; j-- > pre;) {
          printsp(p[j].id);
        }
      }
      dir ^= 1;
      pre = i;
    }
}

```