Fangorn Forest

Ents are the guardians of the forest. Treebeard, the oldest Ent in Middle-earth, wants to decide which trees he will protect and which trees his younger fellow Ent, Bregalad, will protect.

The forest they guard is a rectangle, and it contains an even number of trees. Treebeard will draw a single straight line that splits the forest into two regions, keeping one for himself and giving the other to Bregalad. If the two regions differ in the number of trees or in area, the two Ents will quarrel for tens of thousands of years, so the split must be fair in both respects: each region must contain the same number of trees (exactly $N/2$ each) and have the same area.

A tree lying exactly on the boundary line may be assigned to either region, but not to both.

The input consists of several test cases. The first line of each test case contains the number of trees $N$, the forest width $W$, and the forest height $H$. The four corners of the forest are $(0,0)$, $(W,0)$, $(0,H)$, and $(W,H)$. Each of the next $N$ lines contains a tree's coordinates $x\ y$.

• $2 \le N \le 500000$, and $N$ is even
• $2 \le W, H \le 10000$, and $W$ and $H$ are never both even
• All coordinates are integers with $0 < x < W$ and $0 < y < H$
• No two trees share the same position

Input ends with a line $N = W = H = 0$, which must not be processed.

Because several fair divisions may exist, output the one determined uniquely by the following rule.

The boundary line always passes through the center of the forest, $\left(\tfrac{W}{2},\ \tfrac{H}{2}\right)$ (any line through the center splits the rectangle into two equal areas). Require the line to pass through the center and through at least one tree. Give the line a direction, and let Treebeard's region be the trees strictly to its left, where 'left' means the side reached by turning $90°$ counterclockwise from the line's direction. Trees lying exactly on the line are added to Treebeard's region in increasing order of $(x, y)$ until his region holds exactly $N/2$ trees.

If several directed lines through the center and at least one tree admit such a split (each side $N/2$), choose the one whose direction angle, measured counterclockwise from the positive $x$-axis in $[0°, 360°)$, is smallest.

For each test case, output the $N/2$ trees of Treebeard's region, sorted by increasing $x$ and then by increasing $y$, one per line in the format x y.