Sail Shreds 4

During the recent two-day storm, a group of sailors shipwrecked on a desert island in the Mediterranean sea. Since their radio is broken, they cannot call for help and their only chance of survival is escaping on a raft. However, they need a sail to power the raft. Luckily, they recovered the main sail from the wrecked ship, but it is torn to several shreds. Hence, they have to sew the shreds together to obtain the original sail.

The sailors quickly realized that each of the shreds is a triangle. Because there were stripes on the sail, it was easy to identify the correct orientation of its triangular parts. The shreds must keep their orientations. Otherwise the sail would be less resistant to wind and might be torn again. They spent several hours looking for the original arrangement without success. They think a computer can help, so they asked you.

You are given the plane coordinates of the vertices of each triangular shred and the dimensions of the original sail, which was a rectangle given by two integers $X$ and $Y$. Your task is to move the shreds (without rotation) to reconstruct the original sail (see the figure). In particular, the triangles must be moved so that:

• the whole rectangular area is covered,
• no two triangles intersect, that is, no point lies in the interiors of two different triangles, and
• no triangle has any part outside the rectangle.

You may assume that a solution exists for each input. In particular, the sum of the areas of the shreds equals the area of the original 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 original sail, with $1 \le X, Y \le 1000000$. $N$ is the number of triangular shreds, with $2 \le N \le 1000$.

The next $N$ lines describe the triangles. The $(i+1)$-th line 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 describe the three vertices $A_i$, $B_i$, and $C_i$ of the $i$-th triangle, where $A_i$ is at $(A_{i,x}, A_{i,y})$, $B_i$ is at $(B_{i,x}, B_{i,y})$, and $C_i$ is at $(C_{i,x}, C_{i,y})$. All coordinates satisfy $0 \le$ coordinate $\le 1000000$.

The position of a triangle in the input is irrelevant. Translating a triangle to another position gives the same set of shreds.

Output exactly $N$ lines. The $i$-th line contains two integers $A^*_{i,x}$ and $A^*_{i,y}$, separated by a single space. These are the coordinates of the point $A_i$ after the $i$-th shred is moved to its place. All three conditions in the problem must hold. The lower left corner of the sail is at $(0, 0)$ and the upper right corner is at $(X, Y)$, as shown in the figure.