P14025 [ICPC 2024 Nanjing R] P ⊕ Q = R

Alice wants to train herself to solve constructive problems. So her friend Kei, a super artificial intelligence, generates the following problem for Alice. Given an integer $n$, construct two permutations $P = p_1,p_2,\cdots,p_n$ and $Q = q_1,q_2,\cdots,q_n$ of $0,1,\dots,(n-1)$, such that the sequence $R = r_1,r_2,\cdots,r_n$ is still a permutation of $0,1,\dots,(n-1)$, where $r_i = p_i \oplus q_i$. Here $x \oplus y $ means the bitwise exclusive-or of $x$ and $y$. Alice solves this problem with her powerful calculating ability and she decides to share this problem with you. Can you solve it?

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first and only line contains one integer $n$ ($1 \leq n \leq 2 \times 10^5$) indicating the length of the permutation. It is guaranteed that the sum of $n$ of all test cases will not exceed $2 \times 10^6$.

For each test case: If there exist two permutations satisfying the constraint, first output $\texttt{Yes}$ in one line. Then output a second line containing $n$ integers $p_1,p_2,\dots,p_n$ separated by a space. Finally output a third line containing $n$ integers $q_1,q_2,\dots,q_n$ separated by a space. If there are multiple valid answers, you can output any of them. If there do not exist two permutations satisfying the constraint, just output $\texttt{No}$ in one line.

For the second test case, $R = \{ 3,0,1,2\}$ is still a permutation of $0,1,2,3$. :::align{center}  :::