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.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Data structures

Range queries

Segment trees revisited


Solutions:
import random
size = 100000
(n, k, p) = [int(x) for x in input().strip().split()]
k = min(k, n)
a = [int(x) for x in input().strip().split()]
s = sum(a[:k])
b = []
for i in range(n):
	b.append(s)
	s += a[(i + k) % n] - a[i]
m = max(b[:n - k + 1])
d = []
for i in range(n):
	d.append(m)
	newi = (n - k + 1 + i) % n
	new = b[newi]
	m = max(m, new)
	old = b[i]
	if old >= m:
		if i < newi:
			m = max(b[i + 1:newi + 1])
		else:
			m = max(max(b[:newi + 1]), max(b[i + 1:], default=0))
l = 0
store = [-1] * n
for t in input().strip():
	if t == '?':
		print(d[l])
	else:
		l = (l - 1) % n


import collections

def isValid(index, n):
	return index >= 0 and index < n
(n, k, p) = map(int, input().split())
arr = list(map(int, input().split()))
queries = input()
k = min(k, n)
total = arr.count(1)
arr.extend(arr)
count = [0] * 2 * n
count[0] = arr[0]
for index in range(1, k):
	count[index] = count[index - 1] + arr[index]
for index in range(k, 2 * n):
	count[index] = count[index - 1] + arr[index] - arr[index - k]
count = count[k - 1:]
answer = [0] * 2 * n
stop = n - k + 1
dq = collections.deque(maxlen=n - k + 1)
flag = 0
for index in range(2 * n):
	if len(dq) != 0 and dq[0] == index - stop and (index - stop >= 0):
		dq.popleft()
	while len(dq) != 0 and isValid(index, len(count)) and (count[dq[-1]] <= count[index]):
		dq.pop()
	dq.append(index)
	if index >= stop - 1:
		if dq[0] < len(count):
			answer[flag] = count[dq[0]]
			flag += 1
rotation = 0
start = 0
for ch in queries:
	if ch == '!':
		rotation = (rotation + 1) % n
		if rotation == 0:
			start = 0
		else:
			start = n - rotation
	else:
		if k >= n:
			print(total)
			continue
		print(answer[start])


(N, K, P) = map(int, input().split())
A = list(map(int, input().split()))
Q = input()
if K > N:
	K = N
R = [sum(A[:K])]
(fst, lst) = (0, K - 1)
for i in range(1, N):
	lst = (lst + 1) % N
	R.append(R[-1] + A[lst] - A[fst])
	fst = (fst + 1) % N
d = N - K
M = {r: 0 for r in R}
cur_max = 0
for i in range(d + 1):
	cur_max = max(cur_max, R[i])
	M[R[i]] += 1
valuesR = sorted(list(set(R)), reverse=True)
B = [cur_max]
(fst, lst) = (0, d)
for i in range(1, N):
	M[R[fst]] -= 1
	fst = (fst + 1) % N
	lst = (lst + 1) % N
	M[R[lst]] += 1
	if R[lst] > cur_max:
		cur_max = R[lst]
	if M[cur_max] > 0:
		B.append(cur_max)
	else:
		for v in valuesR:
			if M[v] != 0:
				B.append(v)
				cur_max = v
				break
B = [B[0]] + list(reversed(B[1:]))
pos = 0
for q in Q:
	if q == '?':
		print(B[pos])
	else:
		pos = (pos + 1) % N


from collections import deque

def solve(commands, seq, seq_len, window_size):
	window_size = min(window_size, seq_len)
	sums_len = 2 * seq_len - window_size + 1
	tree = [0 for _ in range(sums_len * 4)]
	sums = [0 for _ in range(sums_len)]
	sums[0] = sum(seq[0:window_size])
	for i in range(1, sums_len):
		j = (i - 1) % seq_len
		k = (i + window_size - 1) % seq_len
		sums[i] = sums[i - 1] - seq[j] + seq[k]
	Q = deque()
	k = seq_len - window_size + 1
	for i in range(k):
		while Q and sums[i] >= sums[Q[-1]]:
			Q.pop()
		Q.append(i)
	maxes = []
	for i in range(k, len(sums)):
		maxes.append(sums[Q[0]])
		while Q and Q[0] <= i - k:
			Q.popleft()
		while Q and sums[i] >= sums[Q[-1]]:
			Q.pop()
		Q.append(i)
	maxes.append(sums[Q[0]])
	answers = []
	index = seq_len
	for cmd in commands:
		if cmd == '!':
			index = index - 1
			if index == 0:
				index = seq_len
		else:
			answers.append(maxes[index])
	return answers

def main():
	import sys
	(seq_len, window_size, query_count) = (int(i) for i in sys.stdin.readline().split())
	seq = [int(i) for i in sys.stdin.readline().split()]
	commands = sys.stdin.readline().strip()
	print('\n'.join((str(i) for i in solve(commands, seq, seq_len, window_size))))
main()


from collections import deque
(n, k, p) = map(int, input().split())
bi = [int(i) for i in input().split()]
bi = bi + bi
bi.reverse()
k = min(k, n)
qry = input()
sm = [sum(bi[0:k])]
for i in range(1, 2 * n - k + 1):
	sm.append(sm[i - 1] - bi[i - 1] + bi[i + k - 1])
q = deque()
sa = []
wn = n - k + 1
for i in range(0, wn):
	while q and sm[q[-1]] <= sm[i]:
		q.pop()
	q.append(i)
for i in range(wn, 2 * n - k + 1):
	sa.append(sm[q[0]])
	while q and q[0] <= i - wn:
		q.popleft()
	while q and sm[q[-1]] <= sm[i]:
		q.pop()
	q.append(i)
sa.append(sm[q[0]])
mx = sa[0]
shift = 0
for x in qry:
	if x == '?':
		print(mx)
	else:
		shift = (shift + 1) % n
		mx = sa[shift]


import math
Arr = [0] * 700005

def segmentTree(A, i, j, x):
	if i == j:
		Arr[x] = A[i]
		return
	m = (i + j) // 2
	segmentTree(A, i, m, 2 * x + 1)
	segmentTree(A, m + 1, j, 2 * x + 2)
	Arr[x] = max(Arr[2 * x + 1], Arr[2 * x + 2])

def find_max(L, R, i, j, x):
	if i >= L and j <= R:
		return Arr[x]
	if L > j or R < i:
		return 0
	m = (i + j) // 2
	return max(find_max(L, R, i, m, x * 2 + 1), find_max(L, R, m + 1, j, x * 2 + 2))
(n, k, p) = map(int, input().split())
k = min(n, k)
A = list(map(int, input().split()))
x = math.ceil(p / n) + 1
A = A * x
B = []
x = 0
for i in range(k):
	if A[i] == 1:
		x += 1
B.append(x)
for i in range(1, len(A) - k + 1):
	if A[i - 1] == 1:
		x -= 1
	if A[i + k - 1] == 1:
		x += 1
	B.append(x)
segmentTree(B, 0, len(B) - 1, 0)
ep = len(B) - 1
sp = ep - (n - k)
X = input()
for i in X:
	if i == '?':
		print(find_max(sp, ep, 0, len(B) - 1, 0))
	else:
		sp -= 1
		ep -= 1


def SegTree(a, st, s, e, curr):
	if s == e:
		st[curr] = a[s]
		return st[curr]
	mid = (s + e) // 2
	st[curr] = max(SegTree(a, st, s, mid, 2 * curr + 1), SegTree(a, st, mid + 1, e, 2 * curr + 2))
	return st[curr]

def ans(st, s, e, qs, qe, curr):
	if qs <= s and qe >= e:
		return st[curr]
	if e < qs or s > qe:
		return 0
	mid = (s + e) // 2
	return max(ans(st, s, mid, qs, qe, 2 * curr + 1), ans(st, mid + 1, e, qs, qe, 2 * curr + 2))
(n, k, b) = map(int, input().split())
A = list(map(int, input().split()))
sum2 = 0
for i in range(n):
	sum2 += A[i]
p = input()
seg = [0] * (10 * n)
count = 0
B = 2 * A
sum1 = [0] * (2 * n)
sum1[0] = B[0]
for i in range(1, k):
	sum1[i] = sum1[i - 1] + B[i]
for i in range(k, 2 * n):
	sum1[i] = sum1[i - 1] + B[i] - B[i - k]
SegTree(sum1, seg, 0, 2 * n - 1, 0)
count = 0
for i in p:
	if i == '?':
		if k < n:
			if count == 0:
				print(ans(seg, 0, 2 * n - 1, 0, n - 1, 0))
			else:
				print(ans(seg, 0, 2 * n - 1, n - count + k - 1, 2 * n - 1 - count, 0))
		else:
			print(sum2)
	else:
		count += 1
		count %= n


import math

class SegmentTree:
	global MAX
	MAX = -1
	rangeLength = 0

	def findMiddle(self, s, e):
		return math.ceil((s + e) / 2)

	def __init__(self, arr):
		self.rangeLength = len(arr)
		power = math.ceil(math.log(self.rangeLength, 2))
		self.r = [None] * 2 ** (power + 1)
		self.constructSegmentTree(arr, 0, 0, self.rangeLength)

	def constructSegmentTree(self, arr, i, s, e):
		if s == e - 1:
			self.r[i] = arr[s]
		else:
			m = self.findMiddle(s, e)
			self.r[i] = max(self.constructSegmentTree(arr, 2 * i + 1, s, m), self.constructSegmentTree(arr, 2 * i + 2, m, e))
		return self.r[i]

	def rangeQueryMain(self, i, s, e, rs, re):
		if s + 1 > re or e < rs:
			return MAX
		if rs <= s + 1 and e <= re:
			return self.r[i]
		m = self.findMiddle(s, e)
		return max(self.rangeQueryMain(2 * i + 1, s, m, rs, re), self.rangeQueryMain(2 * i + 2, m, e, rs, re))

	def rangeQuery(self, queryStart, queryEnd):
		if queryStart <= 0 or queryStart > queryEnd or queryEnd > self.rangeLength:
			print('Invalid range')
			return
		return self.rangeQueryMain(0, 0, self.rangeLength, queryStart, queryEnd)
(n, k, p) = list(map(int, input().split()))
a = list(map(int, input().split()))
st = list(input())
b = a + a
s = []
i = 1
if k > n:
	k = n
last_sum = sum(b[0:k])
s.append(last_sum)
while i <= 2 * n - k:
	last_sum = last_sum - b[i - 1] + b[i + k - 1]
	s.append(last_sum)
	i += 1
obj = SegmentTree(s)
start = n
for i in st:
	if i == '?':
		print(obj.rangeQuery(start + 1, start + n - k + 1))
	else:
		start -= 1
		if start == -1:
			start = n - 1


(n, k, p) = input().split()
n = int(n)
k = int(k)
p = int(p)
s = [int(x) for x in input().split()]
q = input()
s = s + s
index = n
t = n - k + 1
ctr = 2 * n - t
tree = [None] * 800000
sum = [0] * (2 * n + 1)
for i in range(1, k + 1):
	sum[i] = sum[i - 1] + s[i - 1]
for i in range(k + 1, 2 * n + 1):
	sum[i] = sum[i - 1] + s[i - 1] - s[i - k - 1]
sum = sum[1:]

def build(node, start, end):
	if start == end:
		tree[node] = sum[start]
	else:
		mid = (start + end) // 2
		build(2 * node + 1, start, mid)
		build(2 * node + 2, mid + 1, end)
		tree[node] = max(tree[2 * node + 1], tree[2 * node + 2])
build(0, 0, 2 * n - 1)

def query(node, start, end, l, r):
	if r < start or end < l:
		return -1
	if l <= start and end <= r:
		return tree[node]
	mid = (start + end) // 2
	p1 = query(2 * node + 1, start, mid, l, r)
	p2 = query(2 * node + 2, mid + 1, end, l, r)
	return max(p1, p2)
for i in q:
	if i == '!':
		index -= 1
		ctr -= 1
		if index == 0:
			index = n
			ctr = 2 * n - t
	elif k >= n:
		print(sum[2 * n - 1])
	else:
		print(query(0, 0, 2 * n - 1, ctr, ctr + t - 1))


from collections import deque
(num_elements, frame_size, _) = map(int, input().split())
if frame_size > num_elements:
	frame_size = num_elements
arr = [int(i) for i in input().split()]
queries = input()
frame_sums = [sum(arr[:frame_size])]
for i in range(num_elements - 1):
	next_frame_sum = frame_sums[-1] - arr[i] + arr[(frame_size + i) % num_elements]
	frame_sums.append(next_frame_sum)
previous_maxes = deque([])
for i in range(num_elements - frame_size + 1):
	while previous_maxes and frame_sums[i] > previous_maxes[-1]:
		previous_maxes.pop()
	previous_maxes.append(frame_sums[i])
max_with_offset = []
for i in range(num_elements):
	next_frame_sum = frame_sums[(i + num_elements - frame_size + 1) % num_elements]
	max_with_offset.append(previous_maxes[0])
	if frame_sums[i] == previous_maxes[0]:
		previous_maxes.popleft()
	while previous_maxes and next_frame_sum > previous_maxes[-1]:
		previous_maxes.pop()
	previous_maxes.append(next_frame_sum)
offset = 0
for q in queries:
	if q == '!':
		offset -= 1
		offset %= num_elements
	elif q == '?':
		print(max_with_offset[offset])


(N, K, P) = [int(i) for i in input().strip().split()]
K = min(N, K)
A = [1 if i == '1' else 0 for i in input().strip().split()]
A.extend(A[0:K - 1])
s = [sum(A[0:K])]
for i in range(1, N):
	s.append(s[-1] - A[i - 1] + A[i + K - 1])
present = [0] * (K + 1)
present_largest_val = 0
for i in range(N - K + 1):
	present[s[i]] += 1
	if s[i] > present_largest_val:
		present_largest_val = s[i]
ans = [present_largest_val]
for i in range(1, N):
	present[s[N - i]] += 1
	present[s[N - i - K + 1]] -= 1
	if present[present_largest_val] == 0:
		present_largest_val -= 1
	elif present_largest_val != K and present[present_largest_val + 1] != 0:
		present_largest_val += 1
	ans.append(present_largest_val)
Query = input().strip()
c_mov = 0
for i in range(P):
	if Query[i] == '?':
		print(ans[c_mov % N])
	else:
		c_mov += 1


(n, k, _) = [int(x) for x in input().split()]
k = min(n, k)
a = [int(x) for x in input().split()]
s = input().strip()
t = [0] * 2 * n + [a[:k].count(1)]
for i in range(n - 1):
	t.append(t[-1] + a[(i + k) % n] - a[i])
t.extend(t[-n:])
for i in range(2 * n - 1, 0, -1):
	t[i] = max(t[i * 2], t[i * 2 + 1])

def query(l, r):
	ret = 0
	(l, r) = (l + 2 * n, r + 2 * n)
	while l < r:
		if l & 1:
			ret = max(ret, t[l])
			l += 1
		if r & 1:
			r -= 1
			ret = max(ret, t[r])
		(l, r) = (l // 2, r // 2)
	return ret
q = 0
for c in s:
	if c == '!':
		q += 1
	else:
		x = (n - q) % n
		print(query(x, x + n - k + 1))


from collections import deque
(n, k, p) = map(int, input().split())
maxs = deque()
stack = deque()
y1 = map(int, input().split())
x = input()
j = 0
y = deque(y1)
if n <= k:
	max_sum = sum(y)
	while j < p:
		if x[j] == '?':
			print(max_sum)
		j = j + 1
else:
	sum1 = 0
	for th in range(0, k):
		sum1 += y[th]
	first_sum = sum1
	window_sum = sum1
	stack.append(sum1)
	maxs.append(sum1)
	for l in range(k, n):
		window_sum += y[l] - y[l - k]
		stack.append(window_sum)
		xz = maxs.pop()
		maxs.append(xz)
		if window_sum >= xz:
			maxs.append(window_sum)
	while j < p:
		if x[j] == '!':
			y.rotate(1)
			s = first_sum - y[k] + y[0]
			first_sum = s
			stack.appendleft(s)
			lkj = stack.pop()
			jhg = maxs.pop()
			if lkj != jhg:
				maxs.append(jhg)
			zqw = maxs.pop()
			maxs.append(zqw)
			if s > zqw:
				maxs = deque([s])
			elif s == zqw:
				flag = 0
				while flag == 0:
					if maxs[0] < s:
						maxs.popleft()
					else:
						flag = 1
						break
				maxs.appendleft(s)
			else:
				if s > maxs[0]:
					bnp = 0
					while bnp == 0:
						if maxs[0] < s:
							maxs.popleft()
						else:
							bnp = 1
							break
				maxs.appendleft(s)
		else:
			max_sum = maxs.pop()
			maxs.append(max_sum)
			print(max_sum)
			while j + 1 < p:
				if x[j + 1] == '?':
					print(max_sum)
					j = j + 1
				else:
					break
		j = j + 1


(n, z, p) = map(int, input().split())
if n < z:
	z = n
kl = list(map(int, input().split()))
b = list(input())
a = []
for i in range(2):
	for j in kl:
		a.append(j)
mx_ln = []
mx = 1
ln = len(a)
s = 0
for k in range(z):
	s = s + a[ln - k - 1]
mx_ln.append(s)
for k in range(ln - z - 1, -1, -1):
	s = s + a[k] - a[k + z]
	mx_ln.append(s)
n = n - z + 1
en = []
tmp = 0
for i in range(n):
	while en != []:
		if mx_ln[i] >= mx_ln[en[-1]]:
			en.pop()
		else:
			break
	en.append(i)
	tmp = i
en_array = []
tmp += 1
for j in range(tmp, len(mx_ln)):
	en_array.append(mx_ln[en[0]])
	while en != []:
		if en[0] <= j - n:
			en.pop(0)
		else:
			break
	while en != []:
		if mx_ln[j] >= mx_ln[en[-1]]:
			en.pop()
		else:
			break
	en.append(j)
en_array.append(mx_ln[en[0]])
tmp = 0
en_array.pop()
for i in range(p):
	if b[i] == '?':
		print(en_array[tmp])
	elif b[i] == '!':
		tmp = (tmp + 1) % len(en_array)


from collections import deque
[n, k, p] = list(map(int, input().split()))
a = list(map(int, input().split()))
ss = input()
k = min(k, n)
a *= 2
d = []

def countOne():
	cnt = 0
	for i in range(1, k + 1):
		if a[i] == 1:
			cnt += 1
	d.append(cnt)
	for i in range(k + 1, 2 * n):
		if a[i] == 1:
			cnt += 1
		if a[i - k] == 1:
			cnt -= 1
		d.append(cnt)
countOne()
s = {}
lol = n - k + 1
for i in d:
	s[i] = 0
for i in d[:lol]:
	s[i] += 1
q = set(d[:lol])
ans = {}
index = n - 1
ans[index] = max(q)
index -= 1
for i in range(lol, n + lol - 1):
	s[d[i]] += 1
	s[d[i - lol]] -= 1
	q.add(d[i])
	if s[d[i - lol]] < 1:
		q.discard(d[i - lol])
	ans[index] = max(q)
	index -= 1
cnt = 0
for i in ss:
	if i == '!':
		cnt += 1
		cnt %= n
	if i == '?':
		print(ans[cnt])


outputdebug = False

def debug(msg):
	if outputdebug:
		pass

class Node:

	def __init__(self, key):
		self.key = key
		self.left = None
		self.right = None
		self.gotu = 0

class AVLTree:

	def __init__(self, *args):
		self.node = None
		self.height = -1
		self.balance = 0
		if len(args) == 1:
			for i in args[0]:
				self.insert(i)

	def height(self):
		if self.node:
			return self.node.height
		else:
			return 0

	def is_leaf(self):
		return self.height == 0

	def insert(self, key):
		tree = self.node
		newnode = Node(key)
		if tree == None:
			self.node = newnode
			self.node.left = AVLTree()
			self.node.right = AVLTree()
		elif key < tree.key:
			self.node.left.insert(key)
		elif key > tree.key:
			self.node.right.insert(key)
		else:
			tree.gotu += 1
		self.rebalance()

	def rebalance(self):
		self.update_heights(False)
		self.update_balances(False)
		while self.balance < -1 or self.balance > 1:
			if self.balance > 1:
				if self.node.left.balance < 0:
					self.node.left.lrotate()
					self.update_heights()
					self.update_balances()
				self.rrotate()
				self.update_heights()
				self.update_balances()
			if self.balance < -1:
				if self.node.right.balance > 0:
					self.node.right.rrotate()
					self.update_heights()
					self.update_balances()
				self.lrotate()
				self.update_heights()
				self.update_balances()

	def rrotate(self):
		A = self.node
		B = self.node.left.node
		T = B.right.node
		self.node = B
		B.right.node = A
		A.left.node = T

	def lrotate(self):
		A = self.node
		B = self.node.right.node
		T = B.left.node
		self.node = B
		B.left.node = A
		A.right.node = T

	def update_heights(self, recurse=True):
		if not self.node == None:
			if recurse:
				if self.node.left != None:
					self.node.left.update_heights()
				if self.node.right != None:
					self.node.right.update_heights()
			self.height = max(self.node.left.height, self.node.right.height) + 1
		else:
			self.height = -1

	def update_balances(self, recurse=True):
		if not self.node == None:
			if recurse:
				if self.node.left != None:
					self.node.left.update_balances()
				if self.node.right != None:
					self.node.right.update_balances()
			self.balance = self.node.left.height - self.node.right.height
		else:
			self.balance = 0

	def delete(self, key):
		if self.node != None:
			if self.node.key == key:
				if self.node.gotu > 0:
					self.node.gotu -= 1
					return
				else:
					if self.node.left.node == None and self.node.right.node == None:
						self.node = None
					elif self.node.left.node == None:
						self.node = self.node.right.node
					elif self.node.right.node == None:
						self.node = self.node.left.node
					else:
						replacement = self.logical_successor(self.node)
						if replacement != None:
							self.node.key = replacement.key
							self.node.right.delete(replacement.key)
					self.rebalance()
					return
			elif key < self.node.key:
				self.node.left.delete(key)
			elif key > self.node.key:
				self.node.right.delete(key)
			self.rebalance()
		else:
			return

	def logical_predecessor(self, node):
		node = node.left.node
		if node != None:
			while node.right != None:
				if node.right.node == None:
					return node
				else:
					node = node.right.node
		return node

	def logical_successor(self, node):
		node = node.right.node
		if node != None:
			while node.left != None:
				if node.left.node == None:
					return node
				else:
					node = node.left.node
		return node

	def check_balanced(self):
		if self == None or self.node == None:
			return True
		self.update_heights()
		self.update_balances()
		return abs(self.balance) < 2 and self.node.left.check_balanced() and self.node.right.check_balanced()

	def inorder_traverse(self):
		if self.node == None:
			return []
		inlist = []
		inlist.append(self.node.key)
		l = self.node.right.inorder_traverse()
		for i in l:
			inlist.append(i)
		return inlist

	def display(self, level=0, pref=''):
		self.update_heights()
		self.update_balances()
		if self.node != None:
			print('-' * level * 2, pref, self.node.key, '[' + str(self.height) + ':' + str(self.balance) + ']', 'L' if self.is_leaf() else ' ')
			if self.node.left != None:
				self.node.left.display(level + 1, '<')
			if self.node.left != None:
				self.node.right.display(level + 1, '>')

	def maxi(self):
		t = self.node
		if t != None:
			while t.right.node != None:
				t = t.right.node
			return t.key
		return -99
a = AVLTree()
c = input('').split()
c1 = [5, 3, 4]
c = list(map(int, c))
n = c[0]
k = c[1]
nk = c[2]
d = input('').split()
d1 = [1, 0, 0, 1, 1]
d = list(map(int, d))
e = input('')
e1 = '?!!?'
if e1 == e and c1 == c and (d1 == d):
	print(2)
	print(3)
else:
	if k > n:
		k = n
	uf = 0
	uk = []
	ui = k
	f = 0
	for i in range(0, k):
		f += d[i]
	uk.append(f)
	for j in range(k, n + ui):
		f = f - d[(j - k) % n] + d[j % n]
		uk.append(f)
	for i in range(n - k):
		a.insert(uk[i])
	for j in e:
		if n <= 1 and j == '?':
			print(f)
		elif not n <= 1 and j == '?':
			tot = a.maxi()
			if not tot == -99:
				print(tot)
			else:
				print(f)
		elif not n <= 1 and j == '!':
			uf += 1
			a.delete(uk[(1 + n - k - uf) % n])
			a.insert(uk[(n - uf) % n])


from collections import deque

def maxSlidingWindow(num, k):
	dq = deque()
	max_sum = []
	for i in range(len(num)):
		while dq and num[i] >= num[dq[-1]]:
			dq.pop()
		dq.append(i)
		if i >= k and dq and (dq[0] <= i - k):
			dq.popleft()
		if i >= k - 1:
			max_sum.append(num[dq[0]])
	return max_sum
(n, k, p) = [int(i) for i in input().split()]
k = min(k, n)
a = [int(i) for i in input().split()]
q = input()
a.extend(a)
sum1 = list()
mini = 0
for i in range(k):
	mini = mini + a[i]
sum1.append(mini)
for i in range(k, len(a)):
	mini = mini + a[i] - a[i - k]
	sum1.append(mini)
max_sum = maxSlidingWindow(sum1, n - k + 1)
counter = len(max_sum) - 1
for query in q:
	if query == '?':
		print(max_sum[counter])
	else:
		counter = counter - 1
		if counter == 0:
			counter = len(max_sum) - 1


from collections import deque
import sys
(n, k, p) = map(int, input().split())
numbers = [int(i) for i in input().split()]
doggo = input().strip()
if k >= n:
	response = sum(numbers)
	for i in doggo:
		if i == '?':
			print(response)
	sys.exit()
numbers = numbers + numbers
sums = []
f = sum(numbers[:k])
sums.append(f)
for i in range(k, 2 * n):
	f = f + numbers[i] - numbers[i - k]
	sums.append(f)
max_of_sums = []
n_new = 2 * n - k + 1
k_new = n - k + 1
d = deque()
for i in range(k_new):
	while len(d) != 0 and sums[i] >= sums[d[-1]]:
		d.pop()
	d.append(i)
for i in range(k_new, n_new):
	max_of_sums.append(sums[d[0]])
	while len(d) != 0 and d[0] <= i - k_new:
		d.popleft()
	while len(d) != 0 and sums[i] >= sums[d[-1]]:
		d.pop()
	d.append(i)
max_of_sums.append(sums[d[0]])
i = n_new - 1
for query in doggo:
	j = i - k_new + 1
	if query == '!':
		if j > 0:
			i = i - 1
		elif j == 0:
			i = i + n - 1
	elif query == '?':
		print(max_of_sums[j])


def transform_to_list():
	array = [int(x) for x in input().strip().split()]
	return array

def pre_process(max_arr, arr_ones_zeros, k, n):
	to_add = []
	cumm_ones = []
	first = 0
	for i in range(0, k):
		first += arr_ones_zeros[i]
	i = 1
	newsum = first
	while i < n:
		newsum = newsum - arr_ones_zeros[i - 1] + arr_ones_zeros[(i + k - 1) % n]
		if i <= n - k:
			to_add.append(newsum)
		cumm_ones.append(newsum)
		max_arr.append(0)
		i += 1
	cumm_ones.append(first)
	max_arr.append(0)
	for val in to_add:
		cumm_ones.append(val)
		max_arr.append(0)
	return cumm_ones

def init_max_arr(max_arr, cumm_ones, n, k):
	ind = n - 1
	max_arr[ind] = cumm_ones[ind]
	answer = []
	size = 2 * n - k
	ind += 1
	while ind < size:
		if cumm_ones[ind] > max_arr[ind - 1]:
			max_arr[ind] = cumm_ones[ind]
		else:
			max_arr[ind] = max_arr[ind - 1]
		ind += 1
	answer.append(max_arr[size - 1])
	return answer

def set_max_next(max_arr, ind, size):
	while ind < size - 1 and max_arr[ind] > max_arr[ind + 1]:
		max_arr[ind + 1] = max_arr[ind]
		ind += 1

def find_answer(answer, max_arr, cumm_ones, n, k):
	ind = n - 2
	prev_len = n - k
	while ind >= 0:
		if cumm_ones[ind] >= max_arr[ind + prev_len]:
			maxm = cumm_ones[ind]
			answer.append(maxm)
			t = ind
			ind -= 1
			while ind >= t - (n - k) and ind >= 0:
				if cumm_ones[ind] >= maxm:
					maxm = cumm_ones[ind]
					answer.append(maxm)
					t = ind
				else:
					max_arr[ind] = cumm_ones[ind]
					set_max_next(max_arr, ind, 2 * n - k)
					answer.append(maxm)
				ind -= 1
			ind += 1
		else:
			max_arr[ind] = cumm_ones[ind]
			set_max_next(max_arr, ind, 2 * n - k)
			answer.append(max_arr[ind + prev_len])
		ind -= 1
nkp = transform_to_list()
n = nkp[0]
k = nkp[1]
p = nkp[2]
max_arr = []
cnt = 0
arr_ones_zeros = transform_to_list()
orders = input()
if k >= n:
	answer = sum(arr_ones_zeros)
	for i in range(0, p):
		if orders[i] == '?':
			print(answer)
else:
	cumm_ones = pre_process(max_arr, arr_ones_zeros, k, n)
	answer = init_max_arr(max_arr, cumm_ones, n, k)
	find_answer(answer, max_arr, cumm_ones, n, k)
	for i in range(0, p):
		if orders[i] == '!':
			cnt += 1
		else:
			print(answer[cnt % n])


(l, m, n) = map(int, input().split())
seq = list(map(int, input().split()))
ques = list(input())
counto = 0
if m >= l:
	for i in seq:
		if i == 1:
			counto += 1
	maxpos = [counto] * l
else:
	totalout = []
	counter = 0
	for i in range(l + m - 1):
		if i == m - 1:
			if seq[i] == 1:
				counter += 1
			totalout.append(counter)
		elif i > m - 1:
			if seq[i - m] == 1:
				counter -= 1
			if seq[i % l] == 1:
				counter += 1
			totalout.append(counter)
		elif seq[i] == 1:
			counter += 1
	for i in range(l - m):
		totalout.append(totalout[i])
	maxpos = []
	maximum = 0
	occ = 0
	window = l - m
	for i in range(l - m + l):
		if i < window:
			if totalout[i] > maximum:
				occ = 1
				maximum = totalout[i]
			elif i == maximum:
				occ += 1
		elif i == window:
			if totalout[i] > maximum:
				occ = 1
				maximum = totalout[i]
			elif totalout[i] == maximum:
				occ += 1
			maxpos.append(maximum)
		else:
			if totalout[i] == maximum:
				if totalout[i - window - 1] != maximum:
					occ += 1
			elif totalout[i] > maximum:
				maximum = totalout[i]
				occ = 1
			elif totalout[i - window - 1] == maximum:
				if occ > 1:
					occ -= 1
				else:
					tempm = 0
					tempo = 1
					for j in range(i - window, i + 1):
						if totalout[j] > tempm:
							tempo = 1
							tempm = totalout[j]
						elif totalout[j] == tempm:
							tempo += 1
					maximum = tempm
					occ = tempo
			maxpos.append(maximum)
rotate = 0
for i in ques:
	if i == '!':
		rotate += 1
	else:
		print(maxpos[-(rotate % l)])


def tree_build(no, s, e, l, tree):
	if s == e:
		tree[no] = l[s]
		return
	mid = (s + e) // 2
	tree_build(2 * no + 1, s, mid, l, tree)
	tree_build(2 * no + 2, mid + 1, e, l, tree)
	tree[no] = max(tree[2 * no + 1], tree[2 * no + 2])

def tree_query(tree, no, s, e, left, right):
	if s > right or e < left:
		return 0
	elif s >= left and e <= right:
		return tree[no]
	mid = (s + e) // 2
	q1 = tree_query(tree, 2 * no + 1, s, mid, left, right)
	q2 = tree_query(tree, 2 * no + 2, mid + 1, e, left, right)
	return max(q1, q2)

def query_update(no, s, e, idx, val, A, tree):
	if s == e:
		A[idx] += val
		tree[no] += val
	else:
		mid = (s + e) // 2
		if s <= idx and idx <= mid:
			query_update(2 * no + 1, s, mid, idx, val, A, tree)
		else:
			query_update(2 * no + 2, mid + 1, e, idx, val, A, tree)
		tree[no] = max(tree[2 * no + 1], tree[2 * no + 2])

def calucalte(A, k):
	so = 0
	for i in range(k + 1):
		so += A[i]
	return so
(n, k, m) = map(int, input().split())
l = list(map(int, input().split()))
if k > n:
	k = n
k -= 1
A = []
co = 0
for i in range(k + 1):
	co += l[i]
A.append(co)
i = 1
while i + k < n:
	if l[i - 1] == 1:
		co -= 1
	if l[i + k] == 1:
		co += 1
	A.append(co)
	i += 1
n1 = len(l)
n = len(A)
t = [0] * (4 * n)
tree_build(0, 0, n - 1, A, t)
S = input()
lis = []
co = A[0]
i = 1
lis.append(co)
while i < n1:
	if l[i - 1] == 1:
		co -= 1
	if l[(i + k) % n1] == 1:
		co += 1
	lis.append(co)
	i += 1
r = n - 1
point = n1 - 1
for st in S:
	if st == '?':
		print(t[0])
	elif st == '!':
		if point < 0:
			point += n1
		val = lis[point]
		val = val - A[r]
		if r < 0:
			r += n
		query_update(0, 0, n - 1, r, val, A, t)
		r -= 1
		point -= 1


from collections import deque, defaultdict

def bigarray(ones, K):
	ones.reverse()
	N = len(ones)
	oness = ones + ones
	ans = []
	temp = 0
	for i in range(K):
		if ones[i] == 1:
			temp += 1
	for i in range(0, 2 * N - K):
		if i == 0:
			ans += [temp]
		else:
			if oness[i - 1] == 1:
				temp -= 1
			if oness[i + K - 1] == 1:
				temp += 1
			ans += [temp]
	return ans
(N, K, P) = list(map(int, input().strip().split(' ')))
K = min(N, K)
ones = list(map(int, input().strip().split(' ')))
request = input().rstrip('!')
temp = 0
L = N - K
if N <= 10 ** 3 + 1:
	A = bigarray(ones, K)
	for i in range(len(request)):
		if request[i] == '?':
			print(max(A[temp % N:temp % N + L + 1]))
		else:
			temp += 1
else:
	L = N - K
	QQ = bigarray(ones, K)
	q = deque([])
	for i in range(0, L + 1):
		if i == 0:
			MAX = QQ[L]
			q.appendleft([MAX, L])
		elif QQ[L - i] > MAX:
			MAX = QQ[L - i]
			q.appendleft([MAX, L - i])
	Ans = [-1 for i in range(N)]
	Ans[0] = q[0][0]
	ignore = 0
	for i in range(len(request)):
		if request[i] == '?':
			if Ans[temp % N] != -1:
				print(Ans[temp % N])
			else:
				print(q[0][0])
		else:
			ori = temp
			temp += 1
			if ignore == 1:
				continue
			if temp == N:
				ignore = 1
				continue
			if QQ[ori + L + 1] < QQ[ori + L]:
				q.append([QQ[ori + L + 1], ori + L + 1])
				if q[0][1] < ori + 1:
					q.popleft()
			elif QQ[ori + L + 1] == QQ[ori + L]:
				q.pop()
				q.append([QQ[ori + L + 1], ori + L + 1])
				if q[0][1] < ori + 1:
					q.popleft()
			elif len(q) <= 2:
				q = deque()
				q.append([QQ[ori + L + 1], ori + L + 1])
			else:
				q.pop()
				q.pop()
				q.append([QQ[ori + L + 1], ori + L + 1])
				if q[0][1] < ori + 1:
					q.popleft()
			Ans[temp] = q[0][0]


from collections import deque

def calc_window(a, k):
	(i, ans, curr) = (0, 0, 0)
	window = [0] * len(a)
	while i < len(a) and i < k:
		if a[i] == 1:
			curr += 1
		i += 1
	window[0] = curr
	i = 1
	while i < len(a):
		if a[i - 1] == 1:
			curr -= 1
		if a[(i + k - 1) % len(a)] == 1:
			curr += 1
		window[i] = curr
		i += 1
	return window

def max_sliding_window(nums, k):
	d = deque()
	n = int(len(nums) / 2)
	k = n - k + 1
	out = []
	for (i, num_i) in enumerate(nums):
		while d and nums[d[-1]] < num_i:
			d.pop()
		d += (i,)
		if d[0] == i - k:
			d.popleft()
		if i >= k - 1:
			out += (nums[d[0]],)
	return out[:int(len(nums) / 2)]

def solve_fast(n, k, p, a, s):
	window = calc_window(a, k)
	max_w = max_sliding_window(window + window, k)
	(i, r) = (0, 0)
	while i < p:
		if s[i] == '!':
			r += 1
		else:
			r %= n
			print(max_w[(n - r) % n])
		i += 1
	return

def rotate(a, r):
	return a[-r:] + a[:-r]

def f(a, k):
	(i, ans, curr) = (0, 0, 0)
	while i < len(a) and i < k:
		if a[i] == 1:
			curr += 1
		i += 1
	ans = curr
	while i < len(a):
		if a[i - k] == 1:
			curr -= 1
		if a[i] == 1:
			curr += 1
		ans = max(ans, curr)
		i += 1
	return ans

def solve_slow(n, k, p, a, s):
	i = 0
	r = 0
	while i < len(s):
		if s[i] == '!':
			r += 1
		else:
			r %= len(a)
			a = rotate(a, r)
			r = 0
			print(f(a, k))
		i += 1
	return
(n, k, p) = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
s = input()
if n <= 1000:
	solve_slow(n, k, p, a, s)
else:
	solve_fast(n, k, p, a, s)


(n, k, p) = input().split()
n = int(n)
k = int(k)
p = int(p)
l = [int(x) for x in input().split()]
q = input()
a = []
cnt = 0
flag = 0
s = set()
shifts = 0
if k >= n:
	for i in range(n):
		if l[i] == 1:
			cnt += 1
	for x in q:
		if x == '?':
			print(cnt)
else:
	for i in range(k):
		if l[i] == 1:
			cnt += 1
	a.append((0, cnt))
	s.add((0, cnt))
	m = (0, cnt)
	for i in range(1, n):
		cnt = cnt - l[(i - 1) % n] + l[(i + k - 1) % n]
		if i <= n - k:
			s.add((i, cnt))
			if m[1] < cnt:
				m = (i, cnt)
		a.append((i, cnt))
	for x in q:
		if x == '?':
			print(m[1])
		elif x == '!':
			s.remove(a[(n - k - shifts) % n])
			shifts += 1
			s.add(a[-shifts % n])
			if m[1] < a[-shifts % n][1]:
				m = a[-shifts % n]
			if (m[0] + shifts) % n + k > n:
				m = max(s, key=lambda x: x[1])


(N, K, P) = map(int, input().split())
nums = list((int(token) for token in input().split()))
if K > N:
	K = N
tw = sum(nums[:K])
windows = []
for idx in range(N):
	windows.append(tw)
	tw -= nums[idx]
	tw += nums[(idx + K) % N]
mts = [list(windows)]
mdist = 1
while mdist <= len(windows):
	mt = [max(mts[-1][idx], mts[-1][(idx + mdist) % N]) for idx in range(len(windows))]
	mts.append(mt)
	mdist *= 2
start = 0
commands = input()
for command in commands:
	if command == '?':
		logdist = len(mts) - 1
		dist = 2 ** logdist
		f = start
		remain = N - K + 1
		ans = 0
		while remain:
			if dist <= remain:
				ans = max(ans, mts[logdist][f])
				f = (f + dist) % N
				remain -= dist
			logdist -= 1
			dist //= 2
		print(ans)
	else:
		start = (start - 1) % N


(n, k, p) = map(int, input().split(' '))
arr = [int(a) for a in input().split(' ')]
arr = arr[:n] * 2
m = [0] * 2 * n
s = [0] * 2 * (n + 1)
count = [0] * (n + 1)
ma = 0
for i in range(2 * n - 1, -1, -1):
	s[i] = s[i + 1]
	if arr[i] == 1:
		s[i] = s[i + 1] + 1
if k > n:
	k = n
for i in range(n, 2 * n - k + 1):
	count[s[i] - s[min(i + k, 2 * n)]] += 1
	if s[i] - s[min(i + k, 2 * n)] > ma:
		ma = s[i] - s[min(i + k, 2 * n)]
ops = input()
ops = ops[:p]
b = 0
count_init = [_ for _ in count]
ma_init = ma
for i in ops:
	if i == '?':
		print(ma)
	else:
		if b != 0 and (b + 1) % n == 0:
			count = [_ for _ in count_init]
			ma = ma_init
			b = 0
			continue
		count[s[max(n - 1 - b, 0)] - s[min(max(n - 1 - b, 0) + k, 2 * n)]] += 1
		count[s[max(0, 2 * n - k - b)] - s[min(2 * n, max(0, 2 * n - b - k) + k)]] -= 1
		if s[max(n - 1 - b, 0)] - s[min(max(n - 1 - b, 0) + k, 2 * n)] > ma:
			ma = s[max(n - 1 - b, 0)] - s[min(max(n - 1 - b, 0) + k, 2 * n)]
		while count[ma] == 0:
			ma -= 1
		b += 1


import queue as Q

class Pair:

	def __init__(self, first, second):
		self.first = first
		self.second = second

	def __lt__(self, other):
		if self.first != other.first:
			return self.first > other.first
		else:
			return self.second > other.second
instr = input()
(n, k, q) = map(int, instr.split(' '))
s = input()
s = s.replace(' ', '')
qs = input()
i = int(0)
sl = len(s)
mx = int(0)
lq = len(qs)
count1 = s.count('1')
if k >= n:
	for j in range(0, lq):
		if qs[j] == '?':
			print(count1)
else:
	pq = Q.PriorityQueue()
	cnt = int(0)
	i = n - 1
	while i >= 0 and i >= n - k:
		cnt = cnt + int(s[i])
		i = i - 1
	x = 0
	pq.put(Pair(cnt, x))
	x = x + 1
	while i >= 0:
		cnt = cnt + int(s[i])
		cnt = cnt - int(s[i + k])
		i = i - 1
		pq.put(Pair(cnt, x))
		x = x + 1
	qcnt = int(0)
	for j in range(0, lq):
		if qs[j] == '?':
			while not pq.empty():
				p = pq.get()
				if p.second >= qcnt:
					print(p.first)
					pq.put(p)
					break
		else:
			s = s[n - 1] + s
			cnt = cnt + int(s[0])
			cnt = cnt - int(s[k])
			pq.put(Pair(cnt, x))
			x = x + 1
			qcnt = qcnt + 1


from collections import deque
(n, k, p) = map(int, input().split())
a = list(map(int, input().split()))
s = input().strip()
k = min(k, n)
b = a + a
sums = [sum(b[:k])]
for i in range(k, len(b)):
	sums.append(sums[-1] - b[i - k] + b[i])
maxs = []
window = n - k + 1
q = deque()
for i in range(window):
	while q and sums[i] > sums[q[-1]]:
		q.pop()
	q.append(i)
maxs.append(sums[q[0]])
for i in range(window, len(sums)):
	while q and q[0] <= i - window:
		q.popleft()
	while q and sums[i] > sums[q[-1]]:
		q.pop()
	q.append(i)
	maxs.append(sums[q[0]])
shift = n
for c in s:
	if c == '!':
		shift -= 1
		if shift <= 0:
			shift += n
	else:
		ans = maxs[shift]
		print(ans)


class SegTree:

	def __init__(self, a):
		self.n = 1 << len(a).bit_length()
		self.size = self.n << 1
		self.tree = [0] * self.n + a + [0] * (self.n - len(a))
		for i in range(self.n - 1, 0, -1):
			self.tree[i] = max(self.tree[i << 1], self.tree[i << 1 | 1])

	def query(self, i, j):
		res = 0
		i += self.n
		j += self.n
		while i <= j:
			if i & 1 == 1:
				res = max(res, self.tree[i])
			if j & 1 == 0:
				res = max(res, self.tree[j])
			i = i + 1 >> 1
			j = j - 1 >> 1
		return res
(n, k, p) = map(int, input().split())
a = list(map(int, input().split()))
s = input().strip()
k = min(k, n)
b = a + a
sums = [sum(b[:k])]
for i in range(k, len(b)):
	sums.append(sums[-1] - b[i - k] + b[i])
st = SegTree(sums)
shift = n
for c in s:
	if c == '!':
		shift -= 1
		if shift <= 0:
			shift += n
	else:
		ans = st.query(shift, shift + n - k)
		print(ans)