Sail Shreds - 3

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. In fact, they have to respect the orientations of the shreds, since otherwise the sail would be less resistant to wind and might be torn again. They were trying to find the original arrangement for several hours but with no result. They think that a computer can help them and asked you for help.

You are given the description of the triangular shreds (given by the plane coordinates of the vertices of each triangle) 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 should be moved in such a way that

• the whole rectangular area is covered,
• no two triangles intersect, i.e., there is no point which is contained in the interiors of two different triangles, and
• there is no triangle whose part lies outside of the rectangle.

You may assume that there exists a solution for each of the input data. In particular, it holds that the sum of the areas of the shreds is equal to the area of the original sail. There can be several shreds of 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 ≤ X, Y ≤ 1 000 000. N is the number of triangular shreds, with 2 ≤ N ≤ 1 000.

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 give the vertices A_i, B_i, and C_i of the i-th triangle, where A_i has coordinates (A_{i,x}, A_{i,y}), and so on. All coordinates satisfy 0 ≤ coordinate ≤ 1 000 000.

The position of a triangle in the input does not matter. Only its shape is used.

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. The lower left corner of the sail is at (0, 0) and the upper right corner is at (X, Y).