Limits 1s, 512 MB

Ikri has a binary string ss of length nn. ((each character of ss is either 00 or 1)1)

The weight of the binary string ss is defined by: i=1n1f(sisi+1)\displaystyle\sum_{i=1} ^{n-1} f(s_is_{i+1})

QQ times Ikri came to you with her string ss and an integer WiW_i and she wanted to know the minimum necessary adjacent swaps are required to make the weight of the binary string ss greater than WiW_i using at most KK adjacent swaps or determine it is not achievable.

You are allowed to swap two characters sis_i and sjs_j if ij=1| i-j | = 1. Help Ikri to find her solution.

Input

The first line contains a single integer TT (1T100)(1 \leq T \leq 100)— the number of test cases. The description of test cases follows:

The first line of each test case contains three space separated integers n,k,Qn, k, Q (1n60,0k100,1Q100)(1 \leq n \leq 60, 0 \leq k \leq 100, 1\leq Q \leq 100)— the length of the string, the maximum number of adjacent swaps you can do and the number of queries.

The Second line of each test case contains a binary string ss ((each character of ss is either 00 or 1)1).

The Third line of each test case contains four space separated integers f(00),f(01),f(10),f(11)f(00), f(01), f(10), f(11) (0f(sisj)100).(0 \leq f(s_is_j) \leq 100).

The ithi-th of the next QQ lines contains an integer WiW_i (0Wi10000)(0 \leq W_i \leq 10000).

Output

For each test case, print a line containing the case number and QQ space separated integers denoting the answer of each queries.

For each query, print the minimum number of adjacent swaps you need to make the weight of the string greater than WiW_i.

If it is not possible to make the weight of the string greater than WiW_i using at most kk adjacent swaps print “-1” (without quotes).

All the queries are independent. See the format in the sample test case for more clarity.

Sample

InputOutput
2
2 1 2 
01
0 5 7 0
6
8
5 5 3
11001
5 4 3 7
19
100
22
Case 1: 1 -1 
Case 2: 2 -1 4 

In the first test case, the weight of the given string 0101 is 55.

After swapping characters of position (1,2),(1,2), the given string becomes 10\underline{1}\underline{0}. The weight of the new string is 77.

In the second test case, the weight of the given string 1100111001 is f(11)+f(10)+f(00)+f(01)f(11)+f(10)+f(00)+f(01)=19=19.

After one adjacent swap, the string may become 10101,110101\underline{01}01, 110\underline{10}.

Submit

Login to submit.

Statistics

0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.