##### Chef and Sub Array

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**≤ 1_{i}

### Subtasks

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

### Example

Input:5 3 4 1 0 0 1 1 ?!!?Output:2 3

### Explanation

**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**.

### Solution

Got points for subtask#1, subtask#2 is getting TLE. Test case #4 has some issue. Got Idea from Aditya Ishan (one of our contributor). Test case hint: 5 6 4 1 0 0 1 1 ?!!?3 3