Partition

Time Limit: 5 Seconds    Memory Limit: 32768 KB
Special Judge

The Ents are known as the shepherds of the forest. Treebeard, the oldest living Ent in Middle Earth, needs to determine which trees he is to shepherd and which trees are to be shepherded by his young fellow Ent, Bregalad. They have a rectangular portion of Fangorn forest containing an even number of trees that they need to divide into two pieces using a single straight boundary line. In order to equitably distribute the workload, Treebeard and Bregalad have decided that each of their halves of the forest need to contain equal area and contain an equal number of trees. If a tree lies exactly on the dividing line, then that tree is counted in one or the other of the halves of the forest but not both. Any tree exactly on the dividing line may be assigned to either Treebeard or Bregalad.

 

Input

Input will consist of multiple test cases. Each test case begins with a line with 3 space-separated integers N, W, and H, denoting the number of trees, the width of the forest, and the height of the forest, respectively. The forest's four corners are (0, 0), (W, 0), (0,H), and (W,H). Following this line are N lines each with a pair of space-separated integers xi and yi denoting the coordinates of the ith tree. Furthermore,

• 2 <= N <= 50000, 2 <= W <= 10000, 2 <= H <= 10000, N is even, W and H are not both even.
• 0 < xi < W, 0 < yi < H for all i. All locations of trees are distinct.
• Input will be terminated with a case where N = W = H = 0, which should not be processed.

Output

For each test case, print out N=2 lines. On each line, print two space-separated integers xi and yi, denoting the coordinates of the ith tree in the half of the forest that is to be shepherded by Treebeard.

Sample Input

2 5 6
2 3
3 3
4 5 6
1 5
2 5
3 5
4 5
4 10 11
5 1
5 2
5 3
5 4
0 0 0

Sample Output

3 3
1 5
2 5
5 1
5 2

Submit

Source: Pacific Northwest 2012