CF1010B.Rocket

This is an interactive problem.

Natasha is going to fly to Mars. Finally, Natasha sat in the rocket. She flies, flies... but gets bored. She wishes to arrive to Mars already! So she decides to find something to occupy herself. She couldn't think of anything better to do than to calculate the distance to the red planet.

Let's define $x$ as the distance to Mars. Unfortunately, Natasha does not know $x$. But it is known that $1 \le x \le m$, where Natasha knows the number $m$. Besides, $x$ and $m$ are positive integers.

Natasha can ask the rocket questions. Every question is an integer $y$ ($1 \le y \le m$). The correct answer to the question is $-1$, if $x \lt y$, $0$, if $x=y$, and $1$, if $x \gt y$. But the rocket is broken — it does not always answer correctly. Precisely: let the correct answer to the current question be equal to $t$, then, if the rocket answers this question correctly, then it will answer $t$, otherwise it will answer $-t$.

In addition, the rocket has a sequence $p$ of length $n$. Each element of the sequence is either $0$ or $1$. The rocket processes this sequence in the cyclic order, that is $1$-st element, $2$-nd, $3$-rd, $\ldots$, $(n-1)$-th, $n$-th, $1$-st, $2$-nd, $3$-rd, $\ldots$, $(n-1)$-th, $n$-th, $\ldots$. If the current element is $1$, the rocket answers correctly, if $0$ — lies. Natasha doesn't know the sequence $p$, but she knows its length — $n$.

You can ask the rocket no more than $60$ questions.

Help Natasha find the distance to Mars. Assume, that the distance to Mars does not change while Natasha is asking questions.

Your solution will not be accepted, if it does not receive an answer $0$ from the rocket (even if the distance to Mars is uniquely determined by the already received rocket's answers).

这是一个交互式问题。

娜塔莎即将飞往火星。终于，娜塔莎坐进了火箭。她飞啊飞……但感到无聊了。她希望快点抵达火星！于是她决定找点事情做来打发时间。她想不出比计算到这颗红色星球的距离更好的事情了。

我们定义 $x$ 为到火星的距离。不幸的是，娜塔莎并不知道 $x$ 的值。但已知 $1 \le x \le m$，其中 $m$ 是娜塔莎已知的一个数。此外，$x$ 和 $m$ 均为正整数。

娜塔莎可以向火箭提问。每次提问是一个整数 $y$（满足 $1 \le y \le m$）。该问题的正确答案为：若 $x \lt y$ 则为 $-1$；若 $x = y$ 则为 $0$；若 $x \gt y$ 则为 $1$。但火箭坏了——它并不总是给出正确答案。具体来说：设当前问题的正确答案为 $t$，那么如果火箭此次回答正确，则返回 $t$；否则返回 $-t$。

此外，火箭内部有一个长度为 $n$ 的序列 $p$。该序列的每个元素非 $0$ 即 $1$。火箭按循环顺序处理该序列，即第 $1$ 个、第 $2$ 个、第 $3$ 个、……、第 $(n-1)$ 个、第 $n$ 个、第 $1$ 个、第 $2$ 个、第 $3$ 个、……、第 $(n-1)$ 个、第 $n$ 个、……依此类推。若当前处理的序列元素为 $1$，则火箭回答正确；若为 $0$，则说谎。娜塔莎不知道序列 $p$ 的具体内容，但她知道其长度 $n$。

你最多可向火箭提出 $60$ 个问题。

请帮助娜塔莎确定到火星的距离。假设在娜塔莎提问过程中，到火星的距离 $x$ 保持不变。

若你的解法未从火箭处收到答案 $0$（即使根据已获得的所有火箭回答已能唯一确定火星距离），则该解法将不被接受。

The first line contains two integers $m$ and $n$ ($1 \le m \le 10^9$, $1 \le n \le 30$) — the maximum distance to Mars and the number of elements in the sequence $p$.

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

In the example, hacking would look like this:

5 2 3

1 0

This means that the current distance to Mars is equal to $3$, Natasha knows that it does not exceed $5$, and the rocket answers in order: correctly, incorrectly, correctly, incorrectly ...

Really:

on the first query ($1$) the correct answer is $1$, the rocket answered correctly: $1$;

on the second query ($2$) the correct answer is $1$, the rocket answered incorrectly: $-1$;

on the third query ($4$) the correct answer is $-1$, the rocket answered correctly: $-1$;

on the fourth query ($5$) the correct answer is $-1$, the rocket answered incorrectly: $1$;

on the fifth query ($3$) the correct and incorrect answer is $0$.

在示例中，黑客攻击过程如下：

5 2 3

1 0

这意味着当前到火星的距离为 $3$，娜塔莎知道该距离不超过 $5$，而火箭的回答顺序为：正确、错误、正确、错误……

实际情况如下：

• 第一次查询（$1$）：正确答案为 $1$，火箭回答正确：$1$；
• 第二次查询（$2$）：正确答案为 $1$，火箭回答错误：$-1$；
• 第三次查询（$4$）：正确答案为 $-1$，火箭回答正确：$-1$；
• 第四次查询（$5$）：正确答案为 $-1$，火箭回答错误：$1$；
• 第五次查询（$3$）：正确答案与错误答案均为 $0$。