The Metasequoia Trees in Memory

In the past, there was a tall forest of metasequoia trees at the high school. Every time the metasequoia leaves fell, the needle-shaped leaves would cover the ground like a carpet, making walks romantic and leisurely. At that time, Will and his classmates loved to play a "leaf-picking" game under the trees.

At the start of the game, $n$ needle-shaped leaves are laid out on the ground. In each round, a student can choose one leaf and move it horizontally or vertically away (to infinity). However, this is only allowed if the leaf is not obstructed by any other leaves that have not yet been removed during the movement. If the movement of a leaf in a given round is obstructed, that move is illegal and not permitted. After $n$ rounds, all leaves are removed, and the game ends.

Leaves cannot be moved at any time. When there are many leaves, it is troublesome to determine whether a leaf can be moved in a specific direction in each round.

We now model the ground as a Cartesian coordinate system and the $n$ leaves as $n$ non-intersecting line segments on the plane, numbered from $1$ to $n$. Will provides the leaf number and the direction of movement for each round of the game. Please help him:

1) Identify the round in which the first illegal move occurs. 2) Provide a valid sequence of moves to complete the game.

Note: When a line segment moves, contact only at the endpoints does not cause an obstruction. Please refer to the examples for details.

Input

The first line of the input file contains a positive integer $n$, representing the number of leaves. The next $n$ lines each contain 4 integers, describing the position of the leaves. The $i$-th line contains $a_i, b_i, c_i, d_i$, representing the endpoints $(a_i, b_i)$ and $(c_i, d_i)$ of the line segment representing leaf $i$. The next $n$ lines each contain 2 integers, describing the moves. The $i$-th line contains $p_i, q_i$, representing that in the $i$-th round, the leaf with number $p_i$ is moved in direction $q_i$. Here, $q_i$ is an integer between $0$ and $3$: $0$ represents moving left (negative $x$-axis direction), $1$ represents moving up (positive $y$-axis direction), $2$ represents moving right (positive $x$-axis direction), and $3$ represents moving down (negative $y$-axis direction).

Input guarantees: All line segments have positive length, no two segments have common points, and there are no vertical or horizontal line segments. $p_1$ to $p_n$ form a permutation of $1$ to $n$. There is at least one illegal move in the sequence provided by Will. A valid sequence of $n$ moves always exists.

Output

The output file contains $n + 1$ lines. The first line contains an integer between $1$ and $n$, representing the round in which the first illegal move occurs. The next $n$ lines each contain two integers, in the same format as the input, describing a valid sequence of moves.

Subtasks

For each test case: If the illegal move is identified correctly, but the provided sequence is incorrect, you get 5 points. If the illegal move is identified incorrectly, but the provided sequence is correct, you get 5 points. If both the identification of the illegal move and the provided sequence are correct, you get 10 points. Otherwise, you get 0 points.

Note: If the output format of the program is incorrect, it will be judged as 0 points.

Examples

Input 1

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

Output 1

3
2 0
3 0
4 3
1 2
5 1

Note 1

In the 3rd round of the move sequence provided by Will, the movement of leaf 4 to the left is obstructed by leaf 5.

Input 2

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

Output 2

2
4 1
3 1
2 1
1 1

Constraints

(Note: For test cases 7-10, $1 \le i \le n$, $0 \le q_i \le 3$, and $|a_i|, |b_i|, |c_i|, |d_i| \le 10^9$)