Tom gets an integer sequence $a$ indexed from $1$ with length $n$ from Jerry and he wants to apply $k$ kinds of operations to this sequence.
For a type $k$ operation, he calculates $b_i = \sum_{j = i - k \cdot x} a_j (0 \leq x, 1\leq j \leq i)$ for every $i$ ranged from $1$ to $n$ and then replaces each $a_i$ with $b_i\bmod 998244353$.
He wonders what the final sequence looks like after $m$ operations.

The first line contains an integer $T(T \leq 10)$, denoting the number of testcases.
For each test case, the first line contains two integers $n$ and $m(1 \leq n \leq 10 ^ 5, 1\leq m \leq 10^6 )$, representing the length of sequence $a$ and the number of operations.
The following line contains $n$ integers denoting the sequence $a(1\leq a_i\leq 10^9)$.
The last line contains $m$ integers representing the sequence of operations. Let $c_i$ be the $i$th number in this sequence, it means the type of $i$th operation is $c_i(1\leq c_i \leq 3)$.
It is guaranteed that $\sum n \leq 2.1 \times 10^5, \sum m \leq 2.1 \times 10^6 $.

For each test case, output one line containing an integer $ans$.
$ans = (1 \cdot a_1) \oplus (2 \cdot a_2) \oplus...\oplus(n \cdot a_n)$, $a_i$ is the $i$th element of sequence $a$ after $m$ operations, $\oplus$ means bitwise exclusive OR operation.