Given N points on a 2D plane, please sort these points. Two points are compared by the following rules:
1. If the x coordinates are different, the point with the smaller x coordinate wins.
2. If the x coordinate are the same, then point with the smaller y coordinate wins.
The winner point should output before loser point!
Input will ensure that no two points are at the same position.
Input begins with an integer T, the number of test cases. Each test case would be in the following format.
Line 1: An integers: N, means the number of 2D point.
The following are N lines.
Line i (2<=i<=N+1): Two integers: x y, separated by a blank, indicating the x and y coordinate of ith point.
limits :
subtask 1 : (when you pass this subtask, you can get 20 point)
1 <= N <= 1000
0 <= x,y <= 1000000
Using O(N^2) sorting algorithm is okay!
subtask 2 : (when you pass this subtask, you can get another 20 point)
1 <= N <= 100000
0 <= x,y <= 1000000
You have to use O(NlogN) sorting algorithm!
For each test case outputs N lines, the sorting result.