Partition#6977
The Forest Guardians are known as the protectors of the woods. Oakbeard, the eldest of the Guardians, must decide which trees he will watch over and which ones will be overseen by his younger companion, Birchleaf. They are given a rectangular section of the forest, containing an even number of trees, which they must split into two parts using a straight line.
To ensure a fair division of work, Oakbeard and Birchleaf agree that each half of the forest must cover equal area and contain an equal number of trees. If a tree is exactly on the dividing line, it may be assigned to either Oakbeard or Birchleaf, but not both.
Input consists of multiple test cases. Each case begins with a line containing space-separated integers: , , and , representing the number of trees, the width, and the height of the forest. The four corners of the forest are at , , , and (W, H). This is followed by lines, each with two integers: x_i and y_i, the coordinates of the -th tree. Furthermore,
2 \le N \le 50000, 2 \le W \le 10000, 2 \le H \le 10000, is even, and are not both even.
0 < x_i < W, 0 < y_i < H for all ; all tree locations are unique.
Input ends with a case where N = W = H = 0, which should not be processed.
For each test case, print lines. Each line should contain two space-separated integers x_i and y_i: the coordinates of a tree in Oakbeard's half of the forest.
Example 1