这是一个交互式问题！

Hora 是一种传统的罗马尼亚和摩尔多瓦民间舞蹈，参与者手拉手围成一个大圆圈……

在第 8 届欧洲青少年信息学奥林匹克竞赛中，有 $N$ 名参与者开始跳 hora，其中 $N$ 是一个正偶数。男孩的人数等于女孩的人数。组织者为 hora 中的每位参与者分配了一个循环索引。索引从 $0$ 开始，以 $1$ 为增量连续递增，直到 $N - 1$。这意味着索引为 $0$ 和 $N - 1$ 的参与者是邻居，且每位参与者的索引都比其前一个邻居大 $1$。请参阅“样例”部分以了解此类配置。

你并不知道具体哪些参与者是女孩，哪些是男孩，因为你现在正在参加比赛！但是，你可以向测试系统发起调用。每次调用包含两个整数 $L$ 和 $R$，满足 $0 \le L < N$ 且 $0 \le R < N$。响应将包含一个整数——圆圈中从 $L$ 到 $R$ 的连续循环区间内的男孩人数。具体来说：

• 如果 $L \le R$，则答案考虑索引为 $L, L + 1, \dots, R - 1, R$ 的参与者的连续循环区间。
• 如果 $R < L$，则答案考虑索引为 $L, L + 1, \dots, N - 1, 0, \dots, R - 1, R$ 的参与者的连续循环区间。

给定一个整数 $K$ ($1 \le K \le N$)。你的任务是找到圆圈中长度为 $K$ 的一个连续循环区间，使得其中男孩和女孩人数的绝对差尽可能小。更正式地说，你需要实现一个过程，返回一个整数 $S$ ($0 \le S < N$)，使得从 $S$ 开始的长度为 $K$ 的连续循环区间在所有可能的长度为 $K$ 的连续循环区间中，男孩和女孩人数的绝对差最小。注意，某个圆圈配置可能存在多个具有相同最小绝对差的解。在这种情况下，你可以返回其中任何一个。

两个数 $x$ 和 $y$ 的绝对差由 $|x - y|$ 给出。例如，$|2 - 4| = 2$，$|7 - 4| = 3$。

实现细节

你应该实现以下过程：

int solve(int N, int K)

• $N$：hora 中的参与者人数。
• $K$：所考虑区间的长度。
• 该过程应返回 $S$，即男孩和女孩人数绝对差最小的长度为 $K$ 的区间的起始整数。
• 该过程仅被调用一次。

上述过程可以调用以下过程：

int ask(int L, int R)

• $L$：查询区间的起始索引。
• $R$：查询区间的结束索引。
• 返回查询区间内的男孩人数。
• 如果对 ask 过程的调用次数超过 $10^5$，则该方案将收到 Wrong Answer 判决。

样例

假设圆圈看起来如下：

注意，带有白色字母 B 的圆圈代表男孩，带有黑色字母 G 的圆圈代表女孩。此外，每个圆圈右侧的数字代表相应人员的索引。

考虑以下调用：

solve(12, 5)

在这个例子中，有 12 个人在跳 hora，我们寻找长度为 5 的连续区间，使得男孩和女孩人数的绝对差最小。我们的程序发起调用：

ask(0, 10)

对应的答案是 6，意味着该区间内有 6 个男孩在跳 hora。我们可以很容易地推断出同一区间内有 5 个女孩在跳 hora。

ask(0, 4)

对应的答案是 4，意味着该区间内有 4 个男孩在跳 hora。

ask(1, 5)

对应的答案是 3，意味着该区间内有 3 个男孩在跳 hora。我们可以很容易地推断出同一区间内有 2 个女孩在跳 hora。由于 3 和 2 的绝对差是 1，且不存在长度为 5 且绝对差更小的区间，因此你的程序返回 1，这是该对应区间的起始位置。

数据范围

• $2 \le N \le 10^5$
• $1 \le K \le N$
• $N$ 是偶数。
• hora 中参与的男孩和女孩人数相等。
• 评测机不是自适应的。

你的方案将在一组测试组上进行测试，每组测试组都有一定的分值。每个测试组包含一组测试用例。

对于带有参数 $Q_{full}$ 和 Score 的测试组，令 $Q$ 为该测试中调用 ask 过程的次数。如果 $Q \le Q_{full}$，你将获得该测试的 Score 分。如果 $N \ge Q > Q_{full}$，你将获得 $\text{Score} \cdot \left( 1 - \left( \frac{Q - Q_{full}}{N} \right)^{0.05} \right)$ 分。如果 $Q > N$ 或者你的程序对该测试的答案错误，你将获得 0 分。该组的总分是其所有测试中的最低得分。

调用 ask 过程超过 $10^5$ 次将导致 Wrong Answer 判决。

样例评测机

样例评测机按以下格式读取输入：

• 第 1 行：$N, K$
• 第 2 行：$A[0], A[1], \dots, A[N - 1]$，其中数组 $A$ 是表示我们隐藏的参与者圆圈的字符串。特别地，如果 $A[i] = \text{'X'}$，则圆圈中对应的人是男孩；如果 $A[i] = \text{'Y'}$，则圆圈中对应的人是女孩。

样例评测机按以下格式输出每个问题：

• 第 1 行：? L R

样例评测机按以下格式输出每个答案：

• 第 1 行：x boys

样例评测机按以下格式输出选手的答案：

• 第 1 行：! S

在交互结束时，评测机在标准输出的最后一行报告选手调用 ask 过程的次数。