Expression

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.

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].$

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.$

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

6 11 12 6 0 0
6
3
1

2020 Multi-University Training Contest 5