你将建造 $N$ 座塔，每座塔由 $B$ 个立方体块组成，一次放置一个块。塔是自底向上建造的：放置在塔中的第 $i$ 个块最终位于从底部数起的第 $i$ 层。你需要在看到任何后续块之前决定将每个块放置在哪里，且一旦放置，块就不能移动。

每个块上印有一个十进制数字，塔的建造方式使得印有数字的面都朝前。字体设计使得块不能通过旋转来获得不同的数字（例如，印有 $6$ 的块不能通过旋转得到 $9$，反之亦然）。

例如，假设 $N = 3$ 且 $B = 3$，你当前拥有的塔如图 1 所示。如果接下来出现一个印有 $6$ 的块，你有两个选择：要么将其放在只有两个块的塔顶（如图 2 所示），要么开始建造第三座塔（如图 3 所示）。注意，你不能将其放在第一座塔的顶部，因为第一座塔已经有 $B$ 个块了。

图 1

图 2

图 3

建造完成后，我们从上到下读取每座塔正面印有的 $B$ 位整数（即最后放置在塔上的块上的数字是最高位）。注意，这些整数可能包含任意数量的前导零。然后，我们将这 $N$ 个整数相加，得到我们建造操作的得分。

例如，在下方的图 4 中，从左到右每座塔上读取的整数分别是 $123$、$345$ 和 $96$。该建造操作的得分为 $123 + 345 + 96 = 564$。

图 4

每个块上的数字是均匀随机生成的，且独立于任何其他信息。为了使你的解法被判定为正确，你在所有 $T$ 个测试用例上的得分总和必须至少为 $P$。

输入格式

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

裁判程序最初会向你发送一行，包含四个整数 $T$、$N$、$B$ 和 $P$：测试用例的数量、塔的数量、每座塔的块数，以及通过此测试集所需的最低总得分。

然后，你必须处理 $T$ 个测试用例。每个测试用例包含 $N \times B$ 次交换。每次交换对应放置一个块。在每次交换中，裁判程序首先会打印一行，包含一个整数 $D$，表示你需要放置的块上印有的数字。你需要回复一行，包含一个整数 $i$，表示你想要放置该块的塔的编号（在 $1$ 到 $N$ 之间）。

在每个测试用例（最后一个除外）的最后一次交换后，裁判程序将立即开始下一个测试用例。在最后一个测试用例的最后一次交换后，裁判程序将打印额外的一行，包含一个整数：如果你的总得分至少为 $P$，则为 $1$，否则为 $-1$。

如果裁判程序收到格式错误的行、无效的塔编号，或者你程序指定的塔已经包含 $B$ 个块，裁判程序将打印单个数字 $-1$。在裁判程序因上述任何原因打印 $-1$ 后，它将不再打印任何输出。如果你的程序在收到 $-1$ 后继续等待裁判程序，你的程序将超时，导致“超出时间限制”（Time Limit Exceeded）错误。请注意，你有责任让你的程序及时退出，以接收“答案错误”（Wrong Answer）判决，而不是“超出时间限制”错误。通常情况下，如果超过内存限制或程序出现运行时错误，你将收到相应的判决。

你可以假设每个块的数字是均匀随机生成的，且对于每个数字、每个测试用例和每次提交都是独立的。因此，即使你提交完全相同的代码两次，裁判程序也可能使用不同的随机数字。

数据范围

时间限制：60 秒。 内存限制：1 GB。

$T = 50$。 $N = 20$。 $B = 15$。 $D$ 是 $0$ 到 $9$ 之间的十进制数字。

测试集 1（可见判决）

$P = 860939810732536850$（约为 $8.6 \times 10^{17}$）。 注意，此边界选择为 $T \times S$ 的约 $90\%$，其中 $S = 19131995794056374.42...$（约为 $1.9 \times 10^{16}$）是该问题在拥有无限运行时间的情况下，单个测试用例所能达到的最高期望得分。 上述 $S$ 的精确值可以在本地测试工具的第 13 行和第 14 行找到。

测试集 2（可见判决）

$P = 937467793908762347$（约为 $9.37 \times 10^{17}$）。 注意，此边界选择为 $T \times S$ 的约 $98\%$。

样例

样例交互