CF1867E2.Salyg1n and Array (hard version)

This is the hard 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 57 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 $57$ queries to answer the problem.

这是该问题的困难版本。两个版本的唯一区别在于查询次数限制。在本版本中，你最多只能进行 57 次查询。仅当该问题的两个版本均被解决时，才允许进行 hack。

这是一个交互式问题！

salyg1n 给了你一个正整数 $k$，并想和你玩一个游戏。他选择了一个由 $n$ 个整数组成的数组 $a_1, a_2, \ldots, a_n$（其中 $1 \leq a_i \leq 10^9$）。你需要输出 $a_1 \oplus a_2 \oplus \ldots \oplus a_n$，其中 $\oplus$ 表示按位异或运算。你可以进行如下类型的查询：

• $?$ $i$：对于该查询，你将收到 $a_i \oplus a_{i + 1} \oplus \ldots \oplus a_{i + k - 1}$ 的值。此外，在该查询之后，子数组 $a_i, a_{i + 1}, \ldots, a_{i + k - 1}$ 将被翻转，即原数组 $a$ 将变为：$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$。

你最多只能进行 $57$ 次查询来解答该问题。

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

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）——测试用例的数量。

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]$

在第一个测试用例中，出题人选择的数组为 $a$ $=$ $[4, 2, 5, 1]$。

在第二个测试用例中，出题人选择的数组为 $a$ $=$ $[5, 7, 1, 3, 3, 7]$。