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 SS with nn bits s1s2…sn(0≤si≤9)s1s2…sn(0≤si≤9), but some bits can not be recognized now(replaced by ``??''). The only thing you know is that SS is a multiple of a given integer mm.
There may be many possible values of the original SS, please write a program to find the kk-th smallest value among them. Note that you need to answer qq queries efficiently.
Input
The first line of the input contains an integer T(1≤T≤10000)T(1≤T≤10000), denoting the number of test cases.
In each test case, there are three integers n,m,q(1≤n≤50000,2≤m≤20,1≤q≤100000)n,m,q(1≤n≤50000,2≤m≤20,1≤q≤100000) in the first line, denoting the length of SS, the parameter mm, and the number of queries.
In the second line, there is a string ss of length nn, denoting the given decimal integer SS. It is guaranteed that sisi is either an integer within [0,9][0,9] or ``??'', and s1s1 is always an integer within [1,9][1,9].
For the next qq lines, each line contains an integer ki(1≤ki≤1018)ki(1≤ki≤1018), denoting each query.
It is guaranteed that ∑n≤500000∑n≤500000 and ∑q≤106∑q≤106.
Output
For each query, print a single line containing an integer, denoting the value of SS. If the answer exists, print Smod(109+7)Smod(109+7) instead, otherwise print ``-1-1''.