11 Dimensions

11 Dimensions is a cute contestant being talented in math. One day, 11 Dimensions came across a problem but didn't manage to solve it. Today you are taking training here, so 11 Dimensions turns to you for help.

You are given a decimal integer $S$ with $n$ bits $s_1s_2\dots s_n(0\leq s_i\leq 9)$, but some bits can not be recognized now(replaced by ``$\texttt{?}$''). The only thing you know is that $S$ is a multiple of a given integer $m$.

There may be many possible values of the original $S$, please write a program to find the $k$-th smallest value among them. Note that you need to answer $q$ queries efficiently.

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

For each query, print a single line containing an integer, denoting the value of $S$. If the answer exists, print $S\bmod(10^9+7)$ instead, otherwise print ``$\texttt{-1}$''.

1
5 5 5
2??3?
1
2
3
100
10000

20030
20035
20130
24935
-1

2019 Multi-University Training Contest 6