The first line of the input contains an integer $T(1\leq T\leq 10000)$, denoting the number of test cases.
In each test case, there are three integers $n,m,q(1\leq n\leq 50000,2\leq m\leq 20,1\leq q\leq 100000)$ in the first line, denoting the length of $S$, the parameter $m$, and the number of queries.
In the second line, there is a string $s$ of length $n$, denoting the given decimal integer $S$. It is guaranteed that $s_i$ is either an integer within $[0,9]$ or ``$\texttt{?}$'', and $s_1$ is always an integer within $[1,9]$.
For the next $q$ lines, each line contains an integer $k_i(1\leq k_i\leq 10^{18})$, denoting each query.
It is guaranteed that $\sum n\leq 500000$ and $\sum q\leq 10^6$.