310667: CF1867E1. Salyg1n and Array (simple version)

E1. Salyg1n and Array (simple version)time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is the simple version of the problem. The only difference between the versions is the limit on the number of queries. In this version, you can make no more than 100 queries. You can make hacks only if both versions of the problem are solved.

This is an interactive problem!

salyg1n has given you a positive integer $k$ and wants to play a game with you. He has chosen an array of $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$). You must print $a_1 \oplus a_2 \oplus \ldots \oplus a_n$, where $\oplus$ denotes the bitwise XOR operation. You can make queries of the following type:

• $?$ $i$: in response to this query, you will receive $a_i \oplus a_{i + 1} \oplus \ldots \oplus a_{i + k - 1}$. Also, after this query, the subarray $a_i, a_{i + 1}, \ldots, a_{i + k - 1}$ will be reversed, i.e., the chosen array $a$ will become: $a_1, a_2, \ldots a_{i - 1}, a_{i + k - 1}, a_{i + k - 2}, \ldots, a_{i + 1}, a_i, a_{i + k}, \ldots, a_n$.

You can make no more than $100$ queries to answer the problem.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) – the number of test cases.

Interaction

The interaction between your program and the jury's program begins with reading two positive even integers $n$ and $k$ ($1 \leq k \leq n \leq k^2 \leq 2500$) – the length of the chosen array and the length of the query subarray, respectively.

To find the value of $a_i \oplus a_{i + 1} \oplus \ldots \oplus a_{i + k - 1}$, print the query in the format $?$ $i$ ($1 \leq i \leq n - k + 1$). Then read a single integer – the answer to your query.

You can make no more than $100$ queries. When you are ready to print the answer, output it in the format $!$ $x$. After that, proceed to process the next test case or terminate the program if it was the last test case. Printing the answer does not count as one of the $100$ queries.

If your program makes more than $100$ queries for one set of input data, or makes an invalid query, then the response to the query will be -1. After receiving such a response, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, it may receive any other verdict.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10000$. The interactor in this problem is not adaptive.

Hacks:

To perform a hack, use the following format:

The first line contains a single integer $t$ – the number of test cases.

The description of each test case should consist of two lines. The first line contains the numbers $n$ and $k$ – the length of the chosen array and the length of the query subarray, respectively. The second line contains $n$ numbers $a_1, a_2, \ldots, a_n$ – the array that the jury should choose for this test case.

ExampleInput

2
4 2

6

4

6 6

4

Output

? 1

? 3

! 2

? 1

! 4

Note

In the first test case, the jury has chosen the array $a$ $=$ $[4, 2, 5, 1]$

In the second test case, the jury has chosen the array $a$ $=$ $[5, 7, 1, 3, 3, 7]$

题目大意：这是一个交互式问题。salyg1n给你一个正整数k，并想和你玩一个游戏。他选择了一个由n个整数组成的数组a1, a2, ..., an（1 ≤ ai ≤ 10^9）。你必须输出a1 ⊕ a2 ⊕ ... ⊕ an，其中⊕表示按位异或操作。你可以进行以下类型的查询：

- ? i：对于这个查询，你将得到ai ⊕ ai+1 ⊕ ... ⊕ ai+k-1。此外，在此查询之后，子数组ai, ai+1, ..., ai+k-1将被反转，即选定的数组a将变为：a1, a2, ..., ai-1, ai+k-1, ai+k-2, ..., ai+1, ai, ai+k, ..., an。

你最多可以进行100次查询来回答问题。

输入数据格式：第一行包含一个整数t（1 ≤ t ≤ 1000）——测试用例的数量。

交互过程：你的程序与裁判程序的交互从读取两个正偶数n和k（1 ≤ k ≤ n ≤ k^2 ≤ 2500）开始——所选数组的长度和查询子数组的长度。要找到ai ⊕ ai+1 ⊕ ... ⊕ ai+k-1的值，请以? i的格式打印查询（1 ≤ i ≤ n - k + 1）。然后读取一个整数——对你查询的回答。你最多可以进行100次查询。当你准备好打印答案时，以! x的格式输出。然后继续处理下一个测试用例或如果这是最后一个测试用例则终止程序。打印答案不计入100次查询之一。

如果你的程序对一个输入数据集进行超过100次查询，或者进行无效查询，那么查询的响应将是-1。在收到这样的响应后，你的程序应立即终止以获得错误答案的判决。否则，它可能会收到任何其他判决。

在打印查询后不要忘记输出换行符并刷新输出。否则，你将得到超时限制。为此，请使用：

- 在C++中：fflush(stdout)或cout.flush();
- 在Java中：System.out.flush();
- 在Pascal中：flush(output);
- 在Python中：stdout.flush();
- 查看其他语言的文档。

保证所有测试用例的n之和不超过10000。此问题中的交互器不是自适应的。

hacks：要执行hack，请使用以下格式：

- 第一行包含一个整数t——测试用例的数量。
- 每个测试用例的描述应包含两行。第一行包含数字n和k——所选数组的长度和查询子数组的长度。第二行包含n个数a1, a2, ..., an——裁判应为此测试用例选择的数组。

示例：

输入：
```
2
4 2

6

4

6 6

4
```
输出：
```
? 1

? 3

! 2

? 1

! 4
```
注意：在第一个测试用例中，裁判选择了数组a = [4, 2, 5, 1]。在第二个测试用例中，裁判选择了数组a = [5, 7, 1, 3, 3, 7]。题目大意：这是一个交互式问题。salyg1n给你一个正整数k，并想和你玩一个游戏。他选择了一个由n个整数组成的数组a1, a2, ..., an（1 ≤ ai ≤ 10^9）。你必须输出a1 ⊕ a2 ⊕ ... ⊕ an，其中⊕表示按位异或操作。你可以进行以下类型的查询： - ? i：对于这个查询，你将得到ai ⊕ ai+1 ⊕ ... ⊕ ai+k-1。此外，在此查询之后，子数组ai, ai+1, ..., ai+k-1将被反转，即选定的数组a将变为：a1, a2, ..., ai-1, ai+k-1, ai+k-2, ..., ai+1, ai, ai+k, ..., an。 你最多可以进行100次查询来回答问题。 输入数据格式：第一行包含一个整数t（1 ≤ t ≤ 1000）——测试用例的数量。 交互过程：你的程序与裁判程序的交互从读取两个正偶数n和k（1 ≤ k ≤ n ≤ k^2 ≤ 2500）开始——所选数组的长度和查询子数组的长度。要找到ai ⊕ ai+1 ⊕ ... ⊕ ai+k-1的值，请以? i的格式打印查询（1 ≤ i ≤ n - k + 1）。然后读取一个整数——对你查询的回答。你最多可以进行100次查询。当你准备好打印答案时，以! x的格式输出。然后继续处理下一个测试用例或如果这是最后一个测试用例则终止程序。打印答案不计入100次查询之一。 如果你的程序对一个输入数据集进行超过100次查询，或者进行无效查询，那么查询的响应将是-1。在收到这样的响应后，你的程序应立即终止以获得错误答案的判决。否则，它可能会收到任何其他判决。 在打印查询后不要忘记输出换行符并刷新输出。否则，你将得到超时限制。为此，请使用： - 在C++中：fflush(stdout)或cout.flush(); - 在Java中：System.out.flush(); - 在Pascal中：flush(output); - 在Python中：stdout.flush(); - 查看其他语言的文档。 保证所有测试用例的n之和不超过10000。此问题中的交互器不是自适应的。 hacks：要执行hack，请使用以下格式： - 第一行包含一个整数t——测试用例的数量。 - 每个测试用例的描述应包含两行。第一行包含数字n和k——所选数组的长度和查询子数组的长度。第二行包含n个数a1, a2, ..., an——裁判应为此测试用例选择的数组。 示例： 输入： ``` 2 4 2 6 4 6 6 4 ``` 输出： ``` ? 1 ? 3 ! 2 ? 1 ! 4 ``` 注意：在第一个测试用例中，裁判选择了数组a = [4, 2, 5, 1]。在第二个测试用例中，裁判选择了数组a = [5, 7, 1, 3, 3, 7]。