3F. Guessing the Permutation via Median

This is an interactive problem. After each printed line, flush the output.

You are given an integer $n$ and an unknown permutation $p$ of $\{1,2,\dots,n\}$. You must determine the entire permutation by asking at most $\left\lfloor \frac{5n}{4} \right\rfloor$ queries.

In one query, you choose an odd integer $k$ and then give $k$ distinct indices $i_1,i_2,\dots,i_k$ in the order you want. The given indices are not necessarily sorted.

The judge answers with two values:

• Median index $m$:
  Consider the set $\{p_{i_1},p_{i_2},\dots,p_{i_k}\}$. Since $k$ is odd, the median value is the $\frac{k+1}{2}$-th smallest value. You receive an index $m \in \{i_1,i_2,\dots,i_k\}$ such that $p_m$ equals this median value.
• Inversion parity $s$:
  Consider the sequence $(p_{i_1}, p_{i_2}, \dots, p_{i_k})$ in the same order as the indices you provided. Let $inv$ be the number of inversions in this sequence, meaning the number of pairs $(x,y)$ with $1 \le x < y \le k$ and $p_{i_x} > p_{i_y}$. The judge returns $s = inv \bmod 2$.

Constraints

• $1 \le t \le 50$
• $3 \le n \le 100$

Under these constraints, it is guaranteed that there exists a strategy that finds the permutation within the query limit.

The whole interaction is repeated for $t$ test cases.