Sail Shreds - 1

A two-day storm wrecked a group of sailors on a desert island in the Mediterranean Sea. Their radio is broken, so they cannot call for help. Their only chance of survival is to escape on a raft, and the raft needs a sail. They recovered the main sail from the wrecked ship, but it is torn into several shreds. They must sew the shreds together to restore the original sail.

Each shred is a triangle. Stripes on the sail make the correct orientation of each triangle easy to see. The orientations must be kept, because otherwise the sail resists wind poorly and may tear again. The sailors spent several hours searching for the original arrangement without success. They ask you to help them with a computer.

Given the vertices of the triangular shreds and the size of the rectangular sail, move the shreds to rebuild the sail. You may translate each shred but must not rotate it. The arrangement must satisfy these conditions:

• The whole rectangle is covered.
• No two triangles overlap. No point lies in the interiors of two different triangles.
• No part of any triangle lies outside the rectangle.

You may assume a solution exists for every input. The total area of the shreds equals the area of the sail. Several shreds may have the same shape.

The first line contains three integers N, X, and Y separated by single spaces. X is the width and Y is the height of the sail, with $1 \le X, Y \le 1\,000\,000$. N is the number of shreds, with $2 \le N \le 1\,000$.

The next N lines describe the triangles. Line i+1 contains six integers $A_{i,x}$, $A_{i,y}$, $B_{i,x}$, $B_{i,y}$, $C_{i,x}$, and $C_{i,y}$ separated by single spaces. These give the vertices $A_i$, $B_i$, and $C_i$ of the i-th triangle. Every coordinate satisfies $0 \le$ coordinate $\le 1\,000\,000$.

The position of a triangle in the input does not matter. For example, if the third line of the example input were replaced with 6 6 14 5 16 6, the set of shreds would be the same.

Output exactly N lines. The i-th line contains two integers $A^*_{i,x}$ and $A^*_{i,y}$ separated by a space. These are the coordinates of the point $A_i$ after the i-th shred is moved into place. The lower left corner of the sail is at (0, 0), and the upper right corner is at (X, Y).