Problem Statement

KYOPRO City is a square-shaped city with $14$ rows and $14$ columns.
The block in the $i$-th row from the north and the $j$-th column from the west is numbered $(i, j)$, and blocks adjacent to the east, west, south, or north are connected by roads.
In other words, the structure of KYOPRO City is as shown in the figure below.

Also, $N$ citizens live in KYOPRO City, numbered from $1$ to $N$.
The home of citizen $k$ is in block $(A_k, B_k)$, and their company is in block $(C_k, D_k)$.

Initially, all roads built in KYOPRO City are ordinary roads, and it takes $1$ minute to travel along one road.
So the mayor, Taro, decided to shorten travel times by upgrading some roads to highways (which can be traveled in $0.223$ minutes).

Specifically, over the remaining $T$ days of his term, he performs the following actions in order each day.
Initially, he has $10^6$ yen in funds and $1$ collaborator.

Taro's true goal is neither to make the city more convenient nor to make its finances healthy, but to make money, so he wants to have as much money as possible in the end.
Output Taro's actions so that his final amount of money is as large as possible.

Notes

There may be various routes that each citizen could take in step 2.,
but note that under the constraints of this problem, the number of highways traveled on a shortest-time route is unique.

For example, when the yellow roads in the image below are highways, there are $2$ ways to travel from S to T in the shortest time ($4.338$ minutes),
but both of them use $6$ highways.

Input and Output

This is an interactive problem. Note that the input and output format differs from that of ordinary problems.

First, your program must receive $N+1$ lines of input in the following format.

$N$ $T$
$A_1$ $B_1$ $C_1$ $D_1$
$A_2$ $B_2$ $C_2$ $D_2$
 $:$
$A_N$ $B_N$ $C_N$ $D_N$

Next, repeat (a) and (b), in that order, $T$ times.

$u$ $v$

$1$ $x$ $y$ $z$ $w$

$2$

$3$

Constraints

• $N=3000$
• $T=400$
• $1 \leqq A_k, B_k, C_k, D_k \leqq 14$ ($1 \leqq k \leqq N$)
• Note that $(A_k, B_k) = (C_k, D_k)$ may hold

Scoring

Taro's final amount of money is directly your score. For example, if the final amount of money is $5$ hundred million yen, you get $5$ hundred million points.
However, if your output is invalid, it is judged as WA. Invalid output means any of the following.

• The output does not follow the output format
• A highway is built without sufficient funds
• An attempt is made to build a highway connecting block $(x, y)$ and block $(z, w)$, but $|x-z| + |y-w| = 1$ is not satisfied
• An attempt is made to build a highway connecting block $(x, y)$ and block $(z, w)$, but $1 \leqq x, y, z, w \leqq 14$ is not satisfied

If your program produces invalid output at some point, it will receive the input -1 -1 in (a) of the Input and Output section on the next turn, so terminate the program immediately.
If the program does not terminate, the judging result may be another error such as TLE or RE.
Note that attempting to build a highway where one has already been built is not judged as incorrect, but it is wasteful.

There are $50$ test cases in total, and the sum of the scores over all test cases is the score of a submission.
The final ranking is determined by the highest score obtained during the contest, and no system test is performed after the contest ends.

Sample Code / Hints

Heuristic beginners are recommended to read this section.

First, for those who are not familiar with interactive problems, sample code in C++ and Python is given below.
This program raises funds on every day.

• C++: Sample code
• Python: Sample code

Also, note that in this problem you receive the "current funds" and the "current number of collaborators" as input,
so you do not necessarily need to compute the "amount of highway revenue" yourself.

Test Case Generation

Note that this section is not essential for understanding the problem.

Test cases are generated by the following method.

1. For each $(p, q)$ ($1 \leqq p \leqq 14, 1 \leqq q \leqq 14$), generate a random number $e_{p, q}$ with mean $0$ and standard deviation $1$
2. For each $k$ ($1 \leqq k \leqq N$), generate $(A_k, B_k)$. The probability that $(A_k, B_k) = (p, q)$ is proportional to $3^{e_{p,q}}$
3. For each $k$ ($1 \leqq k \leqq N$), generate $(C_k, D_k)$. The probability that $(C_k, D_k) = (p, q)$ is proportional to $3^{e_{p,q}}$

Sample