There are $n$ integer points $(x, y, z)$ on a 3D coordinate system. Sort them in ascending order by $x$, then by $y$ (if points have the same value of $x$), and then by $z$ (if points have the same value of $x$ and $y$).

Input

• The first line contains an integer $n$.
• Each line in the next $n$ lines contains 3 integers $x, y, z$.

Output

• Print $n$ points after sorting.

Constraints

• $1 \le n \le 100000$.
• $1 \le x, y, z \le 10^9$.

Example

Input:

3
3 4 3
2 4 3
2 1 6

Output:

2 1 6
2 4 3
3 4 3