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.util.*;
import java.io.*;

public class Main {
	BufferedReader in;
	PrintWriter out;
	StringTokenizer str;

	private String next() throws Exception {
		if (str == null || !str.hasMoreElements())
			str = new StringTokenizer(in.readLine());
		return str.nextToken();
	}

	private int nextInt() throws Exception {
		return Integer.parseInt(next());
	}

	int n;
	P []p;

	final int WIDTH = 1000;
	
	public void run() throws Exception {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		
		n = nextInt();
		p = new P[n];
		for(int i = 0; i < n; ++i) {
			p[i] = new P(nextInt(), nextInt(), i + 1);
		}
		
		Arrays.sort(p);
		int at = 0;

		for(int i = 0; i <= 1000; ++i) {
			int lo = i * WIDTH, hi = (i + 1) * WIDTH;
			List<P> pts = new ArrayList<>();
			while(at < n && lo <= p[at].x && p[at].x < hi) {
				pts.add(p[at++]);
			}
			if (i % 2 == 0) {
				Collections.sort(pts, new Comparator<P>(){
					public int compare(P p1, P p2) {
						if (p1.y != p2.y)
							return p1.y - p2.y;
						return p1.x - p2.x;
					}
				});
			} else {
				Collections.sort(pts, new Comparator<P>() {
					public int compare(P p1, P p2) {
						if (p1.y != p2.y)
							return p2.y - p1.y;
						return p2.x - p1.x;
					}
				});
			}
			for(P pt : pts) out.print(pt.pos + " ");
		}
		out.println();
		out.close();
	}

	class P implements Comparable<P> {
		int x, y, pos;
		public P(int x, int y, int pos) {
			this.x = x;
			this.y = y;
			this.pos = pos;
		}

		public int compareTo(P other) {
			if (this.x != other.x) 
				return this.x - other.x;
			return this.y - other.y;
		}
	}

	public static void main(String args[]) throws Exception {
		new Main().run();
	}
}
