4341. [国家集训队 2026]奇迹

【题目背景】

日复一日的机械运作着，面前三色荧光单调排列，四周充满黑暗的压抑。将来更是一眼到头的坏结局。  

完全地虚无。“充实”的机械耕耘无法撬动贫瘠的思想土壤，尽管所思所念仍然在不断创造“奇迹”，且毫无意义。  

我所希望的奇迹究竟是什么？我认为应该是一个小概率事件的产生，对若干部分造成了影响，这些部分又相互联系，进而获得了宏观上的巨变。  

一月复一月，黑暗在逐渐侵蚀希望。在几乎必然的绝望之下，我也只能祈望奇迹的光亮再次来临。

【题目描述】

冬雀发现，许多看似毫无关联的事物之间，总会产生一些奇迹般的联系。  

一个奇迹可以使用 $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$，输出任意一个即可。

【样例输入】

3
1
2 0 2
1 0 0
2 2 0
2
0 0 1 1 1 2 0 0 2
1 0 0 2 1 0 1 2 2
10 10 6 8 5 2 8 9 5
3
0 0 0 1 0 1 1 1 1 2 2 2 2 1 0 2 2 0 0 0 1 1 0 2 1 0 2
2 2 1 2 2 0 1 0 1 1 1 0 1 1 1 0 1 1 0 2 0 0 2 1 1 1 0
70 0 81 0 0 0 124 0 105 0 0 0 0 0 0 0 0 0 11 0 101 0 0 0 25 0 108

【样例输出】

1 2 0 0 0 0 0 0 0
1 1 1 0 2 0 0 1 2
0 2 2 0 0 0 2 2 2

【数据规模与约定】

对于所有测试数据，均有：  

- $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$ 满足条件。

特殊性质 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\}$。

【提示】  

本题输入规模较大，请使用较为快速的输入方式。

【来源】

IOI2026中国国家集训队集中培训 Day2 Task3