猎杀霍格沃茨的疣猪兽

交互题

时间限制：$6$ 秒 内存限制：$1024$ 兆字节

哈利和赫敏正在追捕游荡在霍格沃茨的疣猪兽。霍格沃茨有一条长长的走廊，由 $n$ 个独立的牢房组成，从左到右编号为 $1$ 到 $n$。

赫敏可以施展咒语，封锁走廊中任意一个她选定的牢房。咒语施放后，被封锁的牢房会一直保持封锁状态，直到她再次施放其他咒语。

疣猪兽是一种头脑简单的生物，它们只会四处随机移动并撞到障碍物。具体来说： 每只疣猪兽都有一个它认为可通行的区间。当疣猪兽最初出现时，可通行区间为从牢房 $1$ 到牢房 $n$。

一开始，一只疣猪兽会均匀随机地出现在走廊的某个牢房中。然后，在这只疣猪兽被抓住之前，狩猎的每一轮都会按以下流程进行：

1. 赫敏可以选择封锁任意一个牢房，或者什么都不做。
2. 如果她试图封锁的牢房正是疣猪兽所在的牢房，则疣猪兽被捕获。之后，所有被封锁的牢房都会解除封锁。如果还有更多疣猪兽需要捕获，一只新的疣猪兽会立即随机出现在一个位置，狩猎重新开始。
3. 否则，疣猪兽会从它的可通行区间内均匀随机选择一个目标牢房，并尝试向该牢房移动，每次移动一个单元格。无论距离多远，下述的所有移动步骤都在同一轮内完成。
4. 如果选定的目标牢房在疣猪兽的右侧，它就向右移动；如果在左侧，就向左移动。如果选定的牢房与当前位置相同，它则原地不动。
5. 如果在向目标牢房移动的过程中，疣猪兽试图从一个未被封锁的牢房 $i$ 移动到相邻的、已被封锁的牢房 $i \pm 1$，疣猪兽会相应地将其可通行区间的右边界或左边界更新为 $i$。
6. 如果在前往目标牢房的途中，疣猪兽试图进入一个已被封锁的牢房，哈利和赫敏会听到一声巨响（疣猪兽撞到了封锁的牢房）。在这种情况下，疣猪兽会回到本轮开始时的初始位置。
7. 否则，如果疣猪兽在途中没有撞到任何已被封锁的牢房，它的可通行区间不会改变，并停留在新的位置。在这种情况下，哈利和赫敏什么也听不到。

为了将霍格沃茨从疣猪兽手中解放出来，哈利和赫敏需要抓住 $k$ 只疣猪兽，但他们时间紧迫。他们最多只能进行 $200000$ 轮狩猎。请你帮助他们制定一个高效的策略。

---

交互协议

首先，评测系统会输出两个整数 $n$ 和 $k$（$1 \le n \le 10^{18}$；$1 \le k \le 80$）——分别代表走廊的牢房数量和需要捕获的疣猪兽数量。随后，捕获过程开始。

接下来的交互按照题目描述的轮次进行。

在每一轮开始时，你的程序应当输出赫敏的行动：一个整数 $p$（$0 \le p \le n$），代表赫敏想要封锁的牢房位置。

• 如果 $p = 0$ 或者 位置 $p$ 的牢房已经被封锁，赫敏在本轮什么都不做。

然后：

• 如果疣猪兽当前的位置恰好是新封锁的牢房 $p$，则疣猪兽被捕获。评测系统会输出 $2$，所有被封锁的牢房重置为未封锁状态，交互轮次重新开始。
  • 如果你捕获了第 $k$ 只疣猪兽，评测系统会输出 $3$ 而非 $2$，你的程序应立即终止。
• 否则，疣猪兽会按照题目描述的规则尝试移动。
  • 如果过程中撞到了已被封锁的牢房，评测系统输出 $1$。
  • 否则，评测系统输出 $0$。

如果你的第 $200000$ 次行动仍未捕获第 $k$ 只疣猪兽，评测系统会输出 $-1$ 而非常规回复，你的程序应立即终止以确保被判为“Wrong Answer”。

本题的交互器是非自适应的。保证疣猪兽严格遵循题目描述的规则行动。每只疣猪兽的初始位置是均匀随机选择的，它们的移动目标也是从其可通行区间内均匀随机选择的。

本题最多包含 $15$ 组测试数据。

评测系统所有可能的回复汇总

• $-1$ —— 行动次数过多；
• $0$ —— 疣猪兽移动成功，未发生碰撞；
• $1$ —— 疣猪兽尝试移动，撞到了封锁的牢房；
• $2$ —— 疣猪兽已被捕获，新一轮交互开始；
• $3$ —— 第 $k$ 只疣猪兽已被捕获，程序终止。

---

样例

标准输入

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

标准输出

3
7
5
1
9
4
5
7

图示说明

1 2 3 4 5 6 7 8 9
初始位置 8
封锁 3
移动到 4，成功
封锁 7
移动到 9，碰撞
封锁 5
移动到 3，碰撞
封锁 1
移动到 4，成功
封锁 9
移动到 5，碰撞
封锁 4，捕获
初始位置 3
封锁 5
移动到 9，碰撞
封锁 7
移动到 1，成功
什么都不做
移动到 2，成功
封锁 2，捕获

注释

我们从疣猪兽的视角展示样例。

• 黑点表示疣猪兽的当前位置。
• 叉号标记已被封锁的牢房。
• 白色单元格标记疣猪兽认为可通行的区间；其他单元格标记为灰色。
• 右侧展示了赫敏或疣猪兽从上一个状态转换到当前状态所执行的行动。