You are given $N$ points $(x, y)$ on a 2D coordinate plane. Sort them in ascending order of their Manhattan distance from the origin ($|x| + |y|$). If two points have the same Manhattan distance from the origin, output the one with smaller x-coordinate first; if they are still tied for x-coordinate, output the one with smaller y-coordinate first.

Input

The first line of input contains an integer $N$.
Each of next $N$ lines contain the $x$ and $y$ coordinates of a point.

Output

Output the points in the required order.

Constraints

For all subtasks: $1 \le N \le 10^5$
Subtask 1 (90%): $-1000 \le x, y \le 1000$
Subtask 2 (10%): $-10^6 \le x, y \le 10^6$