Sorting Coordinates 2

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

Easy3SortingInterviewNo attempts yetTime limit1sMemory limit256 MB

Problem

You are given NN points on a two dimensional plane. Write a program that sorts the points by increasing yy coordinate, breaking ties by increasing xx coordinate, and prints the sorted points.

Input

The first line contains the number of points NN (1N1000001 \le N \le 100000). Each of the next NN lines contains the coordinates xix_i and yiy_i of the ii-th point, separated by a space (100000xi,yi100000-100000 \le x_i, y_i \le 100000). All coordinates are integers, and no two points share the same position.

Output

Print the sorted points on NN lines, one point per line. On each line print the xx coordinate and the yy coordinate of that point, separated by a single space.