CF1617D2.Too Many Impostors (hard version)

This is an interactive problem. The only difference between the easy and hard version is the limit on number of questions.

There are $n$ players labelled from $1$ to $n$. It is guaranteed that $n$ is a multiple of $3$.

Among them, there are $k$ impostors and $n-k$ crewmates. The number of impostors, $k$, is not given to you. It is guaranteed that $\frac{n}{3} \lt k \lt \frac{2n}{3}$.

In each question, you can choose three distinct integers $a$, $b$, $c$ ($1 \le a, b, c \le n$) and ask: "Among the players labelled $a$, $b$ and $c$, are there more impostors or more crewmates?" You will be given the integer $0$ if there are more impostors than crewmates, and $1$ otherwise.

Find the number of impostors $k$ and the indices of players that are impostors after asking at most $n+6$ questions.

The jury is adaptive, which means the indices of impostors may not be fixed beforehand and can depend on your questions. It is guaranteed that there is at least one set of impostors which fulfills the constraints and the answers to your questions at any time.

这是一个交互式问题。简单版本与困难版本的唯一区别在于提问次数的限制。

有 $n$ 名玩家，编号从 $1$ 到 $n$。保证 $n$ 是 $3$ 的倍数。

其中，有 $k$ 名伪装者（impostors）和 $n-k$ 名船员（crewmates）。伪装者的数量 $k$ 不会提供给你。保证 $\frac{n}{3} \lt k \lt \frac{2n}{3}$。

每次提问时，你可以选择三个互不相同的整数 $a$、$b$、$c$（满足 $1 \le a, b, c \le n$），并提出如下问题：“在编号为 $a$、$b$ 和 $c$ 的玩家中，是伪装者更多，还是船员更多？” 若伪装者人数多于船员人数，则你会收到整数 $0$；否则（即船员人数不少于伪装者人数），你会收到整数 $1$。

你需要在至多 $n+6$ 次提问内，确定伪装者人数 $k$ 以及所有伪装者的编号。

评测机是自适应的（adaptive），这意味着伪装者的编号并非预先固定，而可能依赖于你所提出的提问。但保证：在任意时刻，总存在至少一组满足约束条件的伪装者集合，使其与你已获得的所有回答一致。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first and only line of each test case contains a single integer $n$ ($6 \le n \lt 10^4$, $n$ is a multiple of $3$) — the number of players.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^4$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是测试用例的描述。

每个测试用例仅有一行，包含一个整数 $n$（$6 \le n \lt 10^4$，且 $n$ 是 $3$ 的倍数）—— 表示玩家数量。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^4$。

Explanation for example interaction (note that this example only exists to demonstrate the interaction procedure and does not provide any hint for the solution):

For the first test case:

Question "? 1 2 3" returns $0$, so there are more impostors than crewmates among players $1$, $2$ and $3$.

Question "? 3 4 5" returns $1$, so there are more crewmates than impostors among players $3$, $4$ and $5$.

Outputting "! 3 4 1 2" means that one has found all the impostors, by some miracle. There are $k = 3$ impostors. The players who are impostors are players $4$, $1$ and $2$.

For the second test case:

Question "? 7 1 9" returns $1$, so there are more crewmates than impostors among players $7$, $1$ and $9$.

Outputting "! 4 2 3 6 8" means that one has found all the impostors, by some miracle. There are $k = 4$ impostors. The players who are impostors are players $2$, $3$, $6$ and $8$.

示例交互说明（注意：该示例仅用于演示交互流程，不提供任何解题提示）：

对于第一个测试用例：

询问 “? 1 2 3” 返回 $0$，说明玩家 $1$、$2$ 和 $3$ 中，冒名顶替者（impostor）人数多于船员（crewmate）人数。

询问 “? 3 4 5” 返回 $1$，说明玩家 $3$、$4$ 和 $5$ 中，船员人数多于冒名顶替者人数。

输出 “! 3 4 1 2” 表示某人奇迹般地找出了全部冒名顶替者。此时冒名顶替者人数为 $k = 3$，冒名顶替者为玩家 $4$、$1$ 和 $2$。

对于第二个测试用例：

询问 “? 7 1 9” 返回 $1$，说明玩家 $7$、$1$ 和 $9$ 中，船员人数多于冒名顶替者人数。

输出 “! 4 2 3 6 8” 表示某人奇迹般地找出了全部冒名顶替者。此时冒名顶替者人数为 $k = 4$，冒名顶替者为玩家 $2$、$3$、$6$ 和 $8$。