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.
import sys
input = sys.stdin.buffer.readline 

def process(A):
    n = len(A)
    A2 = []
    m = 0
    for i in range(n):
        x, y = A[i]
        m = max(x, y, m)
        A2.append([i+1, x, y])
    A2 = sorted(A2, key=lambda a:(min(a[1], a[2], m-a[1], m-a[2]), a[1], a[2]))
    dist = 0
    answer = []
    for i in range(n-1):
        t1, a1, a2 = A2[i]
        t2, b1, b2 = A2[i+1]
        answer.append(t1)
        dist = dist+abs(b1-a1)+abs(b2-a2)
    answer.append(A2[-1][0])
    return answer
    
    
    
n = int(input())
A= []
for i in range(n):
    x, y = [int(x) for x in input().split()]
    A.append([x, y])
answer = process(A)
sys.stdout.write(' '.join(map(str, answer))+'\n')