Dongque has discovered that there are often miraculous connections between many seemingly unrelated things.

A miracle can be represented by a $3 \times 3$ matrix $op$, where for all $i, j \in \{0, 1, 2\}$, $op(i, j) \in \{0, 1, 2\}$.

For $0 \le i, j < 3^n$, let the ternary representations of $i$ and $j$ be $(i_{n-1} \dots i_1 i_0)_3$ and $(j_{n-1} \dots j_1 j_0)_3$ respectively (padded with leading zeros to length $n$). We define $i \oplus j = (k_{n-1} \dots k_1 k_0)_3$, where $k_l = op(i_l, j_l)$ for $0 \le l < n$.

If three non-negative integer sequences $A, B, C$ of length $3^n$ contain a miracle $op$, then for all $0 \le i < 3^n$, we have $C_i = \left( \sum_{j \oplus k = i} A_j \times B_k \right) \pmod p$, where $p = 998, 244, 353$.

Dongque hopes to find some miracles to explain the connections between these seemingly unrelated things. Although this is difficult for arbitrary sequences, it is easy to find two random sequences $A, B$ and, through some magical operations, produce a sequence $C$ such that $A, B, C$ contain a miracle.

The only problem now is that he does not know what the miracle is, so he wants you to find a possible answer.

Formally, given three non-negative integer sequences of length $3^n$, where for all $0 \le i < 3^n$, $A_i, B_i$ are generated independently and uniformly at random in $[0, p)$, and there exists an $op$ such that for all $0 \le i < 3^n$, $C_i = \left( \sum_{j \oplus k = i} A_j \times B_k \right) \pmod p$. You need to find any one possible $op$.

Input

The input is read from standard input. This problem contains multiple test cases. The first line contains a positive integer $t$, representing the number of test cases. For each test case: The first line contains a positive integer $n$. The second line contains $3^n$ non-negative integers $A_0, A_1, \dots, A_{3^n-1}$. The third line contains $3^n$ non-negative integers $B_0, B_1, \dots, B_{3^n-1}$. The fourth line contains $3^n$ non-negative integers $C_0, C_1, \dots, C_{3^n-1}$.

Output

Output to standard output. For each test case, output one line containing nine non-negative integers $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)$, representing a possible $op$. If there are multiple $op$ that satisfy the conditions, output any one of them.

Examples

Input 1

1
3
2 1 2 0 2 1 0 0 2 2 0 2 2 0 0 1 1 1 2 0 0 2 1 0 0 2 1
0 1 2 2 1 0 1 2 2 1 0 1 2 2 1 0 1 2 2 1 0 1 2 2 1 0 1
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

Output 1

1 2 0 0 0 0 0 0 0

Subtasks

For all test cases: $1 \le t \le 16$; $1 \le n \le 10$; For all $0 \le i < 3^n$, $A_i$ are generated independently and uniformly at random in $[0, p)$; For all $0 \le i < 3^n$, $B_i$ are generated independently and uniformly at random in $[0, p)$; For all $0 \le i < 3^n$, $0 \le C_i < p$; There exists at least one $op$ satisfying the conditions.

Special Property A: There exist $x, y \in \{0, 1, 2\}$ such that $op = \begin{pmatrix} x & x & x \\ x & x & x \\ y & y & y \end{pmatrix}$.

Special Property B: There exist $x, y, z \in \{0, 1, 2\}$ such that $op = \begin{pmatrix} x & x & x \\ y & y & y \\ z & z & z \end{pmatrix}$.

Special Property C: There exist $x, y \in \{0, 1, 2\}$ such that $op = \begin{pmatrix} x & x & y \\ x & x & y \\ y & y & y \end{pmatrix}$.

Special Property D: There exist $a, b \in \{0, 1, 2\}$ such that for all $i, j \in \{0, 1, 2\}$, $op(i, j) = (ai + bj) \pmod 3$.

Special Property E: For all $i \in \{0, 1, 2\}$, $op(i, 0) = op(i, 1)$.

Special Property F: For all $i, j \in \{0, 1, 2\}$, $op(i, j) \in \{0, 1\}$.

Note

The input size for this problem is large; please use fast I/O methods.