两个侦察队正在参加一场侦察比赛。现在是决赛，每个队伍都准备充分。比赛沿着一条自西向东流动的河流进行。河岸边种有树木，北岸恰好有 $2N$ 棵树，南岸也有 $2N$ 棵树。两支队伍轮流进行游戏。你的队伍先手。

在每一轮中，当前行动的队伍选择南北两岸各一棵尚未系绳的树，并在两棵树之间系上一根绳子，使其横跨河流。每一根新加的绳子都放置在所有先前绳子的上方。当前行动的队伍每使新加的绳子穿过一根先前已有的绳子，即可获得 1 分。

在 $2N$ 轮之后，所有的树都恰好系有一根绳子，因此没有更多可能的走法，游戏结束。每支队伍的总分是他们在所有轮次中获得的分数之和。如果你的队伍得分严格大于对方队伍的得分，则你的队伍获胜。如果你的队伍得分小于或等于对方队伍的得分，则你的队伍不获胜。

以下动画展示了 $N = 2$ 时的一种可能游戏过程。你的队伍用红色表示，对方队伍用蓝色表示。

对方队伍认为先手有巨大优势，因此他们公开了他们的策略。在他们的回合中，他们会选择能使该回合得分最大化的走法。如果存在多种这样的走法，他们会随机选择其中一种。这种选择是针对每一轮、每一个测试用例以及每一次提交，独立且均匀随机生成的。因此，即使你提交完全相同的代码两次，对方队伍也可能做出不同的随机选择。

你总共进行 $T$ 场游戏，你的队伍必须至少赢得其中的 $W$ 场。

输入格式

这是一个交互式问题。请确保你已阅读 FAQ 中关于交互式问题的相关信息。

程序首先应读取一行，包含三个整数 $T$、$N$ 和 $W$：分别表示测试用例的数量、你队伍的回合数以及你需要获胜的场数。注意，对方队伍也有 $N$ 个回合，每场游戏总共进行 $2N$ 个回合。

对于每个测试用例，你的程序必须处理 $N$ 次交换。每次交换代表两个连续的回合，一轮由你的队伍进行，一轮由对方队伍进行。

对于第 $i$ 次交换，你必须首先打印一行，包含两个整数 $A_i$ 和 $B_i$，然后读取一行，包含两个整数 $C_i$ 和 $D_i$。这表示在你的第 $i$ 轮中，你将北岸从西往东数第 $A_i$ 棵树与南岸从西往东数第 $B_i$ 棵树连接起来。类似地，在对方队伍的第 $i$ 轮中，他们使用了北岸从西往东数第 $C_i$ 棵树和南岸从西往东数第 $D_i$ 棵树。树的编号从 1 开始。

在 $N$ 次交换后，你必须读取一个数字，表示该场游戏的结果。如果你的队伍获胜，该数字为 1，否则为 0。

如果还有下一个测试用例，它会立即开始。如果这是最后一个测试用例，裁判将不再发送任何输入，也不期望更多的输出。此外，无论是否已经保证达到获胜场数，所有测试用例都会被处理。只有在处理完所有测试用例后，才会检查是否达到获胜阈值。

如果裁判在任何时刻收到格式错误的行或无效的移动（例如使用已经使用过的树），裁判将打印单个数字 -1 并且不再打印任何输出。如果你的程序在收到 -1 后继续等待裁判，程序将超时，导致 Time Limit Exceeded 错误。请注意，你有责任及时退出程序以接收 Wrong Answer 判决，而不是 Time Limit Exceeded 错误。通常情况下，如果超出内存限制或程序出现运行时错误，你将收到相应的判决。

数据范围

时间限制：90 秒。 内存限制：1 GB。 $T = 2000$。 $N = 50$。

子任务

测试集 1（可见判决）： $W = 1200$ ($W = 0.6 \cdot T$)。

测试集 2（可见判决）： $W = 1560$ ($W = 0.78 \cdot T$)。

测试集 3（可见判决）： $W = 1720$ ($W = 0.86 \cdot T$)。

样例

样例交互