题目描述

Two scout teams are taking part in a scouting competition. It is the finals and each team is well prepared. The game is played along a river that flows west to east. There are $4 \mathrm{~N}$ trees planted along the river, with exactly $2 \mathrm{~N}$ of them lined up along the north bank and $2 \mathrm{~N}$ lined up along the south bank. Both teams alternate turns playing the game. Your team goes first.

On each turn, the playing team selects one tree on each bank that does not have any ropes tied to it and ties a rope between both trees, making it cross the river. Each rope that is added is placed higher than all previous ropes. The playing team scores 1 point per each previously used rope that passes below the newly added rope.

After $2 \mathrm{~N}$ turns, all trees have exactly one rope tied to them, so there are no more possible plays and the game is over. The score of each team is the sum of the scores they got in all of their turns. If your team's score is strictly greater than the opposing team's score, your team wins. If your team's score is less than or equal to the opposing team's score, your team does not win.

The following animation shows a possible game with $\mathrm{N}=2$. Your team is represented by the color red and the other team by the color blue.

The opposing team felt confident that going second is a large advantage, so they revealed their strategy. On their turn, they choose the play that yields the maximum possible score for this turn. If multiple such plays exist, they choose one at random. This choice is generated uniformly at random, and independently for each play, for each test case and for each submission. Therefore, even if you submit exactly the same code twice, the opposing team can make different random choices.

You play $\mathrm{T}$ games in total, and your team must win at least $\mathrm{W}$ of them.

Interactive Protocol

This is an interactive problem. You should make sure you have read the information in the Interactive Problems section of our $F A Q$.

Initially, your program should read a single line containing three integers $\mathbf{T}, \mathbf{N}$, and $\mathbf{W}$ : the number of test cases, the number of turns of your team and the number of wins you need to get for your solution to be considered correct, respectively. Note that the opposing team also gets $\mathbf{N}$ turns, for a total of $2 \mathbf{N}$ turns for each test case.

For each test case, your program must process $\mathbf{N}$ exchanges. Each exchange represents two consecutive turns, one from your team and one from the opposing team.

For the $i$-th exchange, you must first print a single line with two integers $\mathbf{A}_{i}$ and $\mathbf{B}_{i}$ and then read a single line with two integers $\mathbf{C}_{i}$ and $\mathbf{D}_{i}$. This represents that in your $i$-th turn you tied the rope between the $\mathbf{A}_{i}$-th tree from the west on the north bank and the $\mathbf{B}_{i}$-th tree from the west on the south bank. Similarly, in the opposing team's $i$-th turn they used the $\mathbf{C}_{i}$-th tree from the west on the north bank and the $\mathbf{D}_{i}$-th tree from the west on the south bank. Trees are indexed starting from 1.

After the $\mathbf{N}$ exchanges, you must read one number that represents the result of this game. This number will be 1 if your team won, otherwise it will be 0 .

The next test case starts immediately if there is one. If this was the last test case, the judge will expect no more output and will send no further input to your program. In addition, all $\mathbf{T}$ test cases are always processed, regardless of whether it is already guaranteed that the threshold for correctness will or cannot be met. The threshold is only checked after correctly processing all test cases.

If the judge receives an invalidly formatted line or invalid move (like using a tree that has already been used) from your program at any moment, the judge will print a single number -1 and will not print any further output. If your program continues to wait for the judge after receiving a -1, your program will time out, resulting in a Time Limit Exceeded error. Notice that it is your responsibility to have your program exit in time to receive a Wrong Answer judgment instead of a Time Limit Exceeded error. As usual, if the memory limit is exceeded, or your program gets a runtime error, you will receive the appropriate judgment.

输入格式

See Interactive Protocol.

输出格式

See Interactive Protocol.

2 2 1

4 1

2 4
0

2 3

4 4
1

3 2

1 3


1 1

3 2

提示

You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the instructions in comments in that file.

Instructions for the testing tool are included in comments within the tool. We encourage you to add your own test cases. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently.

Limits

• $\mathbf{T}=2000$.
• $\mathbf{N}=50$.

Test Set 1 (15 Pts, Visible Verdict)

• $\mathbf{W}=1200(\mathbf{W}=0.6 \cdot \mathbf{T})$.

Test Set 2 (10 Pts, Visible Verdict)

• $\mathbf{W}=1560(\mathbf{W}=0.78 \cdot \mathbf{T})$.

Test Set 3 (15 Pts, Visible Verdict)

• $\mathbf{W}=1720(\mathbf{W}=0.86 \cdot \mathbf{T})$.