3진법 Mex

$\text{mex}(a, b)$는 $a$와도 $b$와도 같지 않은 가장 작은 음이 아닌 정수를 뜻한다. 항상 $\text{mex}(a, b) < 3$이므로 3진법 mex를 정의할 수 있다. $a$와 $b$를 3진법으로 나타내면 다음과 같다.

$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}$을 공백으로 구분하여 출력한다.

참고로 $3^{12} = 531441$이다.