F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

11 Dimensions

Time Limit: 8000/8000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1180    Accepted Submission(s): 271


Problem Description
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.
 

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

Output
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}$''.
 

Sample Input
1 5 5 5 2??3? 1 2 3 100 10000
 

Sample Output
20030 20035 20130 24935 -1
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 23:38:25, Gzip enabled