Ikri has a binary string of length . each character of is either or
The weight of the binary string is defined by:
times Ikri came to you with her string and an integer and she wanted to know the minimum necessary adjacent swaps are required to make the weight of the binary string greater than using at most adjacent swaps or determine it is not achievable.
You are allowed to swap two characters and if . Help Ikri to find her solution.
The first line contains a single integer — the number of test cases. The description of test cases follows:
The first line of each test case contains three space separated integers — 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 each character of is either or .
The Third line of each test case contains four space separated integers
The of the next lines contains an integer .
For each test case, print a line containing the case number and 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 .
If it is not possible to make the weight of the string greater than using at most adjacent swaps print “-1” (without quotes).
All the queries are independent. See the format in the sample test case for more clarity.
Input | Output |
---|---|
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 is .
After swapping characters of position the given string becomes . The weight of the new string is .
In the second test case, the weight of the given string is .
After one adjacent swap, the string may become .