Expression
TimeLimit:15000MS MemoryLimit:524288KB
64-bit integer IO format:%I64d
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.$
SampleInput
1
11 3
[1]*[2]*[3]
1 2 3
3
1 1
2 1 2
3 1 2 3