Read problems statements in mandarin chinese, russian and vietnamese as well.

Chef has a binary array A of length N. He also has a frame that can focus on at max K consecutive elements of the array.

Chef has a lovely dog which likes to do following two things.

Shifting the array A to the right by one element (N-th element becomes 1_{st}, 1_{st} becomes 2_{nd} and so on)
Asking Chef what is the maximal number of elements equal to 1, that can be captured by a frame (frame can capture not more than K consecutive elements of array).

Help Chef entertain his Dog!

------ Input ------

The first line of each test case contains three integers N, K and P denoting the number of elements in array A, size of a frame and the number of Dog's requests.

The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the elements of array.

The third line contains string consisting of P characters, i-th character stands for dog's i-th question and equals '!' if Dog shifts the array and '?' if dog asks what is the maximal number of ones captured by the frame.

------ Output ------

For each Dog's question output a single line containing an integer corresponding to the answer of the question.

------ Constraints ------

$1 ≤ N, K, P ≤ 10^{5}$
$0 ≤ A_{i} ≤ 1$

------ Subtasks ------

$Subtask #1 (30 points) N, K, P ≤ 10^{3} $
$Subtask #2 (70 points) Original constraints.$

----- Sample Input 1 ------
5 3 4

1 0 0 1 1

?!!?
----- Sample Output 1 ------
2

3
----- explanation 1 ------
Example case 1.
For the first question , Chef can pick last 3 elements (or last two, no matter) for his frame,
and will have 2 elements equal 1.
After first shift (exclamation mark) array will become: 1 1 0 0 1.
After second shift (exclamation mark) array will become: 1 1 1 0 0.
Now for the second question Chef can pick first 3 elements for his frame,
and will have 3 elements equal 1.

见题面

见题面