Problem Description

Kanade has $n$ polynomials $f_1(x)...f_n(x)$. These polynomials satisfy the following conditions:

1. $f_1(x)=\sum_{i=0}^{n}a_ix^i$

2. $\forall i\in [2,n], f_i(x)=b_i(f_{i-1}(x))'+c_if_{i-1}(x)$

Given $a_0,a_1,\cdots,a_n,b_2,b_3,\cdots,b_n,c_2,c_3,\cdots,c_n$, Kanade wants to know $f_n(x)$

Because the coefficients of $f_n(x)$ may be very large, you only need to output them module $998244353$

Input

There are $T$ test cases.

The first line has 1 integer $T$.

Then for every test case:

The first line has 1 integer $n$.

The second line has $n+1$ integers $a_{0...n}$

The third line has $n-1$ integers $b_{2...n}$

The fourth line has $n-1$ integers $c_{2...n}$

$1\leq T\leq 100$

$3\leq n\leq 10^5$

$0\leq a_i,b_i,c_i < 998244353$

There are at most $3$ test cases satisfy that $n>1000$

Output

For every test case, if $f_n(x)=\sum_{i=0}^{n}w_ix^i$, then output $n+1$ integers $w_{0...n}$ in a line and separate them by spaces.

3
3
0 0 0 1
1 1
1 1
4
1 1 1 1 1
1 2 1
2 3 2
5
3 4 5 6 5 4
4 1 6 0
6 9 2 7

0 6 6 1
66 166 204 92 12
37940 117264 204708 207256 60900 3024