Point Travel

Problem Statement

You are given $n$ integer coordinates in a two dimensional plane.

Determine a path (going from point to point) which has a total Manhattan distance travelled of less than $3 \cdot 10^9$.

NOTE: The Manhattan distance of $(x, y)$ to $(p, q)$ is $|x - p| + |y - q|$.

Input Statement

Your first line will contain $n$. Your next $n$ lines will contain two space-separated integers each $x$ and $y$ representing the point $(x, y)$ on the two dimensional plane.

Output Statement

You should output $n$ points, containing each of the points you have been given, in the order of the path that you will take.

Constraints

• $1 \leq n \leq 10^6$
• $0 \leq x, y \leq 10^6$

Sample Cases

6
0 0
0 1000000
1 1000000
1000000 0
1000000 1000000
1000000 1000000

1 1000000
0 0
1000000 1000000
0 1000000
1000000 1000000
1000000 0

Explanation 1

To be honest, the sample cases won't really help, but they are here anyway. Notice any path you take in this case will have total distance travelled less than $3 \cdot 10^9$. Notice there are repeated coordinates and