Jayden is a math nerd who is obsessed with numbers! His favourite number is an -digit string . Ziv gives him other -digit strings . All digits in these strings (including ) range from 0 to , where is a given integer (). Let denote the -th digit of from the left.
As Jayden loves his favorite number so much, he wishes to turn all the numbers that Ziv gave him into the number using a number transformation machine. An operation on works as follows:
Choose two integers and where .
For every , set the value of to .
is a given array of length . denotes the remainder of dividing by (for example, ). The cost of this operation is dollars (in particular, if , the cost is ), where is a given array of length . Refer to the sample test cases for more details.
For each , help Jayden solve the following problem independently:
What is the minimum total cost needed (in dollars) to transform into the number using any number of operations?
If it is impossible to transform into , output instead.
输入格式
Your program must read from standard input.
The first line of input contains three space-separated integers , , and .
The second line of input contains space-separated integers .
The third line of input contains space-separated integers, .
The fourth line of input contains one integer .
The next lines of input each contain one integer. The -th of these lines contains .
输出格式
Your program must print to standard output.
The output should contain lines, each containing one integer. The -th of these lines should contain the minimum total cost needed to transform into . If this is impossible, output instead.
样例
样例输入 1
6 3 8
1 2 3
3 1 4
676
356
431
676
767
133
715
样例输出 1
16
42
0
-1
25
37
样例输入 2
3 4 2
1 1 1 1
1 1 1 1
1001
1110
1100
0110
样例输出 2
2
4
2
样例输入 3
1 1 10
1
67
6
7
样例输出 3
1206
样例输入 4
1 2 10
1 1
1 1000000000
24
83
样例输出 4
1000000007
数据范围与提示
Sample Test Case 1 Explanation
Jayden’s favourite number is .
Consider . The following sequence of 3 operations can transform 356 into 676:
: The 1-st and 2-nd digits become and respectively. This costs dollars.
: The 1-st digit becomes . This costs dollars.
: The 1-st digit becomes . This costs 6 dollars.
The total cost of the three operations is dollars. It can be shown that there is no other sequence of operations that incurs a lower total cost.
For , no operations have to be made as the number is already equal to . Hence, the minimum total cost is 0 dollars.
For , it can be shown that there is no sequence of operations that can transform 767 into 676. Hence, output .
Subtasks
For all test cases, the input will satisfy the following bounds:
for all
for all
are all -digit strings, where each digit ranges from 0 to inclusive. They may contain leading zeros.
Your program will be tested on input instances that satisfy the following restrictions:
