시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 512 MB1312787.500%

## 문제

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$$.