我们记 $\text{mex}(a, b)$（最小排斥值）为既不等于 $a$ 也不等于 $b$ 的最小非负整数。由于 $\text{mex}(a, b) < 3$ 总是成立，因此我们可以定义三进制下的 $\text{mex}$。如果我们用三进制表示 $a$ 和 $b$：

$$a = \sum_{i=0}^{k-1} a_i \cdot 3^i, \quad b = \sum_{i=0}^{k-1} b_i \cdot 3^i$$

其中 $a_i$ 和 $b_i$ 是 $0$ 到 $2$ 之间的整数，我们定义 $\text{mex}_3$ 如下：

$$\text{mex}_3(a, b) = \sum_{i=0}^{k-1} \text{mex}(a_i, b_i) \cdot 3^i$$

给定两个序列 $a_0, \dots, a_{3^k-1}$ 和 $b_0, \dots, b_{3^k-1}$，你需要计算序列 $c_0, \dots, c_{3^k-1}$，其中：

$$c_k = \sum_{\text{mex}_3(i, j)=k} a_i \cdot b_j$$

输入格式

第一行包含一个整数 $k$ ($1 \le k \le 12$)。 第二行包含 $3^k$ 个整数 $a_0, \dots, a_{3^k-1}$ ($0 \le a_i \le 10^3$)。 第三行包含 $3^k$ 个整数 $b_0, \dots, b_{3^k-1}$ ($0 \le b_i \le 10^3$)。

输出格式

输出 $3^k$ 个整数 $c_0, \dots, c_{3^k-1}$，以空格分隔。

样例

样例输入 1

1
1 1 1
1 1 1

样例输出 1

4 3 2

样例输入 2

2
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1

样例输出 2

16 12 8 12 9 6 8 6 4

说明

参考：$3^{12} = 531\,441$。