Sail Shreds - 8

During the recent 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. They recovered the main sail from the wrecked ship, but it is torn into several shreds. They have to sew the shreds together to rebuild the original sail.

The sailors quickly realized that each shred is a triangle. The sail had stripes, so it was easy to identify the correct orientation of each triangular part. They must respect these orientations. Otherwise the sail would be less resistant to wind and might tear again. They spent several hours looking for the original arrangement without success. They think a computer can help, and they asked you for help.

You are given the triangular shreds by the plane coordinates of their vertices, and the dimensions of the original sail, which was a rectangle with integers X and Y. Move the shreds (without rotation) to rebuild the original sail, 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 part of any triangle lies outside the rectangle.

You may assume a solution exists for every 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 and Y (1 ≤ X, Y ≤ 1 000 000) are the width and height of the original sail, and N (2 ≤ N ≤ 1 000) is the number of triangular shreds.

The next N lines describe the triangles. Line i + 1 contains six integers Ai,x, Ai,y, Bi,x, Bi,y, Ci,x, and Ci,y, separated by single spaces. They give the three vertices Ai, Bi, and Ci of the i-th triangle, where Ai has coordinates (Ai,x, Ai,y), Bi has (Bi,x, Bi,y), and Ci has (Ci,x, Ci,y). All coordinates satisfy 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 sample input were replaced with 6 6 14 5 16 6, the set of shreds would be the same.

Print exactly N lines. The i-th line contains two integers A*i,x and A*i,y, separated by a single space, which are the coordinates of the point Ai after you move the i-th shred to its 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.