CF1470C.Strange Shuffle

This is an interactive problem.

$n$ people sitting in a circle are trying to shuffle a deck of cards. The players are numbered from $1$ to $n$, so that players $i$ and $i+1$ are neighbours (as well as players $1$ and $n$). Each of them has exactly $k$ cards, where $k$ is even. The left neighbour of a player $i$ is player $i - 1$, and their right neighbour is player $i + 1$ (except for players $1$ and $n$, who are respective neighbours of each other).

Each turn the following happens: if a player has $x$ cards, they give $\lfloor x / 2 \rfloor$ to their neighbour on the left and $\lceil x / 2 \rceil$ cards to their neighbour on the right. This happens for all players simultaneously.

However, one player $p$ is the impostor and they just give all their cards to their neighbour on the right. You know the number of players $n$ and the number of cards $k$ each player has initially, but $p$ is unknown to you. Your task is to determine the value of $p$, by asking questions like "how many cards does player $q$ have?" for an index $q$ of your choice. After each question all players will make exactly one move and give their cards to their neighbours. You need to find the impostor by asking no more than $1000$ questions.

这是一个交互式问题。

有 $n$ 个人围坐成一圈，正在尝试洗一副扑克牌。玩家编号为 $1$ 到 $n$，因此玩家 $i$ 和 $i+1$ 是相邻的（玩家 $1$ 和 $n$ 也彼此相邻）。每人恰好持有 $k$ 张牌，其中 $k$ 为偶数。玩家 $i$ 的左邻是玩家 $i - 1$，右邻是玩家 $i + 1$（但玩家 $1$ 和 $n$ 彼此互为左右邻）。

每一轮执行如下操作：若某玩家当前持有 $x$ 张牌，则其向左邻给出 $\lfloor x / 2 \rfloor$ 张牌，向右邻给出 $\lceil x / 2 \rceil$ 张牌。所有玩家同时进行此操作。

然而，其中一名玩家 $p$ 是“冒名者”（impostor），他/她会将自己全部的牌都交给右邻。你已知玩家总数 $n$ 及每人初始持牌数 $k$，但冒名者 $p$ 的身份未知。你的任务是通过提问来确定 $p$ 的值；每次提问的形式为：“玩家 $q$ 当前有多少张牌？”，其中 $q$ 由你指定。每次提问后，所有玩家将恰好执行一轮操作（即按上述规则分发牌）。你至多只能提出 $1000$ 个问题，就必须找出冒名者。

The first line contains two integers $n$ and $k$ ($4 \le n \le 10^5$, $2 \le k \le 10^9$, $k$ is even) — the number of players and the number of cards.

第一行包含两个整数 $n$ 和 $k$（$4 \le n \le 10^5$，$2 \le k \le 10^9$，且 $k$ 为偶数）—— 分别表示玩家数量和卡片总数。

In the example the cards are transferred in the following way:

• $2$ $2$ $2$ $2$ — player $1$ has $2$ cards.
• $1$ $2$ $3$ $2$ — player $1$ has $1$ card.

After this turn the number of cards remains unchanged for each player.

在示例中，卡片按以下方式转移：

• $2$ $2$ $2$ $2$ — 玩家 $1$ 拥有 $2$ 张卡片。
• $1$ $2$ $3$ $2$ — 玩家 $1$ 拥有 $1$ 张卡片。

在此轮之后，每位玩家所持卡片数量保持不变。