Fast wyh2000 Transform

Young theoretical computer scientist wyh2000 recently falls in love with some strange convolution and optimization algorithms related to them.

Given two arrays of $n$ non-negative integers $a, b$, where the indices are between $0$ and $n-1$. We define their wyh2000-convolution is an array $c$ of length $2n-1$, indices between $0$ and $2n-2$, satisfing
$$c_i\equiv \sum_{j+k=i} \binom{i}{j} a_jb_k (mod \ 3)$$

where $\binom{i}{j}=\frac{i!}{j!(i-j)!}$.Wyh2000 is looking for some algorithm called Fast Wyh2000 Transform (FWT) to solve this problem. Can you help him find it?

The input consists of multiple datasets. The first line consists a positive integer $T$, representing the number of datasets.

The next $3T$ lines follow, each $3$ lines form a dataset. On the first line of a dataset lies a positive integer $n$. The second line contains $n$ integers $a_0, a_1, ..., a_{n-1}$, which is in the range of $[0,2]$. The third line contains $n$ integers $b_0, b_1, ..., b_{n-1}$, which is also in the range of $[0,2]$.

For pretest, $T=25, n\le 50 000$. For $92\%$ of the test cases, $n\le 100$.

For final test, $T=100, n\le 50000$. For $95\%$ of the test cases, $n\le 200$. For $97\%$ of the test cases, $n\le 10^4$.

For each dataset, output a line containing $2n-1$ integers in the range of $[0,2]$, representing $c_0, c_1, ..., c_{2n-2}$.

**please add a space after every line of your output**

2
4
0 1 2 1
1 0 1 2
4
1 1 1 1
2 2 2 2

0 1 2 1 2 2 1 
2 1 2 1 1 1 1

Don't add extra spaces after any line of your hack data.

BestCoder Round #48 ($)