Description

两支侦察队正在参加一场侦察竞赛。这是决赛环节，每支队伍都做好了充分准备。比赛在一条自西向东流动的河流沿岸进行。河岸两侧共种植了 $4 \mathrm{~N}$ 棵树，其中北岸和南岸各有恰好 $2 \mathrm{~N}$ 棵。两支队伍轮流进行游戏，你的队伍先手。

在每个回合中，当前行动队伍需要在两岸各选择一棵尚未绑绳的树，并在两棵树之间系一条跨河的绳索。每条新添加的绳索必须位于所有先前绳索的上方。该队伍每有一条先前使用的绳索从新绳索下方穿过，就能获得 1 分。

经过 $2 \mathrm{~N}$ 个回合后，所有树都恰好绑有一条绳索，游戏结束。每支队伍的总得分是他们在所有回合中获得分数的总和。若你队伍的得分严格大于对手队伍的得分，则你队获胜；否则不获胜。

以下动画展示了一个 $\mathrm{N}=2$ 时的可能对局。你队用红色表示，对手队用蓝色表示。

对手队认为后手具有巨大优势，因此公开了他们的策略：在他们的回合中，会选择使当前回合得分最大化的操作。若存在多个这样的操作，则随机选择其一。这个选择在每次操作、每个测试用例和每次提交中都是独立且均匀随机的。因此，即使提交完全相同的代码两次，对手队也可能做出不同的随机选择。

你们共进行 $\mathrm{T}$ 局游戏，你队需要至少赢得其中的 $\mathrm{W}$ 局。

交互协议

这是一个交互题。请确保你已阅读交互题常见问题部分。

初始时，你的程序需读取包含三个整数 $\mathbf{T}$、$\mathbf{N}$ 和 $\mathbf{W}$ 的单行输入，分别表示测试用例数量、你队的回合数以及需要获胜的局数。注意对手队也有 $\mathbf{N}$ 个回合，因此每个测试用例共进行 $2 \mathbf{N}$ 个回合。

对于每个测试用例，你的程序需要处理 $\mathbf{N}$ 轮交互。每轮交互代表连续的两个回合，分别由你队和对手队进行。

对于第 $i$ 轮交互，你需要先输出两个整数 $\mathbf{A}_{i}$ 和 $\mathbf{B}_{i}$，然后读取两个整数 $\mathbf{C}_{i}$ 和 $\mathbf{D}_{i}$。这表示在你队的第 $i$ 个回合中，你选择了北岸从西数第 $\mathbf{A}_{i}$ 棵树和南岸从西数第 $\mathbf{B}_{i}$ 棵树系绳；对手队则在他们的第 $i$ 个回合中选择了北岸第 $\mathbf{C}_{i}$ 棵和南岸第 $\mathbf{D}_{i}$ 棵树。树的编号从 1 开始。

完成 $\mathbf{N}$ 轮交互后，你需要读取一个表示本局结果数字：1 表示你队获胜，0 表示未获胜。

若还有后续测试用例，则立即开始处理。若是最后一个测试用例，评测系统将不再提供输入。注意所有 $\mathbf{T}$ 个测试用例都会被处理，不论是否已确定能否达到正确率阈值。该阈值仅在正确处理所有测试用例后才进行检查。

若评测系统在任何时刻接收到非法格式或无效操作（如选择已使用的树），将输出 -1 并终止交互。若你的程序在收到 -1 后仍等待输入，将导致超时错误。请注意确保程序及时退出以避免该情况。

Input Format

参见交互协议部分。

Output Format

参见交互协议部分。

2 2 1

4 1

2 4
0

2 3

4 4
1

3 2

1 3


1 1

3 2

Hint

你可以使用测试工具在本地或平台上进行测试。本地测试时需要并行运行工具和代码，我们提供了交互运行器。更多说明请参阅该文件中的注释。

测试工具的使用说明包含在工具的注释中。建议你添加自己的测试用例。请注意该工具虽然用于模拟评测系统，但并非真实评测系统，其行为可能有所不同。

数据范围

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

测试集 1（15 分，可见判定）

• $\mathbf{W}=1200$（$\mathbf{W}=0.6 \cdot \mathbf{T}$）

测试集 2（10 分，可见判定）

• $\mathbf{W}=1560$（$\mathbf{W}=0.78 \cdot \mathbf{T}$）

测试集 3（15 分，可见判定）

• $\mathbf{W}=1720$（$\mathbf{W}=0.86 \cdot \mathbf{T}$）

翻译由 DeepSeek V3 完成