CF2164G.Pointless Machine

This is an interactive problem.

Madeline is playing with a pointless machine. The pointless machine has a hidden tree of size $n$, and Madeline has to find the edges of the tree by asking the machine.

In a query, Madeline will give the machine a permutation $p$ of $[1,2,\ldots,n]$, and the machine will return a sequence $q_1, q_2, \ldots, q_n$, where $q_i$ is the number of edges of the induced subgraph formed by the vertices ${p_1,p_2,\ldots,p_i}$.

Here, an induced subgraph of a graph $G(V,E)$ formed by a subset of vertices $V' \subseteq V$, is a graph consisting of vertices from this subset and all edges between vertices from subset that are present in original graph $G$.

However, the machine works slowly, so Madeline can only get the results at once after all queries are completed. The memory of this machine is not very large either, so Madeline can only ask $31$ times. She doesn't know how to solve it, so she invited you to help her.

Note that the interactor is non-adaptive. That is, tree is fixed in advance and doesn't change with your queries.

这是一个交互式问题。

玛德琳正在操作一台“毫无意义”的机器。这台“毫无意义”的机器内部隐藏着一棵大小为 $n$ 的树，玛德琳需要通过向该机器提问来找出这棵树的所有边。

在一次查询中，玛德琳将向机器提供一个 $[1,2,\ldots,n]$ 的排列 $p$；机器则返回一个序列 $q_1, q_2, \ldots, q_n$，其中 $q_i$ 表示由顶点集 $\{p_1,p_2,\ldots,p_i\}$ 所诱导的子图中的边数。

此处，图 $G(V,E)$ 关于顶点子集 $V' \subseteq V$ 的诱导子图，是指以 $V'$ 中的顶点为顶点集，并包含所有在原图 $G$ 中两端均属于 $V'$ 的边所构成的图。

然而，该机器运行速度较慢，因此玛德琳必须在提交全部查询之后才能一次性获得所有查询结果。此外，该机器的内存容量也十分有限，因此玛德琳最多只能进行 $31$ 次查询。她不知如何解决这个问题，于是邀请你来协助她。

注意：该交互器是非自适应的（non-adaptive），即隐藏的树在一开始便已固定，不会随你的查询而改变。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The only line of each test case contains a single integer $n$ ($3\le n\le 5\cdot 10^4$) — the size of the tree.

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

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

每个测试用例仅有一行，包含一个整数 $n$（$3\le n\le 5\cdot 10^4$）——表示树的大小。

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

Visualizer link

For the first test case:

• The first query has answer 0 1 2, since only edge $(1, 2)$ is in the induced subgraph formed by ${1,2}$.
• The second query has answer 0 0 2, since no edges are in the induced subgraph formed by ${1,3}$.

For the third test case:

• Edges $(2,3)$, $(3,4)$, and $(4,1)$ are in the induced subgraph formed by ${1,2,3,4}$, so $q_{1,4}=3$.

可视化链接

对于第一个测试用例：

• 第一个查询的答案为 0 1 2，因为由顶点集 $\{1,2\}$ 诱导出的子图中仅包含边 $(1, 2)$。
• 第二个查询的答案为 0 0 2，因为由顶点集 $\{1,3\}$ 诱导出的子图中不包含任何边。

对于第三个测试用例：

• 边 $(2,3)$、$(3,4)$ 和 $(4,1)$ 均属于由顶点集 $\{1,2,3,4\}$ 诱导出的子图，因此 $q_{1,4}=3$。