시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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\).