Đường đi Hamilton Manhattan

Trên mặt phẳng có $n$ điểm với tọa độ nguyên $(x_i,y_i)$, trong đó $0\le x_i,y_i\le {10}^6$. Khoảng cách giữa hai điểm $a$ và $b$ được tính theo khoảng cách Manhattan:

$$d(a,b)=|x_a-x_b|+|y_a-y_b|$$

Một đường đi Hamilton là một hoán vị $p_1,p_2,\dots ,p_n$ của các số $1,2,\dots ,n$. Độ dài của đường đi này được định nghĩa là:

$$L=\sum _{i=1}^{n-1}d(p_i,p_{i+1})$$

Hãy tìm một đường đi Hamilton có độ dài không vượt quá $25·{10}^8$. Lưu ý rằng bạn không cần tối thiểu hoá độ dài. Bài toán đảm bảo luôn tồn tại đáp án thỏa mãn.

Nếu có nhiều đáp án thỏa mãn, in ra đáp án bất kỳ.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ $i+1$ chứa hai số nguyên $x_i$ và $y_i$ — tọa độ của điểm thứ $i$.

Bảo đảm không có hai điểm nào trùng nhau.

Dữ liệu ra

In ra hoán vị $p_1,p_2,\dots ,p_n$ — đường đi Hamilton thỏa mãn $L\le 25·{10}^8$.

Ràng buộc

• $1\le n\le {10}^6$
• $0\le x_i,y_i\le {10}^6$

Ví dụ