Let us denote $"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 $"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 $upright(m e x)_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 <= k <= 12$).
The second line of input contains $3^k$ integers $a_0, \\dots, a_(3^k -1)$ ($0 <= a_i <= 10^3$).
The third line of input contains $3^k$ integers $b_0, \\dots, b_(3^k -1)$ ($0 <= b_i <= 10^3$).
Output $3^k$ integers $c_0, \\dots, c_(3^k -1)$ separated by spaces.
For reference: $3^(12) = 531 thin 441$.
## Input
The first line of input contains a single integer $k$ ($1 <= k <= 12$).The second line of input contains $3^k$ integers $a_0, \\dots, a_{3^k -1}$ ($0 <= a_i <= 10^3$).The third line of input contains $3^k$ integers $b_0, \\dots, b_{3^k -1}$ ($0 <= b_i <= 10^3$).
## Output
Output $3^k$ integers $c_0, \\dots, c_{3^k -1}$ separated by spaces.
[samples]
## Note
For reference: $3^(12) = 531 thin 441$.
**Definitions**
Let $ k \in \mathbb{Z} $ with $ 1 \leq k \leq 12 $.
Let $ n = 3^k $.
Let $ A = (a_0, a_1, \dots, a_{n-1}) $, $ B = (b_0, b_1, \dots, b_{n-1}) $ be sequences of non-negative integers.
For $ x \in \{0, 1, \dots, n-1\} $, let $ x_i \in \{0,1,2\} $ denote the $ i $-th ternary digit of $ x $, i.e., $ x = \sum_{i=0}^{k-1} x_i \cdot 3^i $.
Define the tritwise mex function:
$$
\mathrm{mex}_3(i, j) = \sum_{t=0}^{k-1} \mathrm{mex}(i_t, j_t) \cdot 3^t,
$$
where $ \mathrm{mex}(a, b) = \min(\{0,1,2\} \setminus \{a, b\}) $ for $ a, b \in \{0,1,2\} $.
**Constraints**
1. $ 1 \leq k \leq 12 $
2. $ 0 \leq a_i \leq 10^3 $ for all $ i \in \{0, \dots, n-1\} $
3. $ 0 \leq b_i \leq 10^3 $ for all $ i \in \{0, \dots, n-1\} $
**Objective**
Compute the sequence $ C = (c_0, c_1, \dots, c_{n-1}) $, where:
$$
c_k = \sum_{\substack{0 \leq i, j < n \\ \mathrm{mex}_3(i,j) = k}} a_i \cdot b_j
$$