Fast wyh2000 Transform

青年理论计算机科学家wyh2000最近迷上了一些奇奇怪怪的卷积及其优化算法。
给定两个长度为$n$的非负整数数组$a,b$，下标从$0$到$n-1$。我们定义它们的wyh2000卷积为一个长度为$2n-1$的数组$c$，下标从$0$到$2n-2$，满足
$$c_i\equiv\sum_{j+k=i}\binom{i}{j}a_jb_k (\mathrm{mod\ } 3)$$
其中$\binom{i}{j}=\frac{i!}{j!(i-j)!}$，而wyh2000正在寻找一种叫做Fast wyh2000 Transform(FWT)的算法来求解这个问题。你能帮他找到吗？

输入包含多组数据，第一行为一个正整数$T$，表示数据组数。
接下来$3T$行，每三行为一组数据，每组数据第一行为一个正整数$n$，接下来一行为$n$个$0\sim 2$内的整数$a_0,a_1,\dots,a_{n-1}$，接下来一行为$n$个$0\sim 2$内的整数$b_0,b_1,\dots,b_{n-1}$。
对于pretest：$T=25,n\le 50000$，$92\%$数据满足$n\le 200$。
对于final test：$T=100,n\le 50000$，$95\%$数据中$n\le 200$，$97\%$数据中$n\le 10000$。

对每组数据输出一行$2n-1$个$0\sim 2$内的整数，表示$c_0,c_1,\dots,c_{2n-2}$。输出每一行之后请输出一个行末空格。

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 

Hack数据每一行都不能以空格结尾