P14930 [北大集训 2025] 奇迹

日复一日的机械运作着，面前三色荧光单调排列，四周充满黑暗的压抑。将来更是一眼到头的坏结局。 完全地虚无。“充实”的机械耕耘无法撬动贫瘠的思想土壤，尽管所思所念仍然在不断创造“奇迹”，且毫无意义。 我所希望的奇迹究竟是什么？我认为应该是一个小概率事件的产生，对若干部分造成了影响，这些部分又相互联系，进而获得了宏观上的巨变。 一月复一月，黑暗在逐渐侵蚀希望。在几乎必然的绝望之下，我也只能祈望奇迹的光亮再次来临。

冬雀发现，许多看似毫无关联的事物之间，总会产生一些奇迹般的联系。 一个奇迹可以使用 $3 \times 3$ 的矩阵 $op$ 来表示，其中对于所有 $i, j \in \{0, 1, 2\}$，$op(i, j) \in \{0, 1, 2\}$。 对于 $0 \le i, j < 3^n$，设 $i, j$ 的三进制表示分别为 $(i_{n-1} \dots i_1 i_0)_3$, $(j_{n-1} \dots j_1 j_0)_3$（不足 $n$ 位的用前导 0 补齐），定义 $i \oplus j = (k_{n-1} \dots k_1 k_0)_3$，其中 $k_l = op(i_l, j_l)$ ($0 \le l < n$)。 若 $A, B, C$ 三个长度为 $3^n$ 的非负整数序列之间，蕴含一个奇迹 $op$，那么对于所有 $0 \le i < 3^n$，均有 $C_i = \left(\sum_{j \oplus k = i} A_j \times B_k\right) \mod p$，其中 $p = 998,244,353$。 冬雀希望他能够找到一些奇迹，来解释这些看似毫无关联的事物之间的联系。 尽管这对于任意三个序列难以进行，但它仍然可以轻易的找到两个**随机**的序列 $A, B$，并通过一些神奇的操作，给出序列 $C$，使得 $A, B, C$ 三者内蕴含一个奇迹。 但是现在唯一的问题在于，它不知道奇迹是什么，所以它想让你找出一个可能的答案。 形式化地，给定三个长度为 $3^n$ 的非负整数序列，其中对于所有 $0 \le i < 3^n$，$A_i, B_i$ 均在在 $[0, p)$ 中独立均匀随机生成，且存在 $op$ 满足对于所有 $0 \le i < 3^n$，均有 $C_i = \left(\sum_{j \oplus k = i} A_j \times B_k\right) \mod p$。你需要求出任意一个可能的 $op$。

从标准输入读入数据。 本题包含多组测试数据。 输入的第一行包含一个正整数 $t$，表示测试数据组数。 接下来依次输入每组测试数据，对于每组测试数据： - 第一行包含一个正整数 $n$。 - 第二行包含 $3^n$ 个非负整数 $A_0, A_1, \dots, A_{3^n - 1}$。 - 第三行包含 $3^n$ 个非负整数 $B_0, B_1, \dots, B_{3^n - 1}$。 - 第四行包含 $3^n$ 个非负整数 $C_0, C_1, \dots, C_{3^n - 1}$。

输出到标准输出。 对于每组测试数据，输出一行九个非负整数 $op(0,0), op(0,1), op(0,2), op(1,0), op(1,1), op(1,2), op(2,0), op(2,1), op(2,2)$，表示一个可能的 $op$。若有多个满足条件的 $op$，输出任意一个即可。

### 【子任务】 对于所有测试数据，均有： - $1 \le t \le 16$； - $1 \le n \le 10$； - 对于所有 $0 \le i < 3^n$，$A_i$ 均在 $[0, p)$ 中独立均匀随机生成； - 对于所有 $0 \le i < 3^n$，$B_i$ 均在 $[0, p)$ 中独立均匀随机生成； - 对于所有 $0 \le i < 3^n$，$0 \le C_i < p$； - 存在至少一个 $op$ 满足条件。 | 测试点编号 | $n \le$ | 特殊性质 | |:-:|:-:|:-:| | 1 | 1 | 无 | | 2 | 3 | 无 | | 3 | 5 | 无 | | 4 | 10 | A | | 5 | 10 | B | | 6 | 10 | C | | 7 | 10 | D | | 8 | 10 | E | | 9 | 10 | F | | 10 | 10 | 无 | 特殊性质 A：存在 $x, y \in \{0,1,2\}$ 满足 $op = \begin{pmatrix} x & x & x \\ x & x & x \\ y & y & y \end{pmatrix}$。 特殊性质 B：存在 $x, y, z \in \{0,1,2\}$ 满足 $op = \begin{pmatrix} x & x & x \\ y & y & y \\ z & z & z \end{pmatrix}$。 特殊性质 C：存在 $x, y \in \{0,1,2\}$ 满足 $op = \begin{pmatrix} x & x & y \\ x & x & y \\ y & y & y \end{pmatrix}$。 特殊性质 D：存在 $a, b \in \{0,1,2\}$ 满足对于所有 $i, j \in \{0,1,2\}$，均有 $op(i,j) = (ai + bj) \bmod 3$； 特殊性质 E：对于所有 $i \in \{0,1,2\}$，均有 $op(i,0) = op(i,1)$。 特殊性质 F：对于所有 $i, j \in \{0,1,2\}$，均有 $op(i,j) \in \{0,1\}$。 ### 【提示】 本题输入规模较大，请使用较为快速的输入方式。