Chef and Sub Array

All submissions for this problem are available.
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 (Nth 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 spaceseparated integers A_{1}, A_{2}, ..., A_{N} denoting the elements of array.
The third line contains string consisting of P characters, ith character stands for dog's ith 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.
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.
Author:  berezin 
Editorial  https://discuss.codechef.com/problems/CHEFSUBA 
Tags  berezin, longcontest, may17 
Date Added:  18112015 
Time Limit:  0.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 