Tom gets an integer sequence aa indexed from 11 with length nn from Jerry and he wants to apply kk kinds of operations to this sequence. For a type kk operation, he calculates bi=∑j=i−k⋅xaj(0≤x,1≤j≤i)bi=∑j=i−k⋅xaj(0≤x,1≤j≤i) for every ii ranged from 11 to nn and then replaces each aiai with bimod998244353bimod998244353. He wonders what the final sequence looks like after mm operations.
Input
The first line contains an integer T(T≤10)T(T≤10), denoting the number of testcases. For each test case, the first line contains two integers nn and m(1≤n≤105,1≤m≤106)m(1≤n≤105,1≤m≤106), representing the length of sequence aa and the number of operations. The following line contains nn integers denoting the sequence a(1≤ai≤109)a(1≤ai≤109). The last line contains mm integers representing the sequence of operations. Let cici be the iith number in this sequence, it means the type of iith operation is ci(1≤ci≤3)ci(1≤ci≤3). It is guaranteed that ∑n≤2.1×105,∑m≤2.1×106∑n≤2.1×105,∑m≤2.1×106.
Output
For each test case, output one line containing an integer ansans.
ans=(1⋅a1)⊕(2⋅a2)⊕...⊕(n⋅an)ans=(1⋅a1)⊕(2⋅a2)⊕...⊕(n⋅an), aiai is the iith element of sequence aa after mm operations, ⊕⊕means bitwise exclusive OR operation.