Sorting Points by Coordinates

Interview

Time limit1sMemory limit256 MB

Summary

Sort N planar points by increasing x coordinate, breaking ties by increasing y, and print them in order.

Level: Easy3 of 10
Topics: Sorting
Solved: No attempts yet

Problem

You are given $N$ points on a two-dimensional plane. Write a program that sorts the points by increasing $x$ coordinate, and by increasing $y$ coordinate when the $x$ coordinates are equal, then prints them.

Input

The first line contains the number of points $N$ ( $1 \le N \le 100{,}000$ ). Each of the next $N$ lines contains the coordinates $x_i$ and $y_i$ of the $i$ -th point, separated by a space ( $-100{,}000 \le x_i, y_i \le 100{,}000$ ). All coordinates are integers, and no two points share the same position.

Output

Print the sorted points on $N$ lines, one point per line. On each line print the $x$ coordinate and the $y$ coordinate separated by a space.

Examples4

Example 1

Input

Expected output

Example 2
Input
```
1
0 0
```
Expected output
```
0 0
```
Example 3
Input
```
2
1 5
1 -5
```
Expected output
```
1 -5
1 5
```

Example 4

Input

4
-100000 -100000
100000 100000
-100000 100000
100000 -100000

Expected output

-100000 -100000
-100000 100000
100000 -100000
100000 100000