在霍格沃茨捕捉 Hoglin

这是一个交互式问题。

哈利和赫敏正在试图捕捉在霍格沃茨出没的 Hoglin。霍格沃茨有一条长长的走廊，由 $n$ 个独立的单元格组成，从左到右编号为 $1$ 到 $n$。

赫敏可以施展咒语，封锁她选择的走廊中的任何一个单元格。咒语施放后，该单元格将保持封锁状态，同时她可以继续施放其他咒语。

Hoglin 是简单的生物；它们所做的只是随机移动并撞到东西。更准确地说，每个 Hoglin 都有一个它认为可访问的范围。最初，当 Hoglin 出现时，它的可访问范围是从单元格 $1$ 到单元格 $n$。

最初，单个 Hoglin 出现在走廊中一个均匀随机选择的单元格中。然后，直到该 Hoglin 被捕获，狩猎的每一轮都会发生以下情况：

• 赫敏可以施展咒语封锁她选择的任何单个单元格，或者什么都不做。
• 如果她试图封锁的单元格正是 Hoglin 所在的单元格，则 Hoglin 被捕获。此后，所有被封锁的单元格再次变为空闲，如果还有更多的 Hoglin 需要捕捉，一个新的 Hoglin 会立即出现在一个随机位置，狩猎重新开始。
• 否则，Hoglin 会从其可访问范围内均匀随机选择一个单元格，并尝试向该单元格移动，每次向目标单元格移动一个单元格。无论距离如何，下述所有移动步骤都在同一轮中发生。
• 如果目标单元格在 Hoglin 的右侧，它向右移动；如果目标单元格在 Hoglin 的左侧，它向左移动。如果目标单元格与 Hoglin 当前所在位置相同，它什么也不做。
• 如果在向目标单元格移动的过程中，Hoglin 试图从位置 $i$ 的未封锁单元格向位置 $i \pm 1$ 的相邻封锁单元格移动，Hoglin 会相应地将其可访问范围的右边界或左边界更新为 $i$。
• 如果在前往目标单元格的路上，Hoglin 试图移动到一个被封锁的单元格，哈利和赫敏会听到一声巨响，因为 Hoglin 撞到了被封锁的单元格。在这种情况下，Hoglin 会回到本轮开始时它最初所在的位置。
• 否则，如果 Hoglin 在路上没有撞到任何被封锁的单元格，它不会改变其可访问范围并停留在新位置。在这种情况下，哈利和赫敏什么也听不到。

为了将霍格沃茨从 Hoglin 中解放出来，哈利和赫敏需要捕捉 $k$ 只 Hoglin，但他们没有太多时间。他们最多只能进行 $200\,000$ 轮狩猎。请帮助他们找到一种有效的策略来完成这项任务。

交互

首先，测试系统将写入两个整数 $n$ 和 $k$ ($1 \le n \le 10^{18}; 1 \le k \le 800$) —— 霍格沃茨走廊的单元格数量和需要捕捉的 Hoglin 数量。然后捕捉过程开始。

交互过程按题目描述的轮次进行。

在每一轮开始时，你的程序应输出赫敏的行动 —— 一个整数 $p$ ($0 \le p \le n$)，代表赫敏准备封锁的单元格位置。如果 $p = 0$ 或位置 $p$ 的单元格已经被封锁，则她在本轮中什么都不做。

然后，如果 Hoglin 当前的位置在新封锁的单元格 $p$ 上，则 Hoglin 被捕获；测试系统输出 $2$，所有被封锁的单元格变为空闲，交互轮次重新开始。如果你捕获了第 $k$ 只 Hoglin，测试系统输出 $3$ 而不是 $2$，你的程序应立即停止执行。

否则，Hoglin 会尝试按照题目描述的规则移动。如果在此过程中它撞到了任何被封锁的单元格，测试系统输出 $1$；否则，它输出 $0$。

如果你的第 $200\,000$ 次行动没有捕获第 $k$ 只 Hoglin，测试系统将输出 $-1$ 而不是通常的答案，你的程序应立即停止执行以确保获得“Wrong Answer”判决。

本题中的交互器不是自适应的。保证 Hoglin 遵循题目描述的规则。每只 Hoglin 的起始单元格是均匀随机选择的，它们的移动是从它们认为可访问的单元格范围内均匀随机选择的。

本题最多有 $15$ 个测试点。

以下是所有可能的交互器回答汇总： $-1$ — 行动次数过多； $0$ — Hoglin 移动成功，未发生碰撞； $1$ — Hoglin 尝试移动，撞到了被封锁的单元格； $2$ — Hoglin 被捕获，交互重新开始； * $3$ — Hoglin 被捕获，停止。

样例

输入 1

9 2
0
1
1
0
1
2
1
0
0
3

输出 1

3
7
5
1
9
4
5
7
0
2

说明

我们从 Hoglin 的角度展示样例。 黑点表示 Hoglin 的当前位置。 叉号标记被封锁的单元格。 白色单元格标记 Hoglin 认为可访问的范围；其他单元格标记为灰色。 右侧是赫敏或 Hoglin 为从上一个状态转换到当前状态所执行的动作。