A 和 B 想要潜入一个绝密的研究实验室。不幸的是，入口处配备了复杂的安全系统：系统会提出一个问题（为了简便起见，该问题被编码为一个整数 $q$ ($1 \le q \le N$)），必须回答“yes”或“no”。如果回答正确，系统会开门；否则会触发警报。A 和 B 都知道，系统的提问 $q$ 总是等于 $x$ 或 $y$ 之一 ($x \neq y$)，其中对 $x$ 的正确回答是“yes”，对 $y$ 的正确回答是“no”。

然而，当 A 和 B 策划行动细节时，他们记不起 $x$ 和 $y$ 的具体值。因此，B 被派往入口处进行尝试，而 A 则留在一定距离外以确保他们能够逃脱。

但突然间，就在问题出现时， A 想起了 $x$ 和 $y$ 以及它们的正确答案。但由于距离太远，A 无法给 B 传递明确的指令。他只能向 B 大喊一个整数 $h$ ($1 \le h$)。因此，A 试图将 B 正确回答问题所需的所有信息编码进 $h$ 中。

请在这种情况下帮助 A 和 B，编写一个能够同时扮演 A 和 B 角色的程序。你的程序应当：

1) 对于给定的值 $N, x, y$，帮助 A 并告诉他应该向 B 喊出哪个数字 $h$；以及 2) 对于给定的值 $N, q, h$，帮助 B 并告诉他应该选择什么回答。

你的程序将按如下方式进行测试：首先，程序需要帮助 A 并为若干个测试用例生成数字 $h$；然后，程序需要帮助 B，并将之前生成的数字 $h$ 作为测试用例输入。也就是说，对于每个测试点，你的提交将被运行恰好两次。

输入格式

输入的第一行包含一个整数，为 1（在第一轮运行中）或 2（在第二轮运行中）。

如果为 1，则程序需要帮助 A。输入的其余部分主要由 $T$ 个测试用例组成：第二行包含整数 $N$ 和 $T$（在同一个输入中，所有测试用例的 $N$ 均相同）。接下来的 $T$ 行中，第 $i$ 行描述测试用例 $i$，包含两个整数 $x$ 和 $y$ ($1 \le x, y \le N, x \neq y$)。

如果为 2，则程序需要帮助 B。输入的其余部分主要由 $T$ 个测试用例组成：第二行包含整数 $N$ 和 $T$（在同一个输入中，所有测试用例的 $N$ 均相同）。接下来的 $T$ 行中，第 $i$ 行包含两个整数 $q$ 和 $h$ ($1 \le q \le N, 1 \le h$)；其中 $h$ 是程序在第一轮运行中为测试用例 $i$ 输出的数字。

输出格式

如果程序需要帮助 A，则输出应包含 $T$ 行，其中第 $i$ 行包含 A 在测试用例 $i$ 中应当向 B 喊出的整数 $h$ ($1 \le h$)。对于任意两个输入值 $x$ 和 $y$ 相同的测试用例，你的程序必须输出相同的 $h$ 值。

如果程序需要帮助 B，则输出应包含 $T$ 行，其中第 $i$ 行包含字符串 yes 或 no：即测试用例 $i$ 的正确回答。对于任意两个输入值 $q$ 和 $h$ 相同的测试用例，你的程序必须输出相同的回答字符串。

测试

为了进行测试，你可以使用提供的 manager.sh 工具：

创建一个“输入文件”（例如 input.txt）：第一行必须包含数字 $N$ 和 $T$。接下来的 $T$ 行中，每行包含对应测试用例的数字 $x, y$ 和 $q$。

然后（在照常编译后），你可以使用以下命令运行你的解决方案：

./manager.sh ./yoursolution input.txt

这将创建文件 for1.txt 和 from1.txt（分别对应帮助 A 的程序的输入和输出文件）以及 for2.txt 和 from2.txt（分别对应帮助 B 的程序的输入和输出文件）。此外，它还会告诉你你的解决方案是否正确解决了你指定的输入。

数据范围

在所有测试用例中，$1 \le N \le 920$ 且 $1 \le T \le 2\,000\,000$。

子任务

你的得分取决于在所有测试输入文件中，A 向 B 喊出的最大数字 $h$：

此外，你的程序在所有输入文件的第二轮运行中的输出必须全部正确；否则，你的程序将获得 0 分。

样例

以下是使用 manager.sh 时的一个示例。

input.txt 的内容为：

5 6
1 2 1
4 5 4
1 2 2
3 5 3
4 5 5
5 2 2

样例输入 1

1
5 6
1 2
4 5
1 2
3 5
4 5
5 2

样例输出 1

12
2
12
4
2
1

样例输入 2

2
5 6
1 12
4 2
2 12
3 4
5 2
2 1

样例输出 2

yes
yes
no
yes
no
no

说明

请注意，from1.txt（即样例输出 1）的许多其他输出也是合法的，但只有此 from2.txt（即样例输出 2）的输出是正确的。

反馈

本题提供完整反馈，即显示的公开得分等于你的实际得分，并且会显示所有测试用例的评测结果。