Hide

Problem D
MC Part Deux

/problems/mcpartdeux/file/statement/en/img-0001.jpg
The Dean has determined that mathies have outgrown the building that has served them so well for many years. Luckily for him, the PM has decided to stimulate the economy by funding a new math building. To maximize the stimulating effect, the construction process is outsourced to a software engineering consultant who employs agile methodologies. The building will be built first, and designed later. The Dean has some concerns about this innovative process. After all, it would be very embarrassing if the walls of the new math building failed to line up at right angles!

The Dean sneaks out one night with a tape measure to survey the last remaining grassy area on campus, where the new building will go. He drives stakes into the ground, then measures the distances between them. Afterwards, he retreats into his office to construct a map from his measurements. He notices that the first three stakes form a right-angled triangle with arms of length one metre and hypotenuse of length $\sqrt {2}$ metres. And that’s not all. The Dean plots these first three stakes on a piece of graph paper at coordinates $(0,0)$, $(0,1)$, and $(1,0)$. After plotting some of the other stakes, it turns out that all of the stakes happen to be precisely at lattice points (i.e., points with integer coordinates) on the graph paper. Still, plotting all of the many stakes is tedious, so he asks his co-op student (i.e. you) to help out.

Input

The first line of input contains two integers $n$ and $m$, each at least $1$ and no larger than $1000$.

The integer $n$ is the number of lines that follow, and $m$ is the number of stakes. The stakes are numbered from $1$ to $m$. All of the stakes are at distinct locations. The $x$ and $y$ coordinates of each stake are no less than $-1\, 000\, 000$ and no greater than $1\, 000\, 000$.

Each of the following $n$ lines contains exactly six integers $a$, $b$, $c$, $x$, $y$, $z$. The integers $a$, $b$, and $c$ are the numbers of three distinct stakes. The three stakes are always listed in counter-clockwise order. That is, to move from stake $a$ to stake $b$ and then to stake $c$, one must turn left at stake $b$. The number $x$ is the square of the distance from stake $a$ to stake $b$. The number $y$ is the square of the distance from stake $b$ to stake $c$. The number $z$ is the square of the distance from stake $c$ to stake $a$.

Every stake will appear in at least one line of the input. For every pair of stakes $a$, $b$, there is a subset of the triangles in the input that forms a sequence $T_{1}, T_{2}, \ldots , T_{k}$ such that two of the vertices of $T_{i}$ are also vertices of $T_{i+1}$for all $1 \le i < k$, $a$ is a vertex of $T_{1}$, and $b$ is a vertex of $T_{n}$.

Output

Output consists of exactly $m$ lines. The $m$ lines describe the stakes $1$ to $m$ in sequence. Each line contains two integers, giving the $x$ and $y$ coordinates of the stake. The first three lines of output for each test case are always:

0 0
0 1
1 0
Sample Input 1 Sample Output 1
1 3
1 3 2 1 2 1
0 0
0 1
1 0

Please log in to submit a solution to this problem

Log in