Description

Changzhou Senior High School of Jiangsu is a century-old prestigious school, filled with countless unforgettable memories.

Will remembers that when he was little, before the school's reconstruction, there was a tall metasequoia grove. When the metasequoias shed their leaves, the needles would cover the ground like a blanket, making it romantic and leisurely to walk on. Back then, Will and his classmates liked to use these needles to play a “taking needles” game under the metasequoias.

At the start of the game, everyone lays $n$ needles flat on the ground. Then, in each round, one player may choose one needle and move it in the horizontal or vertical direction (that is, translate it to infinity) — provided that during the movement it is not blocked by any needle that has not yet been moved away. If a needle’s movement would be blocked in a round, then this move is illegal and not allowed.

After $n$ rounds, when all needles have been removed, the game ends. Not every needle can be moved at any time. When there are many needles, determining in each round whether a specific needle can be moved in a given direction is troublesome. Now we abstract the ground as a 2D Cartesian plane, the $n$ needles as $n$ pairwise disjoint line segments in the plane, labeled from $1$ to $n$. Will also provides, for each round, the index of the needle he wants to move and the direction. Please help him:

1. Find in which round the earliest illegal move occurs.
2. Provide a legal move sequence that completes the game.

Note: When moving segments, merely touching at endpoints does not cause obstruction. See the sample for details.

Input Format

The first line contains a positive integer $n$, the number of needles.

The next $n$ lines each contain $4$ integers describing the positions of the needles. On the $i$-th of these lines, the integers $a_i$, $b_i$, $c_i$, $d_i$ indicate that the endpoints of the line segment abstracting needle $i$ are $(a_i, b_i)$ and $(c_i, d_i)$.

The next $n$ lines each contain $2$ integers describing the moves. On the $i$-th of these lines, the integers $p_i$, $q_i$ indicate that in round $i$, the needle to move is $p_i$, and the direction is $q_i$. Here $q_i$ is an integer between $0$ and $3$: $0$ means move left (the negative $x$-axis direction), $1$ means move up (the positive $y$-axis direction), $2$ means move right, and $3$ means move down.

The input is guaranteed that:

• All segments have positive length, no two segments share a point, and there are no vertical or horizontal segments.
• $p_1$ through $p_n$ form a permutation of $1$ through $n$.
• There is at least one illegal move in Will’s given sequence.
• There always exists a sequence of $n$ legal moves that completes the game.

Output Format

The output contains $n+1$ lines.

The first line contains an integer between $1$ and $n$, indicating the earliest round in which an illegal move occurs.

The next $n$ lines each contain two integers, as in the input format, describing a legal move sequence.

5 
2 5 5 8 
2 1 3 5 
5 2 6 5 
7 0 4 2 
3 1 4 0 
2 0 
3 0 
4 0 
1 2 
5 1 

3 
2 0 
3 0 
4 3 
1 2 
5 1 

4
-1 1 2 3
13 5 9 8
10 10 15 14
10 17 0 20
3 1
2 1
1 1

4 1

2
4 1
3 1
2 1
1 1

Hint

[Sample explanation]

In round $3$ of Will’s given plan, moving needle $4$ to the left is blocked by needle $5$.

[Constraints]

See the table below.

For a test point:

• If the illegal move detection is correct but the provided plan is wrong, you can get $5$ points. The message will be: An invalid move in step.
• If the illegal move detection is wrong but the provided plan is correct, you can get $5$ points. The message will be: Negative error detection!.
• If both the detection and the plan are correct, you get $10$ points; otherwise, $0$ points.

If the program’s output format is incorrect, it will be directly judged as $0$ points.

Translated by ChatGPT 5