18536번 - Tritwise Mex 다국어

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.

For reference: \(3^{12} = 531 441\).