CF1010B Rocket

这是一个交互题。 Natasha 即将飞往火星。终于，Natasha 坐上了火箭。她飞啊飞……但很快就感到无聊。她希望能快点到达火星！于是她决定找点事情做。她想不到更好的办法，只好计算到红色星球的距离。 我们定义 $x$ 为到火星的距离。不幸的是，Natasha 并不知道 $x$ 的具体数值。但已知 $1 \le x \le m$，其中 $m$ 是 Natasha 已知的一个数。此外，$x$ 和 $m$ 都是正整数。 Natasha 可以向火箭提问。每次提问是一个整数 $y$（$1 \le y \le m$）。对于每次提问，正确答案为：如果 $x < y$，则为 $-1$；如果 $x = y$，则为 $0$；如果 $x > y$，则为 $1$。但火箭坏了——它并不总是回答正确。具体来说：设当前问题的正确答案为 $t$，那么如果火箭这次回答正确，则它会回答 $t$，否则会回答 $-t$。 此外，火箭有一个长度为 $n$ 的序列 $p$。序列中的每个元素要么是 $0$，要么是 $1$。火箭按循环顺序处理这个序列，即第 $1$ 个元素、第 $2$ 个、第 $3$ 个、……、第 $(n-1)$ 个、第 $n$ 个、第 $1$ 个、第 $2$ 个、第 $3$ 个、……、第 $(n-1)$ 个、第 $n$ 个、……。如果当前元素为 $1$，火箭就会回答正确；如果为 $0$，火箭就会说谎。Natasha 并不知道序列 $p$ 的内容，但她知道它的长度为 $n$。 你最多可以向火箭提问 $60$ 次。 请帮助 Natasha 找到到火星的距离。假设在 Natasha 提问期间，到火星的距离不会发生变化。 如果你的解法没有从火箭那里收到 $0$ 作为回答（即使根据已收到的回答已经唯一确定了距离），你的解法也不会被接受。

第一行包含两个整数 $m$ 和 $n$（$1 \le m \le 10^9$，$1 \le n \le 30$），分别表示到火星的最大距离和序列 $p$ 的长度。

你最多可以向火箭提问 $60$ 次。 每次提问，输出一个数字 $y$（$1 \le y \le m$）并换行，然后刷新输出缓冲区，并读取火箭的回答。 如果你读到 $0$，说明距离已确定，你必须立即终止程序（例如，调用 exit(0)）。如果你忽略这一点，程序会继续从已关闭的输入流读取，可能会得到任意判题结果。 如果你在某个时刻读到 $-2$ 作为回答，必须立即终止程序（例如，调用 exit(0)）。你会收到“Wrong answer”判定，这意味着请求不合法或者请求次数超过 $60$。如果你忽略这一点，程序会继续从已关闭的输入流读取，可能会得到任意判题结果。 如果你的请求不是 $-2^{31}$ 到 $2^{31}-1$（含）之间的合法整数，且没有前导零，也可能得到任意判题结果。 如果你没有输出任何内容，或者忘记刷新输出缓冲区，可能会得到“Idleness limit exceeded”判定。 刷新输出缓冲区的方法如下（在输出问题和换行后）： - C++：fflush(stdout) - Java：System.out.flush() - Python：stdout.flush() - Pascal：flush(output) - 其它语言请查阅相关文档。 Hack 格式 Hack 时请使用如下格式： 第一行输出 $3$ 个整数 $m, n, x$（$1 \le x \le m \le 10^9$，$1 \le n \le 30$），分别表示到火星的最大距离、序列 $p$ 的长度和当前到火星的距离。 第二行输入 $n$ 个数字，每个数字为 $0$ 或 $1$，表示序列 $p$。 被 Hack 的解法无法访问 $x$ 和序列 $p$。

例如，Hack 输入如下： 5 2 3 1 0 这表示当前到火星的距离为 $3$，Natasha 知道它不超过 $5$，火箭的回答顺序为：正确、错误、正确、错误…… 具体过程如下： 第一次询问（$1$），正确答案为 $1$，火箭正确回答：$1$； 第二次询问（$2$），正确答案为 $1$，火箭错误回答：$-1$； 第三次询问（$4$），正确答案为 $-1$，火箭正确回答：$-1$； 第四次询问（$5$），正确答案为 $-1$，火箭错误回答：$1$； 第五次询问（$3$），正确答案为 $0$，无论正误都回答 $0$。 由 ChatGPT 4.1 翻译