시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 12 11 6 85.714%

## 문제

Let us denote $\text{mex}(a, b)$ (minimum excludant) as the minimum non-negative integer which is neither equal to $a$ nor equal to $b$. It always holds that $\text{mex}(a, b)$ < 3, thus we can define tritwise $\text{mex}$. If we write $a$ and $b$ in ternary notation:

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

where $a_i$ and $b_i$ are integers from 0 to 2, we define $\text{mex}_3$ as follows:

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

You are given two sequences $a_0, \dots, a_{3^k-1}$ and $b_0, \dots, b_{3^k-1}$. You have to compute the sequence $c_0, \dots, c_{3^k-1}$:

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

## 입력

The first line of input contains a single integer $k$ ($1 \le k \le 12$).

The second line of input contains $3^k$ integers $a_0, \dots, a_{3^k-1}$ ($0 \le a_i ≤ 10^3$).

The third line of input contains $3^k$ integers $b_0, \dots, b_{3^k-1}$ ($0 \le b_i ≤ 10^3$).

## 출력

Output $3^k$ integers $c_0, \dots, c_{3^k-1}$ separated by spaces.

## 예제 입력 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


## 노트

For reference: $3^{12} = 531 441$.