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

Input 1

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

Output 1

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