405819: GYM102129 A 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 mex. If we write $$$a$$$ and $$$b$$$ in ternary notation: $$$$$$a = \sum\limits_{i=0}^{k-1}a_i \cdot 3^i,~~b=\sum\limits_{i=0}^{k-1} b_i \cdot 3^i\text{,}$$$$$$ where $$$a_i$$$ and $$$b_i$$$ are integers from $$$0$$$ to $$$2$$$, we define $$$\mathrm{mex}_3$$$ as follows: $$$$$$\mathrm{mex}_3(a, b) = \sum\limits_{i=0}^{k-1}\mathrm{mex}(a_i,b_i) \cdot 3^i\text{.}$$$$$$ 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\limits_{\mathrm{mex}_3(i,j)=k}a_i \cdot b_j\text{.}$$$$$$

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

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

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

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

1
1 1 1
1 1 1

4 3 2 

2
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1

16 12 8 12 9 6 8 6 4 

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