Sail Shreds - 5

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

The sailors quickly saw that each shred is a triangle. The sail has stripes, so the correct orientation of each triangular part is easy to identify. The shreds must keep their orientations. Otherwise the sail would resist wind less and could tear again. The sailors spent several hours looking for the original arrangement without success. They believe a computer can help, so they asked you.

You are given the vertex coordinates of each triangular shred and the dimensions of the original sail, a rectangle with width X and height Y. Move the shreds without rotating them to rebuild the sail. In particular:

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

You may assume that a solution exists for every input. In particular, the total area of the shreds equals the area of the original sail. Several shreds can have the same shape.

Each input file describes a single test case with the following structure. The first line contains three integers N, X, and Y, separated by single spaces. X and Y (1 ≤ X, Y ≤ 1 000 000) are the dimensions of the original sail, with X as the width and Y as the height. N (2 ≤ N ≤ 1 000) is the number of triangular shreds.

The next N lines describe the triangles. The (i + 1)-th line contains six integers Ai,x, Ai,y, Bi,x, Bi,y, Ci,x, and Ci,y, separated by single spaces. These give the three vertices Ai, Bi, and Ci of the i-th triangle. Vertex Ai has coordinates (Ai,x, Ai,y), Bi has (Bi,x, Bi,y), and Ci has (Ci,x, Ci,y). You may assume that 0 ≤ Ai,x, Ai,y, Bi,x, Bi,y, Ci,x, Ci,y ≤ 1 000 000.

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

The output must consist of exactly N lines that describe an arrangement of the shreds satisfying all three conditions. 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 Ai after the i-th shred is moved into place. The bottom left corner of the sail is always at (0, 0), and the top right corner is at (X, Y), as shown in the figure.