On a plane are *n* points (*x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub>) with integer coordinates between 0 and 10<sup class="upper-index">6</sup>. The distance between the two points with numbers *a* and *b* is said to be the following value: <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/03274f8c977ad3feb5d9f6ede91c69bcaef04972.png" style="max-width: 100.0%;max-height: 100.0%;"/> (the distance calculated by such formula is called Manhattan distance).

We call a hamiltonian path to be some permutation *p*<sub class="lower-index">*i*</sub> of numbers from 1 to *n*. We say that the length of this path is value <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/2872e932e7cab8f5f7a9c718441f7534261ed638.png" style="max-width: 100.0%;max-height: 100.0%;"/>.

Find some hamiltonian path with a length of no more than 25 × 10<sup class="upper-index">8</sup>. Note that you do not have to minimize the path length.
The first line contains integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">6</sup>).

The *i* + 1-th line contains the coordinates of the *i*-th point: *x*<sub class="lower-index">*i*</sub> and *y*<sub class="lower-index">*i*</sub> (0 ≤ *x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>).

It is guaranteed that no two points coincide.
package main

import (
	"bufio"
	. "fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	type pair struct{ x, y int }

	var n int
	Fscan(in, &n)
	g := [1001][1001][]int{}
	ps := make([]pair, n+1)
	for i := 1; i <= n; i++ {
		Fscan(in, &ps[i].x, &ps[i].y)
		x, y := ps[i].x/1000, ps[i].y/1000
		if x&1 > 0 {
			y = 1000 - y
		}
		g[x][y] = append(g[x][y], i)
	}
	for i := 0; i < 1001; i++ {
		for j := 0; j < 1001; j++ {
			ids := g[i][j]
			if len(ids) == 0 {
				continue
			}
			minI, maxI := ids[0], ids[0]
			for _, id := range ids[1:] {
				if ps[id].x < ps[minI].x {
					minI = id
				} else if ps[id].x > ps[maxI].x {
					maxI = id
				}
			}
			if i&1 > 0 {
				minI, maxI = maxI, minI
			}
			Fprint(out, minI, " ")
			for _, id := range ids {
				if id != minI && id != maxI {
					Fprint(out, id, " ")
				}
			}
			if maxI != minI {
				Fprint(out, maxI, " ")
			}
		}
	}
}
  		 			    	 			 	 		 	 	 	  	