Yi is the OIer that Ou admires the most, not only because Yi is highly skilled, but also because Ou often had the chance to see him. That period was the most memorable time for Ou; she once thought everything would go so smoothly. Until one summer, on a day of heavy rain, raindrops pattered against the glass. After that, everything ceased to exist. Ou knew where Yi had gone, but she did not want to know.

One day later, she discovered an un-erased draft on the blackboard. She finally found some fragments of happy times from a certain day: back then, Ou threw a problem at Yi, asking for a high-dimensional "convolution" of two ternary numbers. However, she forgot the specific method, so she casually mentioned a bitwise $\text{mex}$ operation table that seemed to have no properties. Yi provided a solution. But that solution was still too specific. Then she asked directly for a method without any properties. And then... she couldn't remember.

After that heavy rain, she had lost all memories of him, and only now were some fragments returning. Ou now believes that the Yi of that time must have provided a more excellent solution for a randomly generated operation table, because it "had no properties." Perhaps with just a little modification... the memories from the end of that day could be retrieved. That would be enough.

Formal Problem Statement

The problem provides a $3 \times 3$ operation table $\text{op}$, where the array indices and the range of values are both in $[0, 2]$.

Let $v_3(a)_b$ be the $b$-th digit of $a$ in its ternary representation (where the least significant digit is $0$).

For two numbers $0 \le i, j < 3^n$, define $i \, \text{op} \, j$ such that: $$ v_3(i \, \text{op} \, j)_k = \text{op}_{v_3(i)_k, v_3(j)_k} \quad (0 \le k < n) $$

Two arrays $A_i$ and $B_i$ are also given, with values as integers in $[0, 9]$. For each $x$, calculate: $$ C_x = \sum_{i \, op \, j = x} A_i B_j $$

Specifically, the operation table is generated randomly, and each subtask has exactly five test cases (except for the last one, which has ten).

Input

The first three lines each contain three integers, where the $j$-th number in the $i$-th line represents $\text{op}_{i-1, j-1}$.

The next line contains an integer $n$ representing the dimension.

The next line contains $3^n$ integers, where the $i$-th integer represents $A_{i-1}$.

The next line contains $3^n$ integers, where the $i$-th integer represents $B_{i-1}$. The numbers are separated by spaces.

Output

A single line containing $3^n$ integers, where the $i$-th integer represents $C_{i-1}$.

Examples

Input 1

1 2 1
1 2 0
2 1 0
1
5 7 8
9 8 4

Output 1

60 192 168

Input 2

0 0 1
0 2 0
2 2 1
2
8 1 1 8 1 3 2 5 3
9 0 6 3 5 3 4 9 6

Output 2

358 213 97 190 84 106 209 78 105

Note: Examples 1 and 2 only satisfy the properties of Subtask 5 and are generated using its data generator. Examples 3 through 8 correspond to the other subtasks (excluding Subtask 5) and are generated using the same data generators as those respective subtasks.

Constraints

• Subtask 1 (5 points): $\text{op}_{i, j} = (i + j) \bmod 3$
• Subtask 2 (5 points): $\text{op}_{i, j} = \text{mex}(i, j)$, where $\text{mex}(i, j)$ is the smallest non-negative integer not equal to $i$ or $j$
• Subtask 3 (20 points): $\text{op}_{i, j} \in \{0, 1\}$, and for any two rows, each bit is either entirely the same or entirely different
• Subtask 4 (30 points): $\text{op}_{i, j} \in \{0, 1\}$
• Subtask 5 (10 points): $n \le 9$
• Subtask 6 (10 points): $n = 10$, depends on Subtask 5
• Subtask 7 (20 points): $n = 11$, depends on Subtask 6

For $100\%$ of the data, it is guaranteed that $1 \le n \le 11$, and $\text{op}_{i, j}$ is chosen uniformly at random from all possible configurations satisfying the subtask requirements. It is guaranteed that $0 \le A_i, B_i \le 10$ and are integers. There are exactly $5$ test cases for each subtask except for the last one, which has $10$ test cases.