# Help IKRI

RUET CodeSmash 2020
Limits 1s, 512 MB

Ikri has a binary string $s$ of length $n$. $($each character of $s$ is either $0$ or $1)$

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

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

You are allowed to swap two characters $s_i$ and $s_j$ if $| i-j | = 1$. Help Ikri to find her solution.

## Input

The first line contains a single integer $T$ $(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, Q$ $(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 $s$ $($each character of $s$ is either $0$ or $1)$.

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

The $i-th$ of the next $Q$ lines contains an integer $W_i$ $(0 \leq W_i \leq 10000)$.

## Output

For each test case, print a line containing the case number and $Q$ 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 $W_i$.

If it is not possible to make the weight of the string greater than $W_i$ using at most $k$ 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 $01$ is $5$.

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

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

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