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.
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
struct modui{
    int l,r,id;
}s[N];
int n,pos[N];
bool cmp(modui x,modui y){
	if (pos[x.l]!=pos[y.l]) return x.l<y.l;
    if(pos[x.l]&1) return x.r<y.r;
	return x.r>y.r;
}
int main(){
	cin>>n;
	int dis=sqrt(n);
    
    for(int i=1;i<=n;i++) pos[i]=i/dis;
	for(int i=1;i<=n;i++){
		scanf("%d %d",&s[i].l,&s[i].r);
		s[i].id=i;
	}
	sort(s+1,s+1+n,cmp);
	for(int i=1;i<=n;i++)  printf("%d ",s[i].id);
	return 0;
}
   				  			 	 	 		   	 	  		