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
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class CF_577E {
	public static void main(String[] args) throws IOException {
		FastScanner scan = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		int n = scan.nextInt();
		Point[] pts = new Point[n];
		for (int i = 0; i < n; i++) {
			pts[i] = new Point(i + 1, scan.nextInt(), scan.nextInt());
		}
		Arrays.sort(pts);
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			if(i != 0) {
				sb.append(' ');
			}
			sb.append(pts[i].idx);
		}
		out.println(sb.toString());
		out.close();
	}

	static class Point implements Comparable<Point>{
		long x, y;
		long xGroup;
		int xGroupParity;
		int idx;

		public Point(int idx, int x, int y) {
			this.idx = idx;
			this.x = x;
			this.y = y;
			this.xGroup = x / 1000;
			this.xGroupParity = (int) (this.xGroup % 2);
			//this.d = xy2d(1000001L * 1000001L, x, y);
		}
		@Override
		public int compareTo(Point o) {
			if(xGroup == o.xGroup) {
				if(xGroupParity == 0)
					return Long.compare(y, o.y);
				else
					return -Long.compare(y,o.y);
			}
			return Long.compare(x, o.x);
		}
	}


	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(InputStream i) {
			br = new BufferedReader(new InputStreamReader(i));
			st = new StringTokenizer("");
		}

		public FastScanner(File f) throws IOException {
			br = new BufferedReader(new FileReader(f));
			st = new StringTokenizer("");
		}

		public String next() throws IOException {
			if (st.hasMoreTokens())
				return st.nextToken();
			st = new StringTokenizer(br.readLine());
			return next();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
	}
	/*
	public static BigInteger xy2d(long n, long x, long y) {
		long s;
		BigInteger d = BigInteger.ZERO;
		int rx, ry;
		BigInteger tmp;
		for (s = n / 2; s > 0; s >>= 1) {
			rx = (x & s) > 0 ? 1 : 0;
			ry = (y & s) > 0 ? 1 : 0;
			tmp = BigInteger.valueOf(s);
			tmp = tmp.multiply(tmp);
			tmp = tmp.multiply(BigInteger.valueOf(((3 * rx) ^ ry)));
			d = d.add(tmp);
			if (ry == 0) {
				if (rx == 1) {
					x = n - 1 - x;
					y = n - 1 - y;
				}

				// Swap x and y
				long t = x;
				x = y;
				y = t;
			}
		}
		return d;
	}*/
}
