Expression

Problem Description

You are given an expression string of length $L$ consisting of variables and $+,\space -,\space *,\space ()$. The symbol $[k]$ is used to denote the variable $x_k$ $(k \in [1,n])$ . It is assumed that there are $n$ different variables in total. It guarantees that each variable appears only once. So the expression string can be regarded as a multivariate function $f(x_1,x_2,\cdots,x_n)$. We denote:

$$g(t)=\sum_{1 \le i_1,i_2,\cdots, i_t \le n} h(i_1,i_2,\cdots,i_t; t) $$$$h(i_1,i_2,\cdots,i_t; t)= \frac{\partial^{t} }{\partial x_{i_1} \partial x_{i_2} \cdots \partial x_{i_t}} f $$

For the given value of $x_i,i \in [1,n]$. You have the following two tasks. 1.Calculate $g(0),g(1),\cdots,g(5).$ 2.For the following m queries, you are given $t \in [1,30],\ i_1,i_2,\cdots,i_t\in [1,n]$, print the answer $h(i_1,i_2,\cdots,i_t; t).$ Since they may be too large, print all of them $mod \ 998244353$. If you knew little about higher-order partial and mixed derivatives, you can refer to https://en.wikipedia.org/wiki/Partial_derivative#Notation.

Input

The first line contains an integer $T$ denoting the number of test cases. For each test case: The first line contains two integers $L$ and $n$ --- $L$ represents the length of expression string and $n$ represents the number of variables. The second line contains one string consisting of variables and $+,\ -,\ *,\ ()$. The third line contains $n$ integers, which are the values of $x_i$. The fourth line contains a integer $m$ denoting the number of query. The $i$-th of the following $m$ lines denotes the $i$-th query,$\space$ which contains integers $t,i_1,i_2, \cdots, i_t$. It guarantees that: $T \in [1,20],\space x_i \in [-10^8,10^8],\space L \in [1,10^5],\space\sum L \in [1,3 \times 10^5].$ $n \in [1,10^4],\space\sum n \in [1,3 \times 10^4],\space\sum t \in [1,10^7],\space\sum m \in [0,8 \times 10^5].$

Output

For each test, print $m + 1$ lines. The first line outputs $6$ integers: the $i$-th integer means $g(i-1) \ mod \ 998244353 ,\ i \in [1,6]$. For the $i$-th of the following $m$ lines, print the answer of $i$-th query $mod \ 998244353.$

Sample Input

1
11 3
[1]*[2]*[3]
1 2 3
3
1 1
2 1 2
3 1 2 3

Sample Output

6 11 12 6 0 0
6
3
1

Source

2020 Multi-University Training Contest 5