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.*;
/*
3
111
001
010

5
11101
00111
10101
00000
11000

1
11111111111111111111

3
1000
1100
1110

4
111
111
110
100

20
0000
1000
1100
1010
0101
0011
0111
1110
1100
0110
1001
0000
1000
1100
1010
0101
0011
0111
1110
1100
0110


*/
public class eight 
{	
	public static void main(String[] arg) throws IOException
	{
		new eight();
	}
	public eight()
	{
		FastScanner in = new FastScanner(System.in);
		//Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = in.nextInt();
		Point[] arr = new Point[n];
		for(int i = 0; i < n; i++)
		{
			arr[i] = new Point(in.nextInt(), in.nextInt(), i);
		}
		Arrays.sort(arr);
		for(Point p : arr)
		{
			out.print((p.index+1)+" ");
		}
		in.close(); out.close();
	}
	int split = (int)1e3;
	class Point implements Comparable<Point>
	{
		public int x, y, index;
		public Point(int a, int b, int c)
		{
			x = a;
			y = b;
			index = c;
		}
		public int compareTo(Point a)
		{
			if(x/split != a.x/split)
				return (x/split)-(a.x/split);
			if((x/split)%2 == 0) return y-a.y;
			else return a.y-y;
		}
		public int dist(Point a)
		{
			return Math.abs(x-a.x)+Math.abs(y-a.y);
		}
	}
	class FastInput 
	{
		BufferedReader reader;
		StringTokenizer tokenizer;
		
		public FastInput(InputStream input)
		{
			reader = new BufferedReader(new InputStreamReader(input));
			tokenizer = new StringTokenizer("");
		}
		String next() throws IOException
		{
			while( ! tokenizer.hasMoreTokens() )
			{
				tokenizer = new StringTokenizer(reader.readLine());
			}
			return tokenizer.nextToken();
		}
		String nextLine() throws IOException { return reader.readLine(); }
		char nextChar() throws IOException { return next().charAt(0); }
		int nextInt() throws IOException { return Integer.parseInt(next()); }
		double nextDouble() throws IOException { return Double.parseDouble(next()); }
		long nextLong() throws IOException { return Long.parseLong(next()); }
		void close() throws IOException { reader.close(); }
	}
	class JoltyScanner 
	{
	    public static final int BUFFER_SIZE = 1 << 16;
		public static final char NULL_CHAR = (char) -1;

	    byte[] buffer = new byte[BUFFER_SIZE];
		boolean EOF_FLAG = false;
		int bufferIdx = 0, size = 0;
		char c = NULL_CHAR;
		BufferedInputStream in;

		public JoltyScanner(InputStream in) 
		{
			this.in = new BufferedInputStream(in, BUFFER_SIZE);
		}

		public int nextInt() 
		{
			long x = nextLong();
			if (x > Integer.MAX_VALUE || x < Integer.MIN_VALUE) 
			{
				throw new ArithmeticException("Scanned value overflows integer");
			}
			return (int) x;
		}

		public long nextLong() 
		{
			boolean negative = false;
			if (c == NULL_CHAR) 
			{
				c = nextChar();
			}
			for (; !EOF_FLAG && (c < '0' || c > '9'); c = nextChar()) 
			{
				if (c == '-') 
				{
					negative = true;
				}				
			}
			checkEOF();
			long res = 0;
			for (; c >= '0' && c <= '9'; c = nextChar()) 
			{
				res = (res << 3) + (res << 1) + c - '0';
			}
			return negative ? -res : res;
		}

	    public char nextChar() 
	    {
			if (EOF_FLAG) 
			{
				return NULL_CHAR;
			}
			while (bufferIdx == size) 
			{
				try 
				{
					size = in.read(buffer);
					if (size == -1) 
					{
						throw new Exception();
					}
				} 
				catch (Exception e) 
				{
					EOF_FLAG = true;
					return NULL_CHAR;
				}
				if (size == -1) 
				{
					size = BUFFER_SIZE;
				}
				bufferIdx = 0;
			}
			return (char) buffer[bufferIdx++];
		}

	    public void checkEOF() 
	    {
			if (EOF_FLAG) 
			{
				throw new EndOfFileException();
			}
		}
	    public void close()
	    {
	    	;
	    }
		public class EndOfFileException extends RuntimeException 
		{
		}
	}
	class FastScanner 
	{
		final BufferedReader reader;
		String line;
		int index;
		public FastScanner(InputStream in)
		{
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public String readLine()
		{
			try
			{
				String line = reader.readLine();
				if(line == null) throw new IOException("End of stream");
				return line;
			}
			catch(IOException exception)
			{
				throw new RuntimeException(exception);
			}
		}
		public String nextLine()
		{
			if(line==null) return readLine();
			String s = line;
			line = null;
			return s.substring(index);
		}
		public String next()
		{
			if(line == null)
			{
				line = readLine();
				index = 0;
			}
			while(index >= line.length())
			{
				line = readLine();
				index = 0;
			}
			while(Character.isWhitespace(line.charAt(index)))
			{
				index++;
				while(index >= line.length())
				{
					line = readLine();
					index = 0;
				}
			}
			int endIndex = index;
			while(endIndex < line.length() && !Character.isWhitespace(line.charAt(endIndex)))
				endIndex++;
			String s = line.substring(index, endIndex);
			index = endIndex;
			return s;
		}
		public int nextInt() { return Integer.parseInt(next()); }
		public long nextLong() { return Long.parseLong(next()); }
		public double nextDouble() { return Double.parseDouble(next()); }
		public void close() {;}
	}
}
