CF1147E.Rainbow Coins

Carl has $n$ coins of various colors, and he would like to sort them into piles. The coins are labeled $1,2,\ldots,n$, and each coin is exactly one of red, green, or blue. He would like to sort the coins into three different piles so one pile contains all red coins, one pile contains all green coins, and one pile contains all blue coins.

Unfortunately, Carl is colorblind, so this task is impossible for him. Luckily, he has a friend who can take a pair of coins and tell Carl if they are the same color or not. Using his friend, Carl believes he can now sort the coins. The order of the piles doesn't matter, as long as all same colored coins are in the one pile, and no two different colored coins are in the same pile.

His friend will answer questions about multiple pairs of coins in batches, and will answer about all of those pairs in parallel. Each coin should be in at most one pair in each batch. The same coin can appear in different batches.

Carl can use only $7$ batches. Help him find the piles of coins after sorting.

Interaction

You will be given multiple test cases. The first line contains an integer $t$ $(1 \leq t \leq 5$) — the number of test cases.

The first line of each test case contains one integer $n$ ($1 \leq n \leq 10^5$) — the number of coins. If you read in a value of $-1$ here, that means that you printed an invalid answer in the previous case and exit immediately to avoid getting other verdicts.

To ask a question, print "Q $k\ x_1\ y_1\ \ldots\ x_k\ y_k$" ($1 \leq k \leq n/2, 1 \leq x_i,y_i \leq n, x_i \neq y_i$). $k$ denotes the number of pairs in the batch, and $x_i, y_i$ denote the $i$-th pair of coins in the batch. A coin can only appear at most once in a batch. All $x_i$ and $y_i$ should be distinct.

The judge will respond with a bitstring of length $k$, where the $i$-th character is "1" if $x_i$ and $y_i$ are the same color, and "0" otherwise. The judge will respond with $-1$ if you ever ask an invalid query. Make sure to exit immediately to avoid getting other verdicts.

When you are ready to answer, print four lines.

The first line contains "A $k_1\ k_2\ k_3$" ($0 \leq k_1,k_2,k_3$ and $k_1+k_2+k_3 = n$). These denote the sizes of the three piles.

The next line has $k_1$ integers, the labels of the coins in the first pile.

The next line has $k_2$ integers, the labels of the coins in the second pile.

The next line has $k_3$ integers, the labels coins in the third pile.

Each coin must appear in exactly one pile.

You may only ask at most $7$ batches per test case.

After printing a query and the answer do not forget to output 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 documentation for other languages.

Hack Format

To hack, use the following format. Note that you can only hack with one test case.

The first line should contain a single integer $t$ ($t=1$).

The second line should contain a single string $s$ consisting of only the characters "R", "G", "B" ($1 \leq |s| \leq 10^5$). The $i$-th character in this string represents the color of the $i$-th coin.

卡尔有 $n$ 枚颜色各异的硬币，他希望将这些硬币分成三堆。硬币编号为 $1,2,\ldots,n$，每枚硬币恰好是红色、绿色或蓝色中的一种。他希望将硬币分为三堆，使得其中一堆包含所有红色硬币，一堆包含所有绿色硬币，另一堆包含所有蓝色硬币。

不幸的是，卡尔是色盲，因此这项任务对他而言无法完成。幸运的是，他有一位朋友，可以对任意一对硬币判断它们是否颜色相同。借助这位朋友，卡尔相信自己现在能够完成排序任务。堆的顺序无关紧要，只要同色硬币全部归入同一堆，且不同颜色的硬币不混在同一堆中即可。

他的朋友以“批”（batch）的形式回答问题：每次可同时询问多对硬币，朋友将并行地对这批中的所有对给出回答。在每一批中，每枚硬币最多只能出现在一个配对中；但同一枚硬币可在不同批次中重复出现。

卡尔最多只能使用 $7$ 批查询。请帮助他在排序后确定这三堆硬币分别包含哪些硬币。

交互方式

你将收到多个测试用例。第一行是一个整数 $t$（$1 \leq t \leq 5$），表示测试用例的数量。

每个测试用例的第一行是一个整数 $n$（$1 \leq n \leq 10^5$），表示硬币数量。若此处读入的值为 $-1$，说明你在上一测试用例中输出了非法答案，请立即退出，以避免收到其他判定结果。

要提出一个问题，请输出格式为 "Q $k\ x_1\ y_1\ \ldots\ x_k\ y_k$" 的一行（其中 $1 \leq k \leq n/2$，$1 \leq x_i,y_i \leq n$，且 $x_i \neq y_i$）。$k$ 表示该批次中配对的数量，$x_i, y_i$ 表示该批次中第 $i$ 对硬币。每枚硬币在同一批次中至多出现一次。所有 $x_i$ 和 $y_i$ 必须互不相同。

评测程序将返回一个长度为 $k$ 的比特串（bitstring），其中第 $i$ 个字符为 "1" 表示硬币 $x_i$ 与 $y_i$ 颜色相同，为 "0" 则表示颜色不同。若你提出任何非法查询，评测程序将返回 $-1$。此时请确保立即退出，以免收到其他判定结果。

当你准备好提交最终答案时，请输出四行：

第一行为 "A $k_1\ k_2\ k_3$"（其中 $0 \leq k_1,k_2,k_3$ 且 $k_1+k_2+k_3 = n$），表示三堆的大小。

第二行为 $k_1$ 个整数，表示第一堆中硬币的编号。

第三行为 $k_2$ 个整数，表示第二堆中硬币的编号。

第四行为 $k_3$ 个整数，表示第三堆中硬币的编号。

每枚硬币必须且仅能出现在一堆中。

每个测试用例中，你最多只能发起 $7$ 批查询。

每次输出查询或答案后，请务必输出换行符并刷新输出缓冲区，否则你会收到 “Idleness limit exceeded”。为此，请使用以下方式：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 stdout.flush()；
• 其他语言请查阅相应文档。

Hack 格式

用于 hack 时，请采用如下格式。注意：你只能对单个测试用例进行 hack。

第一行应为一个整数 $t$（$t = 1$）。

第二行应为一个仅由字符 "R"、"G"、"B" 组成的字符串 $s$（$1 \leq |s| \leq 10^5$）。该字符串中第 $i$ 个字符表示第 $i$ 枚硬币的颜色。

In the example, there are three test cases.

In the first test case, there are three coins. We ask about the pairs $(1,2)$, $(2,3)$, and $(1,3)$ in different batches and get that they are all the same color. Thus, we know all the coins are the same color, so we can put them all in one pile. Note that some piles can be empty and those are denoted with an empty line.

In the second test case, there are three coins again. This time, we only get that $(1,3)$ are the same and $(1,2)$ and $(2,3)$ are different. So, one possible scenario is that coins $1$ and $3$ are red and coin $2$ is green.

In the last case, there are $6$ coins. The case shows how to ask and receive answers for multiple pairs in one batch.

在该示例中，共有三个测试用例。

在第一个测试用例中，共有三枚硬币。我们在不同的批次中依次询问了三对硬币 $(1,2)$、$(2,3)$ 和 $(1,3)$，并得知它们的颜色均相同。因此，我们可推断所有硬币颜色一致，于是可将它们全部放入同一堆中。注意：某些堆可以为空，空堆以空行表示。

在第二个测试用例中，同样有三枚硬币。但此次我们仅得知 $(1,3)$ 颜色相同，而 $(1,2)$ 和 $(2,3)$ 颜色不同。因此，一种可能的情形是：硬币 $1$ 和 $3$ 为红色，硬币 $2$ 为绿色。

在最后一个测试用例中，共有 $6$ 枚硬币。该用例展示了如何在单个批次中同时询问多对硬币，并接收其答案。