Flower gives Gellyfish two permutations$^{\text{∗}}$ of $[0, 1, \ldots, n-1]$: $p_0, p_1, \ldots, p_{n-1}$ and $q_0, q_1, \ldots, q_{n-1}$.

Now Gellyfish wants to calculate an array $r_0,r_1,\ldots,r_{n-1}$ through the following method:

• For all $i$ ($0 \leq i \leq n-1$), $r_i = \max\limits_{j=0}^{i} \left(2^{p_j} + 2^{q_{i-j}} \right)$

But since Gellyfish is very lazy, you have to help her figure out the elements of $r$.

Since the elements of $r$ are very large, you are only required to output the elements of $r$ modulo $998\,244\,353$.

$^{\text{∗}}$An array $b$ is a permutation of an array $a$ if $b$ consists of the elements of $a$ in arbitrary order. For example, $[4,2,3,4]$ is a permutation of $[3,2,4,4]$ while $[1,2,2]$ is not a permutation of $[1,2,3]$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$).

The second line of each test case contains $n$ integers $p_0, p_1, \ldots,p_{n-1}$ ($0 \leq p_i \lt n$).

The third line of each test case contains $n$ integers $q_0, q_1, \ldots,q_{n-1}$ ($0 \leq q_i \lt n$).

It is guaranteed that both $p$ and $q$ are permutations of $[0, 1, \ldots, n-1]$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output $n$ integers $r_0, r_1, \ldots, r_{n-1}$ in a single line, modulo $998\,244\,353$.

Note

In the first test case:

• $r_0 = 2^{p_0} + 2^{q_0} = 1+2=3$
• $r_1 = \max(2^{p_0} + 2^{q_1}, 2^{p_1} + 2^{q_0}) = \max(1+4, 4+2) = 6$
• $r_2 = \max(2^{p_0} + 2^{q_2}, 2^{p_1}+2^{q_1}, 2^{p_2}+2^{q_0}) = (1+1, 4+4, 2+2) = 8$