CF1354G.Find a Gift

This is an interactive problem. Don't forget to flush output after printing queries using cout.flush() or fflush(stdout) in C++ or similar functions in other programming languages.

There are $n$ gift boxes in a row, numbered from $1$ to $n$ from left to right. It's known that exactly $k$ of them contain valuable gifts — other boxes contain just lucky stones. All boxes look the same and differ only in weight. All boxes with stones have the same weight and are strictly heavier than boxes with valuable items. But valuable gifts may be different, so the boxes with valuable items may have different weights.

You can ask no more than $50$ queries (printing an answer doesn't count). By each query you can compare total weights of two non-intersecting subsets of boxes $a_1, a_2, \dots, a_{k_a}$ and $b_1, b_2, \dots, b_{k_b}$. In return you'll get one of four results:

• FIRST, if subset $a_1, a_2, \dots, a_{k_a}$ is strictly heavier;
• SECOND, if subset $b_1, b_2, \dots, b_{k_b}$ is strictly heavier;
• EQUAL, if subsets have equal total weights;
• WASTED, if the query is incorrect or the limit of queries is exceeded.

Using such queries (or, maybe, intuition) find the box with a valuable gift with the minimum index.

这是一个交互式问题。请勿忘记在输出查询后刷新输出缓存，例如在 C++ 中使用 cout.flush() 或 fflush(stdout)，或其他编程语言中对应的类似函数。

一排共有 $n$ 个礼品盒，从左到右编号为 $1$ 到 $n$。已知其中恰好有 $k$ 个盒子装有贵重礼物，其余盒子仅装有幸运石子。所有盒子外观相同，仅重量不同。所有装有石子的盒子重量相等，且严格重于装有贵重礼物的盒子。但贵重礼物可能各不相同，因此装有贵重礼物的盒子之间重量也可能不同。

你最多可进行 $50$ 次查询（输出最终答案不计入查询次数）。每次查询中，你可以比较两个互不相交的盒子子集 $a_1, a_2, \dots, a_{k_a}$ 和 $b_1, b_2, \dots, b_{k_b}$ 的总重量。系统将返回以下四种结果之一：

• FIRST：若子集 $a_1, a_2, \dots, a_{k_a}$ 的总重量严格更大；
• SECOND：若子集 $b_1, b_2, \dots, b_{k_b}$ 的总重量严格更大；
• EQUAL：若两个子集的总重量相等；
• WASTED：若查询格式错误或查询次数超出限制。

请利用此类查询（或可能还需借助直觉），找出编号最小的、装有贵重礼物的盒子。

The input consists of several cases. In the beginning, you receive the integer $T$ ($1 \le T \le 500$) — the number of test cases.

At the beginning of each test case, you receive two integers $n$ and $k$ ($2 \le n \le 1000$, $1 \le k \le \frac{n}{2}$) — the number of boxes in a row and the number of boxes with valuable gifts.

It's guaranteed that the order of boxes is fixed beforehand and that the sum of $n$ in one test doesn't exceed $1000$.

输入包含多个测试用例。首先，你将接收到一个整数 $T$（$1 \le T \le 500$），表示测试用例的数量。

对于每个测试用例，首先你将接收到两个整数 $n$ 和 $k$（$2 \le n \le 1000$，$1 \le k \le \frac{n}{2}$），分别表示一行中箱子的总数以及其中装有贵重礼物的箱子数量。

保证箱子的排列顺序预先已固定，且单个测试用例中所有 $n$ 的总和不超过 $1000$。

For each test case print the minimum index among all boxes with a valuable gift in the following format: "! $x$" where $x$ ($1 \le x \le n$) — the index of the box.

对于每个测试用例，输出所有装有贵重礼物的盒子中索引最小的一个，格式为：! $x$，其中 $x$（$1 \le x \le n$）为盒子的索引。

Additional separators "–" in the sample are used only to increase the readability of the sample. Don't print any unnecessary symbols or line breaks in your solution when you send it to the system.

Hacks are forbidden in this task.

样例中的额外分隔符“–”仅用于提高样例的可读性。向系统提交解答时，请勿输出任何不必要的符号或换行符。

本题禁止 Hack。