AT_agc074_c.[AGC074C] PORALIS

给定一个正整数 $N$。

请输出一对非负整数序列 $P=(P_1, P_2, \dots, P_N)$，$A=(A_1, A_2, \dots, A_N)$，使其满足以下所有条件：

• $0 \leq P_i < 2^{30}\ (1 \leq i \leq N)$
• $0 \leq A_i < 2^{30}\ (1 \leq i \leq N)$
• 对于每个 $i\ (1 \leq i \leq N)$，$ (P_1_\mathrm{OR}A_i, P_2_\mathrm{OR}A_i, \dots, P_N_\mathrm{OR}A_i) $ 的最长严格递增子序列的长度为 $i$。
  • 其中 $\mathrm{OR}$ 表示按位或运算。

可以证明，在本题的限制条件下，至少存在一组满足条件的 $P, A$。

请你解决 $T$ 组测试用例。

::::info[什么是按位或（$\mathrm{OR}$）？]

按位或是对非负整数 $A, B$ 的二进制表示，在每一位上只要有一个数字为 $1$，结果的那一位就为 $1$，否则为 $0$。

例如，$3\ \mathrm{OR}\ 5 = 7$（即二进制 $011\ \mathrm{OR}\ 101 = 111$）。

::::

从标准输入读取数据，格式如下：

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

每组测试用例为：

$N$

请按顺序输出 $\mathrm{case}_1, \mathrm{case}_2, \dots, \mathrm{case}_T$ 的答案。

对于每组测试用例，输出一组如下格式的解：

$P_1$ $P_2$ $\ldots$ $P_N$ $A_1$ $A_2$ $\ldots$ $A_N$

如果有多组解，任意一组均为正确答案。

样例解释 1

对于第一组测试用例，样例输出为 $P = (3, 14, 5),\ A = (13, 2, 10)$。

• $(3~\mathrm{OR}~13, 14~\mathrm{OR}~13, 5~\mathrm{OR}~13) = (15, 15, 13)$ 的最长严格递增子序列之一为 $(13)$，其长度为 $1$。
• $(3~\mathrm{OR}~2, 14~\mathrm{OR}~2, 5~\mathrm{OR}~2) = (3, 14, 7)$ 的最长严格递增子序列为 $(3, 7)$，长度为 $2$。
• $(3~\mathrm{OR}~10, 14~\mathrm{OR}~10, 5~\mathrm{OR}~10) = (11, 14, 15)$ 的最长严格递增子序列为 $(11, 14, 15)$，长度为 $3$。

由此可知，$P = (3, 14, 5),\ A = (13, 2, 10)$ 满足条件。

数据范围

• $1 \leq T$
• $1 \leq N \leq 1024$
• 单个输入中的 $N$ 之和不超过 $200000$。
• 单个输入中的 $N^2$ 之和不超过 $1024^2$。
• 所有输入值均为整数。

由 ChatGPT 5 翻译