#215046. [北大集训 2025] 奇迹

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

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

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

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

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

一个奇迹可以使用 的矩阵 来表示，其中对于所有 ，。

对于 ，设 的三进制表示分别为 , （不足 位的用前导 0 补齐），定义 ，其中 ()。

若 三个长度为 的非负整数序列之间，蕴含一个奇迹 ，那么对于所有 ，均有 ，其中 。

冬雀希望他能够找到一些奇迹，来解释这些看似毫无关联的事物之间的联系。

尽管这对于任意三个序列难以进行，但它仍然可以轻易的找到两个随机的序列 ，并通过一些神奇的操作，给出序列 ，使得 三者内蕴含一个奇迹。

但是现在唯一的问题在于，它不知道奇迹是什么，所以它想让你找出一个可能的答案。

形式化地，给定三个长度为 的非负整数序列，其中对于所有 ， 均在在 中独立均匀随机生成，且存在 满足对于所有 ，均有 。你需要求出任意一个可能的 。

从标准输入读入数据。

本题包含多组测试数据。

输入的第一行包含一个正整数 ，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含一个正整数 。
• 第二行包含 个非负整数 。
• 第三行包含 个非负整数 。
• 第四行包含 个非负整数 。

输出到标准输出。

对于每组测试数据，输出一行九个非负整数 ，表示一个可能的 。若有多个满足条件的 ，输出任意一个即可。

样例输入 1

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

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

【子任务】

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

• ；
• ；
• 对于所有 ， 均在 中独立均匀随机生成；
• 对于所有 ， 均在 中独立均匀随机生成；
• 对于所有 ，；
• 存在至少一个 满足条件。

特殊性质 A：存在 满足 。

特殊性质 B：存在 满足 。

特殊性质 C：存在 满足 。

特殊性质 D：存在 满足对于所有 ，均有 ；

特殊性质 E：对于所有 ，均有 。

特殊性质 F：对于所有 ，均有 。

【提示】

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