Description

这是一道交互题。

Harry 和 Hermione 正在猎捕潜伏在霍格沃茨的 霍格林。霍格沃茨有一条长长的走廊，由 $n$ 个独立的单元格组成，从左到右编号为 $1$ 到 $n$。

Hermione 可以施展咒语封锁她选择的任意一个单元格。一旦施法，该单元格将持续处于封锁状态，直到该轮结束，即使她随后继续施展其他咒语。

霍格林是一种很简单的生物，它们只会随机移动并撞上障碍。更准确地说，每只霍格林都有一个它认为可以活动的可达范围。最初，当霍格林出现时，它的可达范围是整个走廊，即第 $1$ 到第 $n$ 个单元格。

每一只霍格林初始随机地出现在走廊中的某个单元格内。之后，在猎捕过程中，每一轮按照如下流程进行：

• Hermione 可以选择一个单元格进行封锁，或者什么都不做；
• 如果她试图封锁的单元格正好是霍格林所在的位置，那么霍格林就被捕获。随后所有被封锁的单元格被解除封锁，如果还有霍格林待抓捕，则一只新的霍格林立即随机出现，猎捕继续进行；
• 否则，霍格林会从它的当前可达范围中随机选择一个单元格，试图向该单元格移动，该移动将在同一轮内完成，无论其距离多远，具体过程如下：
  • 如果目标单元格在当前霍格林位置的右侧，则霍格林向右移动；如果在左侧，则向左移动；若目标与当前位置相同，则不移动；
  • 在向目标移动的过程中，若霍格林从某个未封锁的位置 $i$ 试图前往其相邻的封锁位置 $i \pm 1$，则霍格林将更新其可达范围的右边界或左边界为 $i$；
  • 如果霍格林在前往目标单元格的路途中撞上了封锁单元格，则 Harry 和 Hermione 会听到一声巨响，此时霍格林会回到本轮开始时的初始位置；
  • 否则，如果途中没有撞到封锁单元格，则霍格林成功移动至目标位置，并保留原有的可达范围。Harry 和 Hermione 什么也不会听到。

为了彻底清除霍格沃茨中的霍格林，Harry 和 Hermione 需要抓到 $k$ 只霍格林，但时间有限。他们最多只能进行 $200\,000$ 轮操作。请帮助他们设计高效的策略。

交互协议说明

首先，评测器会输出两个整数 $n$ 和 $k$（$1 \le n \le 10^{18}$，$1 \le k \le 800$），分别表示走廊的长度和需要抓捕的霍格林数量。接下来开始进行猎捕。

之后交互按轮进行，每轮遵循题目描述的流程：

• 你的程序需输出一个整数 $p$（$0 \le p \le n$），表示 Hermione 本轮选择封锁的位置。如果 $p=0$ 或 $p$ 所在单元格已被封锁，则 Hermione 本轮不进行操作。

• 若当前霍格林正好位于被封锁的位置 $p$，则该霍格林被捕获，评测器输出 $\texttt{2}$，所有封锁单元格解除，并立即生成新的霍格林，猎捕继续进行；

  • 若这是第 $k$ 个被捕获的霍格林，评测器输出 $\texttt{3}$，你的程序应立即退出。

• 若未抓到霍格林，评测器将模拟霍格林的移动并输出如下之一：

  • $\texttt{0}$：霍格林成功移动到目标位置，途中没有撞击；
  • $\texttt{1}$：霍格林在移动途中撞到了封锁单元格，发出声响并返回原位。

• 若你的程序在第 $200\,000$ 轮仍未成功抓到第 $k$ 个霍格林，评测器将输出 $\texttt{-1}$，你的程序应立即退出，否则将判定为 Wrong Answer。

Input Format

详见 交互协议说明。

Output Format

详见 交互协议说明。

9 2

0

1

1

0

1

2

1

0

0

3

3

7

5

1

9

4

5

7

0

2

Hint

下图展示了从霍格林的视角观察的一个示例状态：

• 黑点表示当前霍格林的位置；
• 十字表示被封锁的单元格；
• 白色区域表示霍格林认为的可达范围；
• 灰色区域为其不可达区域；
• 图右侧注释了 Hermione 或霍格林执行的操作，导致状态变化。