Chef has a sequence $A_1, A_2, \ldots, A_N$; each element of this sequence is either $0$ or $1$. Appy gave him a string $S$ with length $Q$ describing a sequence of queries. There are two types of queries:
- '!': right-shift the sequence $A$, i.e. replace $A$ by another sequence $B_1, B_2, \ldots, B_N$ satisfying $B_{i+1} = A_i$ for each valid $i$ and $B_1 = A_N$
- '?': find the length of the longest contiguous subsequence of $A$ with length $\le K$ such that each element of this subsequence is equal to $1$
Answer all queries of the second type.

-----Input-----
- The first line of the input contains three space-separated integers $N$, $Q$ and $K$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.
- The third line contains a string with length $Q$ describing queries. Each character of this string is either '?', denoting a query of the second type, or '!', denoting a query of the first type.

-----Output-----
For each query of the second type, print a single line containing one integer — the length of the longest required subsequence.

-----Constraints-----
- $1 \le K \le N \le 10^5$
- $1 \le Q \le 3 \cdot 10^5$
- $0 \le A_i \le 1$ for each valid $i$
- $S$ contains only characters '?' and '!'

-----Subtasks-----
Subtask #1 (30 points):
- $1 \le N \le 10^3$
- $1 \le Q \le 3 \cdot 10^3$
Subtask #2 (70 points): original constraints 

-----Example Input-----
5 5 3
1 1 0 1 1
?!?!?    

-----Example Output-----
2
3
3

-----Explanation-----
- In the first query, there are two longest contiguous subsequences containing only $1$-s: $A_1, A_2$ and $A_4, A_5$. Each has length $2$.
- After the second query, the sequence $A$ is $[1, 1, 1, 0, 1]$.
- In the third query, the longest contiguous subsequence containing only $1$-s is $A_1, A_2, A_3$.
- After the fourth query, $A = [1, 1, 1, 1, 0]$.
- In the fifth query, the longest contiguous subsequence containing only $1$-s is $A_1, A_2, A_3, A_4$ with length $4$. However, we only want subsequences with lengths $\le K$. One of the longest such subsequences is $A_2, A_3, A_4$, with length $3$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Preprocessing

Data structures

Range queries

Segment trees revisited


Solutions:
(n, q, k) = map(int, input().split(' '))
l = list(map(int, input().split(' ')))
l2 = list(l)
stri = input()
stinds = -1
x = str()
stinde = -1
endinds = n
endinde = n
mx = -1
mxinds = -1
mxinde = -1
mx2inds = -1
mx2inde = -1
cou = 0
mxind = -1
mx2ind = -1
(st, ed, mx2) = (0, 0, 0)
(co1, co0) = (0, 0)
for i in l:
	if i == 0:
		co0 = co0 + 1
	else:
		co1 = co1 + 1
for i in range(n):
	if l[i] == 0 and i != 0:
		stinds = 0
		stinde = i - 1
		break
	if l[i] == 0 and i == 0:
		stinds = -1
		stinde = -1
		break
if co1 == n:
	st = n
	stinde = n - 1
	stinds = 0
elif stinds == -1 and stinde == -1:
	st = 0
else:
	st = stinde - stinds + 1
if co1 == n:
	ed = 0
else:
	for i in range(n - 1, -1, -1):
		if l[i] == 0 and i != n - 1:
			endinds = i + 1
			endinde = n - 1
			ed = endinde - endinds + 1
			break
		elif l[i] == 0 and i == n - 1:
			ed = 0
			break
for i in range(stinde + 1, endinds):
	if l[i] == 1:
		cou = cou + 1
		if cou == 1:
			mxind = i
	if l[i] == 0:
		if cou > mx:
			mx = cou
			mxinds = mxind
			mxinde = i - 1
			cou = 0
		else:
			cou = 0
cou = 0
mx2 = -1
for i in range(mxinds, mxinde + 1):
	l2[i] = 0
for i in range(stinde + 1, endinds):
	if l2[i] == 1:
		cou = cou + 1
		if cou == 1:
			mx2ind = i
	if l2[i] == 0:
		if cou > mx2:
			mx2 = cou
			mx2inds = mx2ind
			mx2inde = i - 1
			cou = 0
		else:
			cou = 0
a = max(mx, mx2, st, ed)
if a == st:
	lol = 1
elif a == mx2:
	lol = 2
elif a == mx:
	lol = 3
elif a == ed:
	lol = 4
if st + ed > mx:
	lol1 = 2
else:
	lol1 = 2
lol = 0
hai = 1
for i in stri:
	if i == '!':
		if ed > 0:
			if stinds != -1:
				stinde = (stinde + 1) % n
			st = st + 1
			ed = ed - 1
			if mxinds != -1:
				mxinds = (mxinds + 1) % n
				mxinde = (mxinde + 1) % n
			if mx2inds != -1:
				mx2inds = (mx2inds + 1) % n
				mx2inde = (mx2inde + 1) % n
			a = max(st, ed, mx, mx2)
		elif ed == 0 and x == 'st':
			hai = 0
			if stinds != -1:
				stinds = (stinds + 1) % n
				stinde = (stinde + 1) % n
			if mxinds != -1:
				mxinds = (mxinds + 1) % n
				mxinde = (mxinde + 1) % n
			if stinde - stinds < 0:
				st = max(stinde + 1, n - stinds)
			else:
				st = stinde - stinds + 1
			if mx2inds != -1:
				mx2inds = (mx2inds + 1) % n
				mx2inde = (mx2inde + 1) % n
			if stinds == 0:
				hai = 1
			a = max(st, ed, mx, mx2)
			if mxinde > mx2inde and mxinde > stinde:
				if mxinde == n - 1:
					x = 'mx'
				elif hai == 1:
					x = 'mom'
			if mx2inde > mxinde and mx2inde > stinde:
				if mx2inde == n - 1:
					x = 'mx2'
				elif hai == 1:
					x = 'mom'
			if mx2inde < stinde and mxinde < stinde:
				if stinde == n - 1:
					x = 'st'
				elif hai == 1:
					x = 'mom'
		elif ed == 0 and x == 'mx2':
			hai = 0
			if stinde != -1:
				stinds = (stinds + 1) % n
				stinde = (stinde + 1) % n
			mx2inds = (mx2inds + 1) % n
			mx2inde = (mx2inde + 1) % n
			if mx2inde - mx2inds < 0:
				mx2 = max(mx2inde + 1, n - mx2inds)
			else:
				mx2 = mx2inde - mx2inds + 1
			if mxinds != -1:
				mxinds = (mxinds + 1) % n
				mxinde = (mxinde + 1) % n
			if mx2inds == 0:
				hai = 1
			a = max(st, ed, mx, mx2)
			if mxinde > mx2inde and mxinde > stinde:
				if mxinde == n - 1:
					x = 'mx'
				elif hai == 1:
					x = 'mom'
			if mx2inde > mxinde and mx2inde > stinde:
				if mx2inde == n - 1:
					x = 'mx2'
				elif hai == 1:
					x = 'mom'
			if mx2inde < stinde and mxinde < stinde:
				if stinde == n - 1:
					x = 'st'
				elif hai == 1:
					x = 'mom'
		elif ed == 0 and x == 'mx':
			hai = 0
			if stinds != -1:
				stinds = (stinds + 1) % n
				stinde = (stinde + 1) % n
			if mxinds != -1:
				mxinds = (mxinds + 1) % n
				mxinde = (mxinde + 1) % n
			if mxinds == 0:
				hai = 1
			if mxinde - mxinds < 0:
				mx = max(mxinde + 1, n - mxinds)
			else:
				mx = mxinde - mxinds + 1
			if mx2inds != -1:
				mx2inds = (mx2inds + 1) % n
				mx2inde = (mx2inde + 1) % n
			a = max(st, ed, mx, mx2)
			if mxinde > mx2inde and mxinde > stinde:
				if mxinde == n - 1:
					x = 'mx'
				elif hai == 1:
					x = 'mom'
			if mx2inde > mxinde and mx2inde > stinde:
				if mx2inde == n - 1:
					x = 'mx2'
				elif hai == 1:
					x = 'mom'
			if mx2inde < stinde and mxinde < stinde:
				if stinde == n - 1:
					x = 'st'
				elif hai == 1:
					x = 'mom'
		elif ed == 0 and (x == 'mom' or lol == 0):
			if stinds != -1:
				stinds = (stinds + 1) % n
				stinde = (stinde + 1) % n
			if mxinds != -1:
				mxinds = (mxinds + 1) % n
				mxinde = (mxinde + 1) % n
			if mx2inds != -1:
				mx2inds = (mx2inds + 1) % n
				mx2inde = (mx2inde + 1) % n
			a = max(st, ed, mx, mx2)
			if mxinde > mx2inde and mxinde > stinde:
				if mxinde == n - 1:
					x = 'mx'
					lol = 1
				else:
					x = 'mom'
					lol = 1
			if mx2inde > mxinde and mx2inde > stinde:
				if mx2inde == n - 1:
					x = 'mx2'
					lol = 1
				else:
					x = 'mom'
					lol = 1
			if mx2inde < stinde and mxinde < stinde:
				if stinde == n - 1:
					x = 'st'
					lol = 1
				else:
					x = 'mom'
					lol = 1
	if i == '?' and co1 == n:
		if n < k:
			print(n)
		else:
			print(k)
	elif i == '?' and co0 == n:
		print(0)
	elif i == '?' and co0 != n:
		if a < k:
			print(a)
		else:
			print(k)


def calc_subseq_lengths():
	(li, tmp, ctr) = ([[0, 0], [0, 0]], A + A[:A.index('0') + 1], 0)
	for i in range(A.index('0'), len(tmp)):
		if tmp[i] == '1':
			ctr += 1
		else:
			li.append([ctr, i - ctr])
			ctr = 0
	return sorted(li)[-2:]
(N, Q, K) = map(int, input().split())
A = ''.join(input().split())
S = input()
if '0' not in A:
	(seq1, seq2) = ([N, 0], [N, 0])
else:
	(seq1, seq2) = calc_subseq_lengths()
if seq1[0] >= K and seq2[0] >= K:
	print('\n'.join([str(K)] * S.count('?')))
elif seq1[0] == seq2[0]:
	print('\n'.join([str(seq1[0])] * S.count('?')))
else:
	for query in S:
		if query == '!':
			seq1[1] = (seq1[1] + 1) % N
			seq2[1] = (seq2[1] + 1) % N
		else:
			flag = [sum(seq1) >= N, sum(seq2) >= N]
			cLen = [seq1[0] if not flag[0] else max(N - seq1[1], seq1[0] - (N - seq1[1])), seq2[0] if not flag[1] else max(N - seq2[1], seq2[0] - (N - seq2[1]))]
			print(min(max(cLen), K))


from operator import itemgetter
(n, a, k) = (int(i) for i in input().split())
arr = [int(i) for i in input().split()]
t = input()
counts = []
(sum1, sum0) = (0, 0)
for bit in arr:
	if bit == 1:
		sum1 += 1
		if sum0 < 0:
			counts.append(sum0)
			sum0 = 0
	if bit == 0:
		if sum1 > 0:
			counts.append(sum1)
			sum1 = 0
		sum0 -= 1
if sum0 < 0:
	counts.append(sum0)
if sum1 > 0:
	counts.append(sum1)
lenC = 0
ind = -1
flag = True
oldans = -1
countsleng = -1
for c in t:
	if c == '!':
		lenC = len(counts) - 1
		if ind == lenC or ind == 0:
			flag = True
		if counts[lenC] > 0:
			counts[lenC] -= 1
			if counts[lenC] == 0:
				counts.pop()
			if counts[0] > 0:
				counts[0] += 1
			else:
				counts.insert(0, 1)
				ind += 1
		else:
			counts[lenC] += 1
			if counts[lenC] == 0:
				counts.pop()
			if counts[0] <= 0:
				counts[0] -= 1
			else:
				counts.insert(0, -1)
				ind += 1
		if counts[ind] < counts[0] and counts[0] <= k:
			flag = True
		elif counts[ind] < counts[len(counts) - 1] and counts[len(counts) - 1] <= k:
			flag = True
	elif ind == -1 or flag:
		a = [[counts[i], i] for i in range(len(counts)) if counts[i] > 0]
		if a != []:
			flag = False
			res = max(a, key=itemgetter(0))
			if res[0] > k:
				flag = True
				res[0] = k
			ind = res[1]
			print(res[0])
			oldans = res[0]
		else:
			ind = -1
			flag = True
			print(0)
			oldans = 0
	else:
		print(counts[ind])


def amit(input):
	answer = list(map(len, input.split('0')))
	return answer

def amit2(arr, n):
	count = 0
	result = 0
	ind = 0
	for i in range(0, n):
		if arr[i] == 0:
			count = 0
		else:
			count += 1
			if result < count:
				ind = i
			result = max(result, count)
	return (result, ind)
(n, q, k) = map(int, input().split())
arr = [i for i in input().split()]
ar = [int(i) for i in arr]
qer = k
s = ''.join(arr)
ans = -2
if arr.count('0') == n:
	ans = -1
if arr.count('1') == n:
	ans = -3
query = input()
strike = 0
dic = {}
xolo = amit(s)
colo = xolo[:]
wolo = xolo[:]
real = max(xolo)
if ar[-1] == 1 and ar[0] == 1:
	strike = 1
if ans == -1:
	for i in query:
		if i == '?':
			print(0)
elif ans == -3:
	for i in query:
		if i == '?':
			print(k)
elif xolo.count(max(xolo)) > 1 and strike == 0:
	k = min(max(xolo), k)
	dic[0] = k
	count = 0
	for i in range(1, len(arr) + 1):
		dic[i] = k
	for i in query:
		if i == '?':
			if ans == -1:
				print(0)
				continue
			if ans == -3:
				print(k)
				continue
			print(dic[count])
		else:
			count += 1
			if count == n:
				count = 0
elif strike == 0:
	xolo.remove(real)
	fake = max(xolo)
	dic[0] = min(real, k)
	(maxy, ind) = amit2(ar, n)
	maxy -= 1
	gh = maxy + 1
	ind = n - ind - 1
	count = 0
	for i in range(1, len(arr) + 1):
		if count == ind:
			dic[i] = min(max(fake, maxy, gh - maxy), k)
			maxy -= 1
			if maxy == 0:
				count = real - 1
			continue
		else:
			count += 1
			dic[i] = min(real, k)
	count = 0
	for i in query:
		if i == '?':
			if ans == -1:
				print(0)
				continue
			if ans == -3:
				print(k)
				continue
			print(dic[count])
		else:
			count += 1
			if count == n:
				count = 0
else:
	rolo = colo[:]
	rolo.remove(real)
	fake = max(rolo)
	(maxy, ind) = amit2(ar, n)
	ind = n - ind - 1
	maxy -= 1
	fake2 = fake
	if xolo.count(max(xolo)) == 1 and colo[-1] != max(xolo) and (colo[0] != max(xolo)):
		fake = real
	len1 = colo[0]
	len2 = colo[-1]
	k = qer
	dic[0] = min(real, k)
	i = 1
	while i != len2 + 1:
		dic[i] = min(max(len1 + i, len2 - i, fake), k)
		i += 1
	lo = 1
	while lo != len1:
		dic[n - lo] = min(max(len1 - lo, len2 + lo, fake), k)
		lo += 1
	count = 0
	gh = maxy + 1
	for j in range(1, len(arr) + 1):
		if count == ind:
			if j not in dic:
				dic[j] = min(max(len1 + len2, fake2, maxy, gh - maxy), k)
			maxy -= 1
			if maxy == 0:
				count = real - 1
			continue
		else:
			count += 1
			if j not in dic:
				dic[j] = min(max(real, len1 + len2), k)
	count = 0
	for i in query:
		if i == '?':
			if ans == -1:
				print(0)
				continue
			if ans == -3:
				print(k)
				continue
			print(dic[count])
		else:
			count += 1
			if count == n:
				count = 0


def l(b):
	e = []
	i = 0
	j = 0
	while True:
		d = 0
		if b[i] == 1:
			for j in range(i, a[0]):
				if b[j] != 1 or j == a[0] - 1:
					if j == a[0] - 1 and b[j] == 1:
						e.append(d + 1)
					else:
						e.append(d)
					i = j + 1
					break
				else:
					d = d + 1
		else:
			i = i + 1
		if j == a[0] - 1 or i == a[0]:
			break
	return e
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = input()
f = l(b)
n = c.count('?')
if a[1] > 50000:
	if len(f) == 0:
		for i in range(n):
			print(0)
	else:
		right = a[0] - 1
		left = 0
		if len(f) >= 2:
			so = sorted(f)
			m1 = vm = so[-1]
			m2 = so[-2]
			i1 = f.index(m1)
			i2 = f.index(m2)
		else:
			m1 = vm = f[0]
			m2 = 0
			i1 = 0
			i2 = 'a'
		for i in range(len(c)):
			if c[i] == '?':
				n = n - 1
				if vm >= a[2]:
					print(a[2])
				else:
					print(vm)
			elif b[right] == 0:
				right = right - 1
				left = left - 1
			elif b[right] == 1:
				f[-1] = f[-1] - 1
				right = right - 1
				if f[-1] == 0:
					if i1 == len(f) - 1:
						i1 = 0
						m1 = f[0]
					elif i2 == len(f) - 1:
						i2 = 0
						m2 = f[0]
					del f[-1]
					if len(f) == 1:
						m1 = f[0]
						i1 = 0
						m2 = 0
						i2 = 'a'
				if b[left] == 1:
					f[0] = f[0] + 1
				else:
					f.insert(0, 1)
					if len(f) == 2:
						m2 = 1
						i2 = 0
					else:
						i1 = i1 + 1
						i2 = i2 + 1
				left = left - 1
			if right == -1:
				right = a[0] - 1
			if left == -a[0]:
				left = 0
			if len(f) == 2:
				vm = max(f[0], f[1])
			elif len(f) == 1:
				vm = f[0]
			elif i1 == len(f) - 1:
				if i2 == 'a':
					vm = max(f[-1], f[0])
				else:
					vm = max(f[-1], f[0], f[i2])
			elif i2 == len(f) - 1:
				vm = max(f[-1], f[0], f[i1])
			else:
				vm = f[i1]
			if n == 0:
				break
elif len(f) == 0:
	for i in range(n):
		print(0)
else:
	right = a[0] - 1
	left = 0
	for i in range(len(c)):
		if c[i] == '?':
			n = n - 1
			v = sorted(f)
			if v[-1] >= a[2]:
				print(a[2])
			else:
				print(v[-1])
		elif b[right] == 0:
			right = right - 1
			left = left - 1
		elif b[right] == 1:
			f[-1] = f[-1] - 1
			right = right - 1
			if f[-1] == 0:
				del f[-1]
			if b[left] == 1:
				f[0] = f[0] + 1
			else:
				f.insert(0, 1)
			left = left - 1
		if n == 0:
			break
		if right == -1:
			right = a[0] - 1
		if left == -a[0]:
			left = 0


import math

def merge(l1, l2):
	(m1, p1, s1, z1) = l1
	(m2, p2, s2, z2) = l2
	if z1 == 0 and z2 == 0:
		result = [m1 + m2, m1 + m2, m1 + m2, 0]
	elif z1 == 0 and z2 == 1:
		result = [max(m1 + p2, m2), p1 + p2, s2, 1]
	elif z1 == 1 and z2 == 0:
		result = [max(m1, s1 + m2), p1, s1 + s2, 1]
	elif z1 == 1 and z2 == 1:
		result = [max(max(m1, m2), s1 + p2), p1, s2, 1]
	return result

def build(node, l, r):
	if l == r:
		if sequence[l] == 1:
			segTree[node] = [1, 1, 1, 0]
		else:
			segTree[node] = [0, 0, 0, 1]
	else:
		mid = (l + r) // 2
		build(2 * node, l, mid)
		build(2 * node + 1, mid + 1, r)
		(m1, p1, s1, z1) = segTree[2 * node]
		(m2, p2, s2, z2) = segTree[2 * node + 1]
		if z1 == 0 and z2 == 0:
			segTree[node] = [m1 + m2, m1 + m2, m1 + m2, 0]
		elif z1 == 0 and z2 == 1:
			segTree[node] = [max(m1 + p2, m2), p1 + p2, s2, 1]
		elif z1 == 1 and z2 == 0:
			segTree[node] = [max(m1, s1 + m2), p1, s1 + s2, 1]
		elif z1 == 1 and z2 == 1:
			segTree[node] = [max(max(m1, m2), s1 + p2), p1, s2, 1]

def segQuery(node, l, r, ql, qr):
	if l >= ql and r <= qr:
		return segTree[node]
	elif r < ql or l > qr:
		return [-1, -1, -1, -1]
	else:
		mid = (l + r) // 2
		(m1, p1, s1, z1) = segQuery(2 * node, l, mid, ql, qr)
		(m2, p2, s2, z2) = segQuery(2 * node + 1, mid + 1, r, ql, qr)
		if m1 == -1:
			return [m2, p2, s2, z2]
		elif m2 == -1:
			return [m1, p1, s1, z1]
		else:
			result = merge([m1, p1, s1, z1], [m2, p2, s2, z2])
			return result
firstInp = [int(x) for x in input().split()]
n = firstInp[0]
q = firstInp[1]
k = firstInp[2]
sequence = [int(x) for x in input().split()]
sequence = sequence * 2
shiftP = n
segNodes = 2 ** math.ceil(math.log(2 * n, 2) + 1)
segTree = [[-1, -1, -1, -1]] * segNodes
build(1, 0, 2 * n - 1)
queries = input()
for query in queries:
	if query == '!':
		shiftP -= 1
		if shiftP == 0:
			shiftP = n
	else:
		print(min(k, segQuery(1, 0, 2 * n - 1, shiftP, shiftP + n - 1)[0]))


supplementary_array = [i % 7 for i in range(98)]
(n, q, k) = map(int, input().split())
a = [int(o) for o in input().split()]
ui = a.count(0)
uo = a.count(1)
ghy = [0] * (n + 1)
a.extend(ghy)
s = input()
s = list(s)
for i in range(n):
	a[n + i] = a[i]
if ui == n:
	for i in range(s.count('?')):
		print('0')
elif uo == n:
	for i in range(s.count('?')):
		print(min(k, n))
else:
	first_first = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	first_first = sorted(first_first)
	second_second = [0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	the_index_of_maximum_element = 0
	x = 1
	b = 2
	l = n
	r = 2 * n - 1
	i = 2 * n - 1
	while i >= n:
		if a[i] == 0:
			break
		else:
			r -= 1
			l -= 1
		i -= 1
	yi_yi_ya = l
	oh_yi_ye = l
	counter_of_elements = 0
	for i in range(l, r + 1):
		if a[i] == 0:
			if counter_of_elements >= first_first[x]:
				if first_first[x] != 0:
					second_second[x] = first_first[x]
					second_second[the_index_of_maximum_element] = first_first[the_index_of_maximum_element]
					second_second[b] = first_first[b]
					supplementary_array = sorted(supplementary_array)
					(supplementary_array[0], supplementary_array[-1]) = (supplementary_array[-1], supplementary_array[0])
				first_first[x] = counter_of_elements
				first_first[the_index_of_maximum_element] = yi_yi_ya
				first_first[b] = i - 1
				(supplementary_array[8], supplementary_array[45]) = (supplementary_array[45], supplementary_array[8])
			elif counter_of_elements > second_second[x]:
				second_second[x] = counter_of_elements
				second_second[the_index_of_maximum_element] = yi_yi_ya
				second_second[b] = i - 1
				(supplementary_array[87], supplementary_array[25]) = (supplementary_array[87], supplementary_array[45])
			counter_of_elements = 0
			yi_yi_ya = 0
		else:
			if counter_of_elements == 0:
				yi_yi_ya = i
			counter_of_elements += 1
	index_of_left_of_first = n
	index_of_right_of_first = 2 * (n - 1)
	for i in range(q):
		if s[i] == '?':
			final_value_of_result = 0
			if index_of_left_of_first >= first_first[the_index_of_maximum_element] and index_of_left_of_first <= first_first[b]:
				(supplementary_array[87], supplementary_array[25]) = (supplementary_array[87], supplementary_array[45])
				(supplementary_array[8], supplementary_array[45]) = (supplementary_array[45], supplementary_array[8])
				z = (first_first[the_index_of_maximum_element] + first_first[b]) // 2
				if index_of_left_of_first <= z:
					p = first_first[b] - index_of_left_of_first + 1
					(supplementary_array[87], supplementary_array[25]) = (supplementary_array[87], supplementary_array[45])
					(supplementary_array[8], supplementary_array[45]) = (supplementary_array[45], supplementary_array[8])
				else:
					p = index_of_left_of_first - first_first[the_index_of_maximum_element]
					(supplementary_array[87], supplementary_array[25]) = (supplementary_array[87], supplementary_array[45])
					(supplementary_array[8], supplementary_array[45]) = (supplementary_array[45], supplementary_array[8])
				if p > second_second[x]:
					final_value_of_result = p
					(supplementary_array[87], supplementary_array[25]) = (supplementary_array[87], supplementary_array[45])
					(supplementary_array[8], supplementary_array[45]) = (supplementary_array[45], supplementary_array[8])
				else:
					final_value_of_result = second_second[x]
					(supplementary_array[87], supplementary_array[25]) = (supplementary_array[87], supplementary_array[45])
					(supplementary_array[8], supplementary_array[45]) = (supplementary_array[45], supplementary_array[8])
			elif index_of_left_of_first + n >= first_first[the_index_of_maximum_element] and index_of_left_of_first + n <= first_first[b]:
				z = (first_first[the_index_of_maximum_element] + first_first[b]) // 2
				(supplementary_array[87], supplementary_array[25]) = (supplementary_array[87], supplementary_array[45])
				(supplementary_array[8], supplementary_array[45]) = (supplementary_array[45], supplementary_array[8])
				if index_of_left_of_first + n <= z:
					p = first_first[b] - (index_of_left_of_first + n) + 1
					(supplementary_array[87], supplementary_array[25]) = (supplementary_array[87], supplementary_array[45])
					(supplementary_array[8], supplementary_array[45]) = (supplementary_array[45], supplementary_array[8])
				else:
					p = index_of_left_of_first + n - first_first[the_index_of_maximum_element]
				if p > second_second[x]:
					final_value_of_result = p
				else:
					final_value_of_result = second_second[x]
					(supplementary_array[87], supplementary_array[25]) = (supplementary_array[87], supplementary_array[45])
					(supplementary_array[8], supplementary_array[45]) = (supplementary_array[45], supplementary_array[8])
			else:
				final_value_of_result = first_first[x]
			print(min(final_value_of_result, k))
		else:
			index_of_left_of_first -= 1
			index_of_right_of_first -= 1
			if index_of_left_of_first == 0:
				index_of_left_of_first = n
				index_of_right_of_first = 2 * (n - 1)
			(supplementary_array[87], supplementary_array[25]) = (supplementary_array[87], supplementary_array[45])
			(supplementary_array[8], supplementary_array[45]) = (supplementary_array[45], supplementary_array[8])


from collections import Counter

def shift(a):
	return a[-1] + a[:-1]

def long(a):
	b = []
	max1 = 0
	for i in range(len(a)):
		if a[i] == '1':
			max1 += 1
		else:
			b.append(max1)
			max1 = 0
	b.append(max1)
	b.sort(reverse=True)
	if len(b) > 1:
		return [b[0], b[1]]
	else:
		return [b[0], b[0]]

def pos(a, n):
	if a[0:n] == '1' * n:
		return 1
	elif a[len(a) - n:] == '1' * n:
		return 2
	else:
		return 3

def start(a):
	count = 0
	for i in range(len(a)):
		if a[i] == '1':
			count += 1
		else:
			break
	return count

def end(a):
	count = 0
	i = len(a) - 1
	while i >= 0:
		if a[i] == '1':
			count += 1
		else:
			break
		i -= 1
	return count
(n, q, k) = map(int, input().split())
a = [str(x) for x in input().split()]
bi = ''
si = ''
for i in a:
	bi += i
	si += i
s = input()
if n <= 1000 and q <= 3000:
	for i in range(q):
		if s[i] == '?':
			print(min(long(bi)[0], k))
		else:
			bi = shift(bi)
else:
	d = Counter(s)
	u = Counter(a)
	if d['?'] != 0:
		arr = long(bi)
		f = min(arr[0], k)
		e = arr[1]
		val = [f]
		st = start(bi)
		en = end(bi)
		for i in range(d['!']):
			r = pos(bi, f)
			bi = shift(bi)
			if si == bi:
				break
			if bi[0] == '1':
				st += 1
				st = min(st, u['1'])
				en -= 1
				en = max(0, en)
				if r == 1:
					if max(st, en) >= e:
						f = max(st, en)
					else:
						f = e
						e = max(st, en)
					val.append(min(f, k))
				elif r == 2:
					if max(st, en) >= e:
						f = max(st, en)
					else:
						f = e
						e = max(st, en)
					val.append(min(f, k))
				else:
					val.append(val[-1])
			else:
				st = 0
				en = end(bi)
				f = max(en, f)
				val.append(min(f, k))
		y = len(val)
		l = 0
		for i in range(q):
			if s[i] == '?':
				print(val[l % y])
			else:
				l += 1


(n, q, k) = map(int, input().split())
ays = list(map(int, input().split()))
qs = input().strip()
asum = sum(ays)
if asum == n or asum < 2:
	ans = [min(asum, k)] * qs.count('?')
else:
	ans = []
	run = []
	last = 0
	for (ix, a) in enumerate(ays):
		if a == 1:
			if last == 0:
				run.append([1, ix])
			else:
				run[-1][0] += 1
		last = a
	mark = 0
	if last == 1 and ays[0] == 1:
		(mark, _) = run.pop()
		run[0][0] += mark
	run.sort(reverse=True)
	(main, st) = run[0]
	if st > 0:
		st += mark
	en = st + main
	if len(run) > 1:
		spare = run[1][0]
	else:
		spare = 0
	mk = min(main, k)
	if spare >= k or main >= 2 * k or main == spare:
		ans = [mk] * qs.count('?')
	else:
		for c in qs:
			if c == '!':
				mark -= 1
				if mark < 0:
					mark += n
			elif mark > st and mark < en:
				m1 = mark - st
				m2 = en - mark
				ans.append(min(max(m1, m2, spare), k))
			else:
				ans.append(mk)
print('\n'.join(map(str, ans)))


(n, q, k) = map(int, input().split())
a = list(map(int, input().split()))
f = 0
if a.count(1) == n:
	f = 1
else:
	l1 = a.index(0)
	l2 = a[::-1].index(0)
	m1 = 0
	m2 = 0
	i = l1
	i1 = 0
	i2 = 0
	f2 = 0
	while i < n - l2:
		if a[i] == 1:
			j = i
			f2 = 1
			while j < n - l2 and a[j] == 1:
				j += 1
			if j - i > m1:
				m2 = m1
				i2 = i1
				m1 = j - i
				i1 = i
			elif j - i > m2:
				m2 = j - i
				i2 = i
			i = j
		i += 1
s = input()
r = 0
for i in s:
	if i == '?':
		if f == 1:
			m = n
		elif r <= l2:
			m = max(m1, m2, l1 + r, l2 - r)
		elif f2 == 1 and r > n - (m1 + i1) and (r < n - i1):
			m = max(l1 + l2, m2, n - i1 - r, r - (n - i1 - m1))
		elif r > n - l1:
			m = max(m1, m2, r - (n - l1), l1 + l2 - (r - (n - l1)))
		else:
			m = max(m1, l1 + l2)
		if m > k:
			print(k)
		else:
			print(m)
	else:
		r += 1
		r = r % n


import heapq as hq
import collections
(n, q, k) = map(int, input().split())
arr = list(map(int, input().split()))
s = input().strip()
d = {}
h = []
qq = []
count = 0
flag = 0
for i in range(n):
	if arr[i] == 0:
		if flag == 1:
			qq.append(count)
			if count in d.keys():
				d[count] += 1
			else:
				d[count] = 1
				hq.heappush(h, -count)
			flag = 0
			count = 0
	else:
		count += 1
		if flag == 0:
			flag = 1
if flag == 1:
	qq.append(count)
	if count in d.keys():
		d[count] += 1
	else:
		d[count] = 1
		hq.heappush(h, -count)
queue = collections.deque(qq)
mod = n
curr = n - 1
flag = arr[0]
hq.heapify(h)
for i in range(q):
	if s[i] == '!':
		if arr[curr] == 1:
			if len(queue) != 0:
				c = queue.pop()
				d[c] -= 1
				if d[c] == 0:
					del d[c]
				if c != 1:
					queue.append(c - 1)
					if c - 1 in d.keys():
						d[c - 1] += 1
					else:
						d[c - 1] = 1
						hq.heappush(h, -(c - 1))
				if flag == 0:
					c = 0
				else:
					c = queue.popleft()
					d[c] -= 1
					if d[c] == 0:
						del d[c]
				queue.appendleft(c + 1)
				flag = 1
				if c + 1 in d.keys():
					d[c + 1] += 1
				else:
					d[c + 1] = 1
					hq.heappush(h, -(c + 1))
		else:
			flag = 0
		curr = (curr - 1) % mod
	elif h == []:
		print(0)
	else:
		while True:
			p = -hq.heappop(h)
			if p in d.keys():
				print(min(p, k))
				hq.heappush(h, -p)
				break
			elif h == []:
				print(0)
				break


(n, q, k) = input().split()
(n, q, k) = [int(n), int(q), int(k)]
a = list(map(int, input().split()))
q = input()
sum1 = 0
max1 = 0
for i in range(n):
	sum1 = sum1 + a[i]
	if sum1 > max1:
		max1 = sum1
		st = i - max1 + 1
	if a[i] == 0:
		sum1 = 0
if max1 == n:
	for s in q:
		if s == '?':
			if n <= k:
				print(n)
			else:
				print(k)
else:
	sums = 0
	sumn = 0
	max2 = 0
	i = 0
	while i < n:
		sums = sums + a[i]
		if a[i] == 0:
			break
		i += 1
	i = n - 1
	while i >= 0:
		sumn = sumn + a[i]
		if a[i] == 0:
			break
		i -= 1
	sum1 = sums + sumn
	if sum1 > max1:
		max1 = sum1
		en = sums - 1
		st = n - sumn
	elif sum1 == max1:
		max1 = sum1
		en = sums - 1
		st = n - sumn
		max2 = max1
	else:
		en = st + max1 - 1
	if max2 == 0:
		sum2 = 0
		if st < en:
			i = 0
			if i == st:
				i = en + 1
			while i < n:
				if i == st:
					i = en + 1
				sum2 = sum2 + a[i]
				if sum2 > max2:
					max2 = sum2
				if a[i] == 0:
					sum2 = 0
				i += 1
		else:
			i = en + 1
			while i < st:
				sum2 = sum2 + a[i]
				if sum2 > max2:
					max2 = sum2
				if a[i] == 0:
					sum2 = 0
				i += 1
	for s in q:
		if s == '?':
			if st + max1 > n:
				a1 = (st + max1) % n
				a2 = max1 - a1
				a3 = max2
			else:
				a1 = max1
				a2 = 0
				a3 = 0
			if max(a1, a2, a3) <= k:
				print(max(a1, a2, a3))
			else:
				print(k)
		else:
			st += 1
			st = st % n


import bisect
import math
import numpy
(n, q, k) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
query = input()
lis = []
list1 = []
for j in range(n):
	if arr[j] == 0:
		lis.append(j)
fc = 0
for j in range(len(lis) - 1):
	if lis[j + 1] - lis[j] == 1:
		fc = fc + 1
if arr[0] == 0 and arr[n - 1] == 0:
	fc = fc + 1
dic = {}
temp = []
xxx = 0
for j in range(len(lis) - 1):
	temp.append(lis[j + 1] - lis[j] - 1)
if len(lis) != 0:
	if arr[0] + arr[n - 1] != 2:
		temp.append(lis[0])
		temp.append(n - lis[len(lis) - 1] - 1)
	else:
		temp.append(lis[0] + n - lis[len(lis) - 1] - 1)
temp.sort()
max1 = 0
max2 = 0
if len(lis) != 0:
	max1 = temp[len(temp) - 1]
	max2 = temp[len(temp) - 2]
if max1 == max2:
	xxx = max1
l1 = 0
r1 = 0
l2 = 0
r2 = 0
if len(lis) != 0:
	if lis[0] + n - lis[len(lis) - 1] - 1 == max1:
		l1 = (lis[len(lis) - 1] + 1) % n
		r1 = lis[0] - 1
		if r1 < 0:
			r1 = r1 + n
	elif lis[0] + n - lis[len(lis) - 1] - 1 == max2:
		l2 = (lis[len(lis) - 1] + 1) % n
		r2 = lis[0] - 1
		if r2 < 0:
			r2 = r2 + n
for j in range(len(lis) - 1):
	if lis[j + 1] - lis[j] - 1 == max1:
		l1 = lis[j] + 1
		r1 = lis[j + 1] - 1
	elif lis[j + 1] - lis[j] - 1 == max2:
		l2 = lis[j] + 1
		r2 = lis[j + 1] - 1
count = 0
for i in range(q):
	if query[i] == '!':
		count = count + 1
	elif len(lis) == n:
		print(0)
	elif len(lis) == n - 1:
		print(1)
	elif len(lis) == n - 2:
		l1 = arr.index(1)
		arr.reverse()
		l2 = n - 1 - arr.index(1)
		if l2 - l1 == 1 or (l1 == 0 and l2 == n - 1):
			print(min(k, 2))
		else:
			print(1)
	elif len(lis) == 0:
		if n <= k:
			print(n)
		else:
			print(k)
	elif len(lis) == 1:
		if max((lis[0] + count) % n, n - 1 - (lis[0] + count) % n) <= k:
			print(max((lis[0] + count) % n, n - 1 - (lis[0] + count) % n))
		else:
			print(k)
	elif fc == len(lis) - 1:
		val = 0
		if (l1 + count) % n <= (r1 + count) % n:
			val = (r1 - l1) % n + 1
		else:
			val = max(n - (l1 + count) % n, (r1 + count) % n + 1)
		if val <= k:
			print(val)
		else:
			print(k)
	elif xxx != 0:
		if xxx <= k:
			print(xxx)
		else:
			print(k)
	elif (l1 + count) % n > (r1 + count) % n and (l2 + count) % n <= (r2 + count) % n:
		if max((r2 - l2) % n + 1, max((r1 + count) % n + 1, n - (l1 + count) % n)) <= k:
			print(max((r2 - l2) % n + 1, max((r1 + count) % n + 1, n - (l1 + count) % n)))
		else:
			print(k)
	elif (l1 + count) % n <= (r1 + count) % n and (l2 + count) % n > (r2 + count) % n:
		if max((r1 - l1) % n + 1, max((r2 + count) % n + 1, n - (l2 + count) % n)) <= k:
			print(max((r1 - l1) % n + 1, max((r2 + count) % n + 1, n - (l2 + count) % n)))
		else:
			print(k)
	elif max(max1, max2) <= k:
		print(max(max1, max2))
	else:
		print(k)


(n, q, k) = input().split()
(n, q, k) = [int(n), int(q), int(k)]
arr = list(map(int, input().split()))
s = input()
count = 0
_max = 0
check = 0
_max2 = 0
len_cross = 0
start = 0
max_len = 0
start1 = 0
end1 = 0
if arr.count(1) == 0:
	for _ in s:
		if _ == '?':
			print(0)
elif arr.count(0) == 0:
	for _ in s:
		if _ == '?':
			if n <= k:
				print(n)
			else:
				print(k)
else:
	arr.append(0)
	for i in range(0, n + 1):
		if arr[i] == 1:
			count += 1
			if count == 1:
				start = i
		else:
			if count >= _max:
				_max2 = _max
				_max = count
				max_start = start
				max_end = i - 1
			elif count > _max2:
				_max2 = count
			start = 0
			count = 0
	arr.pop()
	if arr[0] == 1 and arr[n - 1] == 1:
		check = 1
		if arr.count(0) > 0:
			end1 = ''.join((str(x) for x in arr)).index('0') - 1
			start1 = n - ''.join((str(x) for x in arr[::-1])).index('0')
		else:
			check = 0
	for _ in s:
		if _ == '?':
			if max_end >= max_start:
				max_len = max_end - max_start + 1
			else:
				max_len = max(n - max_start, max_end + 1)
			max_len = max(max_len, _max2)
			if check == 1:
				if start1 <= end1:
					len_cross = end1 - start1 + 1
				else:
					len_cross = max(n - start1, end1 + 1)
			if check == 1:
				if max(len_cross, max_len) <= k:
					print(max(len_cross, max_len))
				else:
					print(k)
			elif max_len <= k:
				print(max_len)
			else:
				print(k)
		elif _ == '!':
			max_start = max_start + 1
			max_end = max_end + 1
			if max_end == n:
				max_end = 0
			if max_start == n:
				max_start = 0
			if check == 1:
				start1 += 1
				end1 += 1
				if start1 == n:
					start1 = 0
				if end1 == n:
					end1 = 0


def longest_subsequence(d):
	d = d + [0]
	tmp = 0
	mx = -1
	s = -1
	e = -1
	store = []
	for i in range(n + 1):
		if d[i] == 0:
			e = i - 1
			if mx < max(mx, tmp):
				store = [[s, e]]
				mx = max(mx, tmp)
			elif mx == tmp:
				store.append([s, e])
			tmp = 0
		else:
			if tmp == 0:
				s = i
			tmp += 1
	return (mx, store)

def arraySegment(f):
	answer = []
	lenArr = len(f)
	tm = 0
	for i in range(lenArr - 1):
		if f[i] == 1 and f[i + 1] == 1:
			tm += 1
		elif tm == 0:
			continue
		else:
			answer.append(tm + 1)
			tm = 0
	return answer
(n, q, k) = map(int, input().split())
a = list(map(int, input().split()))
queries = list(input())
lastZero = -1
shift = 0
for i in range(1, n + 1):
	if a[-i] == 0:
		lastZero = n - i
		break
lastOne = lastZero + 1
a = a[lastOne:] + a[:lastOne]
shift += n - lastOne
(maxi, cluster) = longest_subsequence(a)
ans = []
if len(cluster) >= 2 or maxi == n:
	ans = [maxi] * n
else:
	arraySeg = arraySegment(a)
	arraySeg.sort(reverse=True)
	secHigh = 0
	if len(arraySeg) > 1:
		secHigh = arraySeg[1]
	tmp = n - cluster[0][1]
	while tmp > 0:
		if len(ans) == n:
			break
		ans.append(maxi)
		tmp -= 1
	tmp3 = maxi
	tmp4 = maxi
	if (tmp3 - 1) % 2 == 0:
		for i in range(tmp3 - 1):
			if len(ans) == n:
				break
			if i < (tmp3 - 1) // 2:
				tmp4 -= 1
				ans.append(max(tmp4, secHigh))
			else:
				ans.append(max(tmp4, secHigh))
				tmp4 += 1
	else:
		for i in range(tmp3 - 1):
			if len(ans) == n:
				break
			if i < (tmp3 - 1) // 2 + 1:
				tmp4 -= 1
				ans.append(max(tmp4, secHigh))
			else:
				tmp4 += 1
				ans.append(max(tmp4, secHigh))
	reamaining = n - len(ans)
	if reamaining > 0:
		ans = ans + [maxi] * reamaining
ans = ans[-shift:] + ans[:-shift]
queries_decode = []
tmp = 0
q = len(queries)
for i in range(q):
	if queries[i] == '?':
		queries_decode.append(tmp)
		continue
	else:
		tmp += 1
for i in queries_decode:
	j = i % n
	anss = ans[j]
	if anss > k:
		print(k)
	else:
		print(anss)


(n, q, kinput) = [int(i) for i in input().split()]
t = [int(i) for i in input().split()]
inputstr = str(input())
d = []
e = []
i = 0
length = len(t)
j = length - 1
ctr = 0
tp = 0
tp6 = 0
tp9 = 0
tp150 = 0
for f in range(length):
	if t[f] == 1:
		ctr = ctr + 1
z5 = []
for i7 in range(n // 10008):
	z5.append(n * i7)
waste10 = []
for i9 in range(n // 17895):
	waste10.append(q * (2 * i9))
if length >= 2:
	if ctr != length:
		while t[j] != 0:
			j = j - 1
		while t[i] != 0:
			i = i + 1
if i == 0 or j == length - 1:
	a = -10000014
	b = -15115454
	k = 0
	while k < length:
		if t[k] == 1:
			a = k
			while k <= length - 1 and t[k] != 0:
				k = k + 1
			b = k - 1
			pankti1 = b - a + 1
			d.append(pankti1)
			e.append([a, b])
		k = k + 1
if i != 0 and j != length - 1:
	e.append([j + 1, i - 1])
	pankti = length - j + i
	d.append(pankti - 1)
	a = -14848465879
	b = -11545121488
	k = i
	while k < j + 1:
		if t[k] == 1:
			a = k
			while k <= length - 1 and t[k] != 0:
				k = k + 1
			b = k - 1
			pankti2 = b - a + 1
			e.append([a, b])
			d.append(pankti2)
		k = k + 1
u = -150
v = -150
a = -150
b = -150
for f in range(length):
	if t[f] == 0:
		tp = tp + 1
if len(d) != 0:
	maxcurrent = max(d)
	z1 = d.index(maxcurrent)
	goovadd = e.pop(z1)
	goov = d.pop(z1)
	(a, b) = goovadd
for f in range(length // 10000):
	tp5 = 0
	if t[f] == 0:
		tp5 = tp5 + 1
if len(d) != 0:
	maxcurrent = max(d)
	z2 = d.index(maxcurrent)
	good2add = e.pop(z2)
	good2 = d.pop(z2)
	(u, v) = good2add
for i in range(len(inputstr)):
	currentans1 = 0
	currentans2 = 0
	currentans3 = 0
	if inputstr[i] == '!':
		u5 = (u + 1) % n
		v5 = (v + 1) % n
		a5 = (a + 1) % n
		b5 = (b + 1) % n
		if u != -150 and v != -150:
			u = u5
			v = v5
		if a != -150 and b != -150:
			a = a5
			b = b5
		for f in range(length // 961):
			if t[f] == 1:
				tp150 = tp150 + 1
	elif inputstr[i] == '?':
		if b - a >= 0 and a != -150 and (b != -150):
			currentans2 = b - a + 1
			if u != -150:
				if v != -150:
					if v - u >= 0:
						currentans3 = v - u + 1
					else:
						currentans1 = v + 1
						currentans3 = length - u
		if b - a < 0:
			currentans1 = b + 1
			currentans2 = length - a
			if u != -150:
				if v != -150:
					currentans3 = v - u + 1
		if ctr == length:
			currentans1 = length
		prefinalans = max(currentans1, currentans2)
		prefinalans = max(prefinalans, currentans3)
		for f in range(length // 509):
			if t[f] == 0:
				tp6 = tp6 + 1
		if prefinalans <= kinput:
			print(prefinalans)
		else:
			print(kinput)
z = []
for i in range(n // 74787):
	z.append(n * i)
waste = []
for i in range(n // 46987):
	waste.append(q * (2 * i))


(n, q, k) = map(int, input().split())
arr = list(map(int, input().split()))
string = input()
dictionary = {}
dictionary[n] = 0
count = 0
max_count = 0
for var in range(n):
	dictionary[var] = 0
	if arr[var] == 1:
		count += 1
	else:
		if count != 0:
			arr[var - count] = count
			arr[var - 1] = count
			if count not in dictionary:
				dictionary[count] = 1
			else:
				dictionary[count] += 1
			max_count = max(max_count, count)
		count = 0
if count != 0:
	arr[-count] = count
	arr[-1] = count
	dictionary[count] = dictionary[count] + 1
	max_count = max(max_count, count)
temp = 0
right = -1
left = 0
another_dict = {}
while left != -1 * n + 1:
	another_dict[temp] = min(max_count, k)
	temp += 1
	right -= 1
	left -= 1
	if arr[right + 1] >= 1:
		arr[right] = arr[right + 1] - 1
		dictionary[arr[right + 1]] -= 1
		if dictionary[max_count] == 0:
			max_count -= 1
		arr[(right - arr[right] + 1) % n] = arr[right]
		dictionary[arr[right]] += 1
		if arr[left + 1]:
			arr[left] = arr[left + 1] + 1
			dictionary[arr[left + 1]] -= 1
			arr[left + arr[left] - 1] = arr[left]
			dictionary[arr[left]] = dictionary[arr[left]] + 1
			max_count = max(max_count, arr[left])
		else:
			dictionary[1] += 1
			arr[left] = 1
count = 0
another_dict[n - 1] = min(max_count, k)
for i in range(len(string)):
	if string[i] == '!':
		count = (count + 1) % n
	else:
		print(another_dict[count])


import math
inp = input().split(' ')
n = int(inp[0])
q = int(inp[1])
lim = int(inp[2])
by = input().split(' ')
binary = [int(x) for x in by]
k = 0
left = 0
right = 0
maxm = 0
start = -1
minm = 0
minstart = -1
count = 0
cycle = 0
if binary[0] != 0 and binary[-1] != 0:
	cycle = 1
for i in range(n):
	if binary[i] == 0:
		if count > maxm:
			maxm = count
			start = i - count
		count = 0
	else:
		count += 1
if i == n - 1:
	if count > maxm:
		maxm = count
		start = i - count + 1
	count = 0
if start == 0:
	count = 0
	for i in range(start + maxm, n):
		if binary[i] == 0:
			if count > minm:
				minm = count
				minstart = i - count
			count = 0
		else:
			count += 1
elif start == n - maxm:
	count = 0
	for i in range(0, start):
		if binary[i] == 0:
			if count > minm:
				minm = count
				minstart = i - count
			count = 0
		else:
			count += 1
else:
	count = 0
	for i in range(0, start):
		if binary[i] == 0:
			if count > minm:
				minm = count
				minstart = i - count
			count = 0
		else:
			count += 1
	count = 0
	for i in range(start + maxm, n):
		if binary[i] == 0:
			if count > minm:
				minm = count
				minstart = i - count
			count = 0
		else:
			count += 1
right = start + maxm - 1
all1 = 0
if cycle:
	k = 0
	c = 0
	while binary[k] == 1:
		if k == n - 1:
			all1 = 1
			break
		c += 1
		k += 1
	right = k - 1
	if all1:
		maxm = n
		start = 0
		right = n - 1
	else:
		x = n - 1
		co = 0
		while binary[x] == 1:
			co += 1
			x -= 1
		if c + co > maxm:
			start = x + 1
			maxm = c + co
		r = 0
		if start == x + 1:
			for i in range(k, x + 1):
				if binary[i] == 0:
					if r > minm:
						minm = r
						minstart = i - r
					r = 0
				else:
					r += 1
		elif c + co > minm:
			minm = c + co
			minstart = x + 1
if math.ceil(maxm / 2) > minm:
	minm = math.ceil(maxm / 2)
left = start
query = input()
for i in range(q):
	if query[i] == '!':
		left = (left + 1) % n
		right = (right + 1) % n
	elif query[i] == '?':
		if all1:
			ans = min(lim, n)
		else:
			ans = 0
			if left + maxm <= n:
				ans = min(lim, maxm)
			else:
				temp1 = left + maxm - n
				temp2 = n - left
				temp3 = max(temp1, temp2)
				temp4 = max(minm, temp3)
				ans = min(lim, temp4)
		print(ans)


(length, queries, minimum) = map(int, input().split())
array = list(map(int, input().split()))
string = input()
pref = []
i = 0
while i < len(array):
	if array[i] == 0:
		pref.append(0)
		i += 1
	elif array[i] == 1:
		count = 0
		while i < len(array) and array[i] == 1:
			count += 1
			i += 1
		pref.append(count)
answer = [0] * length
frequency = [0] * (length + length)
for i in range(len(pref)):
	if pref[i] != 0:
		frequency[pref[i]] += 1
answer[0] = max(pref)
maximum = max(pref)
length2 = len(pref)
for i in range(1, length):
	if pref[length2 - 1] == 0:
		pref.pop(length2 - 1)
		pref.insert(0, 0)
		answer[i] = maximum
	elif pref[length2 - 1] > 0:
		if pref[length2 - 1] > 1:
			if pref[0] == 0:
				x = pref[length2 - 1]
				frequency[x] -= 1
				frequency[x - 1] += 1
				frequency[1] += 1
				pref[length2 - 1] -= 1
				length2 += 1
				pref.insert(0, 1)
			elif pref[0] > 0:
				x = pref[length2 - 1]
				y = pref[0]
				frequency[x] -= 1
				frequency[y] -= 1
				frequency[x - 1] += 1
				frequency[y + 1] += 1
				pref[length2 - 1] -= 1
				pref[0] += 1
		elif pref[length2 - 1] == 1:
			if pref[0] == 0:
				pref.pop()
				pref.insert(0, 1)
			elif pref[0] > 0:
				x = pref[0]
				frequency[x] -= 1
				frequency[x + 1] += 1
				frequency[1] -= 1
				pref.pop()
				pref[0] += 1
				length2 -= 1
		if frequency[maximum + 1] > 0:
			maximum = maximum + 1
		elif frequency[maximum] > 0:
			maximum = maximum
		elif frequency[maximum - 1] > 0:
			maximum = maximum - 1
		answer[i] = maximum
conti = 0
if len(pref) == 1:
	for i in range(queries):
		if string[i] == '?':
			print(min(minimum, pref[0]))
else:
	for i in range(queries):
		if string[i] == '!':
			conti += 1
		elif string[i] == '?':
			print(min(minimum, answer[conti % length]))


(n, q, k1) = map(int, input().split())
l = list(map(int, input().split()))
s = input()
if n == 1:
	for i in s:
		if i == '?':
			if l[0] == 1:
				print(1)
			else:
				print(0)
elif n == 2:
	c = 0
	for i in range(n):
		if l[i] == 1:
			c += 1
	if c == 2:
		for i in s:
			if i == '?':
				if c <= k1:
					print(c)
				else:
					print(k1)
	if c == 0:
		for i in s:
			if i == '?':
				print(0)
	if c == 1:
		for i in s:
			if i == '!':
				(l[0], l[1]) = (l[1], [0])
			else:
				print(1)
else:
	beg = [0, [0, 0]]
	c = 0
	start = -1
	for i in range(len(l)):
		if l[i] == 1:
			c += 1
			if start == -1:
				start = i
		else:
			if c != 0:
				end = i
				beg = [c, [start, end - 1]]
			break
	if c != 0 and beg[0] == 0:
		beg = [c, [0, len(l) - 1]]
	j = i + 1
	if j < len(l):
		x = []
		c = 0
		(start, end) = (0, 0)
		for i in range(j, len(l)):
			if l[i] == 1:
				c += 1
				if start == 0:
					start = i
			else:
				if c != 0:
					end = i
					x.append([c, [start, end - 1]])
					(start, end) = (0, 0)
				c = 0
		if c != 0:
			x.append([c, [start, len(l) - 1]])
		l_x = len(x)
		if beg == 0 and l_x == 0:
			for i in s:
				if i == '?':
					print(0)
		if l_x == 0:
			(mx1, mx2) = ([0, [0, 0]], [0, [0, 0]])
		elif l_x == 1:
			mx1 = x[0]
			mx2 = [0, [0, 0]]
		elif l_x >= 2:
			x = sorted(x, reverse=True)
			mx1 = x[0]
			mx2 = x[1]
		j1 = n - 1
		k = n - 1
		for i in s:
			if i == '!':
				if l[k] == 0 and l[(k + 1) % n] == 0:
					mx1[1][0] += 1
					mx1[1][1] += 1
					mx2[1][0] += 1
					mx2[1][1] += 1
				elif l[k] == 0 and l[(k + 1) % n] == 1:
					if beg[0] > mx1[0]:
						if mx1[0] > mx2[0]:
							mx2 = mx1
							mx1 = beg
							beg = [0, [0, 0]]
						else:
							mx1 = beg
							beg = [0, [0, 0]]
					elif beg[0] > mx2[0]:
						mx2 = beg
						beg = [0, [0, 0]]
					else:
						beg = [0, [0, 0]]
					mx1[1][0] += 1
					mx1[1][1] += 1
					mx2[1][0] += 1
					mx2[1][1] += 1
				elif l[k] == 1 and l[(k + 1) % n] == 0:
					beg = [1, [0, 0]]
					if j1 >= mx1[1][0] and j1 <= mx1[1][1]:
						mx1[0] -= 1
						if mx1[0] == 0:
							mx1[1][0] = 0
							mx1[1][1] = 0
						else:
							mx1[1][0] += 1
						mx2[1][0] += 1
						mx2[1][1] += 1
					elif j1 >= mx2[1][0] and j1 <= mx2[1][1]:
						mx2[0] -= 1
						if mx2[0] == 0:
							mx2[1][0] = 0
							mx2[1][1] = 0
						else:
							mx2[1][0] += 1
						mx1[1][0] += 1
						mx1[1][1] += 1
					else:
						mx1[1][0] += 1
						mx1[1][1] += 1
						mx2[1][0] += 1
						mx2[1][1] += 1
				elif l[k] == 1 and l[(k + 1) % n] == 1:
					beg[0] += 1
					beg[1][1] += 1
					if j1 >= mx1[1][0] and j1 <= mx1[1][1]:
						mx1[0] -= 1
						if mx1[0] == 0:
							mx1[1][0] = 0
							mx1[1][1] = 0
						else:
							mx1[1][0] += 1
						mx2[1][0] += 1
						mx2[1][1] += 1
					elif j1 >= mx2[1][0] and j1 <= mx2[1][1]:
						mx2[0] -= 1
						if mx2[0] == 0:
							mx2[1][0] = 0
							mx2[1][1] = 0
						else:
							mx2[1][0] += 1
						mx1[1][0] += 1
						mx1[1][1] += 1
					else:
						mx1[1][0] += 1
						mx1[1][1] += 1
						mx2[1][0] += 1
						mx2[1][1] += 1
				k -= 1
				if k < 0:
					k = n - 1
			else:
				M = max(beg[0], mx1[0], mx2[0])
				if M <= k1:
					print(M)
				else:
					print(k1)
	elif beg[0] == n:
		for i in s:
			if i == '?':
				if beg[0] <= k1:
					print(beg[0])
				else:
					print(k1)
	else:
		j1 = n - 1
		beg = beg[0]
		beg1 = beg
		for i in s:
			if i == '!':
				if l[j1] == 1 and l[(j1 + 1) % n] == 0:
					beg = 1
					beg1 -= 1
					j1 -= 1
				elif l[j1] == 1 and l[(j1 + 1) % n] == 1:
					beg += 1
					beg1 -= 1
					j1 -= 1
				elif l[j1] == 0 and l[(j1 + 1) % n] == 1:
					beg = 0
					j1 -= 1
				else:
					j1 -= 1
				if j1 < 0:
					j1 = n - 1
			elif max(beg, beg1) <= k1:
				print(max(beg, beg1))
			else:
				print(k1)


def create(current, ss, se):
	if ss == se:
		if array[ss] == 1:
			value = 1
		else:
			value = 0
		tree[current] = [value, value, 1 - value, value]
	else:
		mid = (ss + se) // 2
		left = 2 * current + 1
		right = 2 * current + 2
		create(left, ss, mid)
		create(right, mid + 1, se)
		if tree[left][2] == 0:
			tree[current][0] = tree[left][0] + tree[right][0]
		else:
			tree[current][0] = tree[left][0]
		if tree[right][2] == 0:
			tree[current][1] = tree[left][1] + tree[right][1]
		else:
			tree[current][1] = tree[right][1]
		tree[current][2] = tree[left][2] + tree[right][2]
		tree[current][3] = max(tree[left][3], tree[right][3], tree[left][1] + tree[right][0])

def query(current, ss, se, l, r):
	if ss > r or se < l:
		return None
	if ss >= l and se <= r:
		return tree[current]
	mid = (ss + se) // 2
	left_q = query(2 * current + 1, ss, mid, l, r)
	right_q = query(2 * current + 2, mid + 1, se, l, r)
	if left_q == None:
		return right_q
	if right_q == None:
		return left_q
	ans = [0, 0, 0, 0]
	if left_q[2] == 0:
		ans[0] = left_q[0] + right_q[0]
	else:
		ans[0] = left_q[0]
	if right_q[2] == 0:
		ans[1] = left_q[1] + right_q[1]
	else:
		ans[1] = right_q[1]
	ans[2] = left_q[2] + right_q[2]
	ans[3] = max(left_q[3], right_q[3], left_q[1] + right_q[0])
	return ans
(n, q, k) = map(int, input().split())
array = list(map(int, input().split()))
array += array
s = input()
tree = [[0, 0, 0, 0] for i in range(8 * n)]
create(0, 0, 2 * n - 1)
i = 0
for ch in s:
	if ch == '?':
		i = i % n
		ans = query(0, 0, 2 * n - 1, n - i, 2 * n - 1 - i)
		print(min(k, ans[3]))
	else:
		i += 1


(n, q, k) = map(int, input().split())
l = list(map(str, input().split()))
s = input()
for x in s:
	if x == '!':
		temp = l[-1]
		l[1:] = l[:-1]
		l[0] = temp
		continue
	elif x == '?':
		s_new = ''.join(l[:])
		l_new = s_new.split('0')
		l_new.sort()
		if len(l_new[-1]) >= k:
			print(k)
		else:
			print(len(l_new[-1]))


(n, q, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
l = len(a)
s = input()
if n <= 1000 and q <= 3000:
	for x in s:
		if x == '!':
			b = a.pop(l - 1)
			a = [b] + a
		else:
			f = 0
			z = 0
			a = a + [0]
			for x in a:
				if x == 1:
					f += 1
				else:
					if f >= k:
						z = k
						break
					if f > z:
						z = f
					f = 0
			print(z)
			a.pop(l)
else:
	f = 0
	z = 0
	ub = 0
	u = 0
	a = a + [0]
	for x in range(len(a)):
		if a[x] == 1:
			f += 1
		else:
			if f > z:
				z = f
				ub = x - 1
			f = 0
	f = 0
	q1 = 0
	z1 = 0
	for x in range(len(a)):
		if a[x] == 1:
			f += 1
		else:
			if f > q1 and f < z:
				z1 = f
				q1 = f
			f = 0
	a.pop(l)
	lb = ub + 1 - z
	if z1 == 0:
		a1 = a.count(1)
		if a1 > z:
			z1 = z
	if z == l:
		for x in s:
			if x == '?':
				print(min(k, z))
	elif z == 0:
		for x in s:
			if x == '?':
				print(0)
	elif z == 1:
		for x in s:
			if x == '?':
				print(1)
	else:
		q1 = 0
		q2 = l - 1
		f1 = 0
		f2 = 0
		secl = z1
		if a[0] == 1 and a[l - 1] == 1:
			while a[q1] != 0:
				f1 += 1
				q1 += 1
			while a[q2] != 0:
				f2 += 1
				q2 -= 1
			if f1 + f2 > z:
				ub = f1 - 1
				lb = l - f2
				o = 0
				z2 = 0
				for t in range(ub + 1, lb):
					if a[t] == 1:
						o += 1
					elif o > z2:
						z2 = o
				secl = z2
				z = f1 + f2
			elif f1 + f2 == z:
				secl = z
			elif f1 + f2 > z1:
				secl = f1 + f2
			else:
				secl = z1
		for x in s:
			if x == '!':
				ub += 1
				lb += 1
				if ub > l - 1:
					ub = 0
				if lb > l - 1:
					lb = 0
			elif lb > ub:
				w1 = max(ub + 1, l - lb)
				w2 = max(w1, secl)
				if w2 > k:
					print(k)
				else:
					print(w2)
			else:
				w1 = min(ub - lb + 1, k)
				print(w1)


(N, Q, K) = map(int, input().split())
data = [0] * (2 * N)
(count1, count0) = (0, 0)
p = [int(x) for x in input().split()]
for i in range(N):
	data[i] = p[i]
	data[i + N] = p[i]
	if p[i] == 1:
		count1 += 1
	else:
		count0 += 1
largest = 0
(l, r, count, templ, tempr) = (-1, -1, 0, 0, -1)
for i in range(2 * N):
	if data[i] == 1:
		count += 1
		tempr += 1
	else:
		if count > largest:
			largest = count
			l = templ
			r = tempr
		templ = i + 1
		tempr = i
		count = 0
(l2, r2) = (0, 0)
if 0 <= l and r <= N - 1:
	l2 = N + 1
	r2 = N + r
else:
	l2 = l
	r2 = r
(secondlargest, count) = (-1, 0)
for i in range(N):
	if not (l <= i and i <= r or i <= r - N):
		if data[i] == 1:
			count += 1
		else:
			if count > secondlargest:
				secondlargest = count
			count = 0
rotate = [0] * N
if count1 == N:
	for i in range(N):
		rotate[i] = N
elif count0 == N:
	for i in range(N):
		rotate[i] = 0
else:
	for i in range(N - 1, -1, -1):
		(low, up) = (i + 1, i + N)
		if low <= l and r <= up or (low <= l2 and r2 <= up):
			rotate[N - 1 - i] = largest
		else:
			c = secondlargest
			if l <= low and low <= r:
				a = low - l
				b = largest - a
			else:
				a = up - l2 + 1
				b = largest - a
			rotate[N - 1 - i] = (a if a > c else c) if a > b else b if b > c else c
query = input()
rot = 0
for i in range(Q):
	if query[i] == '?':
		print(rotate[rot] if rotate[rot] <= K else K)
	else:
		rot = (rot + 1) % N


(n, q, k) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
c = list(input())
le = c.count('?')
if len(set(arr)) == 1 and arr[0] == 1:
	if k >= n:
		for i in range(le):
			print(n)
	else:
		for i in range(le):
			print(k)
elif len(set(arr)) == 1 and arr[0] == 0:
	for i in range(le):
		print(0)
else:
	a = [0] * (2 * n)
	for i in range(n):
		a[i] = arr[i]
		a[i + n] = arr[i]
	sol = [0] * n
	shifts = 0
	m = 0
	arrStart = n
	arrEnd = 2 * n - 1
	maxStart = -1
	maxEnd = -1
	prevStart = -1
	prevEnd = -1
	tempStart = -1
	tempEnd = -1
	flag = 1
	for i in range(2 * n - 1, n - 1, -1):
		if a[i] == 1:
			if flag:
				tempEnd = i
			tempStart = i
			flag = 0
		else:
			if flag:
				continue
			if tempEnd - tempStart + 1 >= m:
				m = tempEnd - tempStart + 1
				maxStart = tempStart
				maxEnd = tempEnd
			elif prevEnd - prevStart + 1 >= tempEnd - tempStart + 1:
				prevStart = tempStart
				prevEnd = tempEnd
			flag = 1
	if flag == 0 and tempEnd - tempStart + 1 >= m:
		m = tempEnd - tempStart + 1
		maxStart = tempStart
		maxEnd = tempEnd
	if m < k:
		sol[shifts] = m
	else:
		sol[shifts] = k
	shifts += 1
	arrStart = n - 1
	while arrStart > 0:
		arrEnd = arrStart + n - 1
		if maxEnd == arrEnd + 1:
			m -= 1
			maxEnd -= 1
			if prevEnd - prevStart + 1 >= m:
				maxStart = prevStart
				maxEnd = prevEnd
				m = prevEnd - prevStart + 1
		if a[arrStart] == 1:
			if flag:
				tempEnd = arrStart
			tempStart = arrStart
			flag = 0
		else:
			flag = 1
		if tempEnd - tempStart + 1 >= m:
			m = tempEnd - tempStart + 1
			maxStart = tempStart
			maxEnd = tempEnd
		elif prevEnd - prevStart + 1 <= tempEnd - tempStart + 1:
			prevStart = tempStart
			prevEnd = tempEnd
		if m < k:
			sol[shifts] = m
		else:
			sol[shifts] = k
		arrStart -= 1
		shifts += 1
	reqShift = 0
	for i in range(q):
		if c[i] == '?':
			print(sol[reqShift])
		else:
			reqShift += 1
		if reqShift == n:
			reqShift = 0


def appyLoveOne(A, S, K, N):
	(max_, max2, smax, emax) = givemax1andmax2(A)
	start = 0
	end = len(A) - 1
	fstpass = True
	for i in S:
		if i == '!':
			fstpass = False
			start = end
			end = (end - 1 + len(A)) % len(A)
		else:
			if smax <= emax and start >= smax and (start <= emax):
				localmax = max(emax - start + 1, start - smax, max2)
			elif smax > emax and (start <= emax or start >= smax):
				if start <= emax:
					localmax = max(emax - start + 1, len(A) - smax + start, max2)
				elif start >= smax:
					localmax = max(start - smax, emax - 0 + 1 + (len(A) - start), max2)
			else:
				localmax = max_
			if localmax > K:
				print(K)
			else:
				print(localmax)

def givemax1andmax2(A):
	start = 0
	end = len(A) - 1
	N = len(A)
	count = 0
	max_ = 0
	(smax, st) = (-1, 0)
	(emax, et) = (-1, 0)
	for j in range(2 * N):
		index = (start + j) % N
		if A[index] == 1:
			count += 1
			et = index
		else:
			count = 0
			st = index + 1
		if max_ < count:
			max_ = count
			smax = st
			emax = et
	if emax <= smax:
		(first, last) = (smax, (emax + 1) % N)
	else:
		B = A[0:smax] + A[emax + 1:]
		(first, last) = (smax, emax)
	count = 0
	max2_ = 0
	(sma, st) = (-1, 0)
	(ema, et) = (-1, 0)
	(first, last) = (smax, (emax + 1) % N)
	if emax <= smax:
		for j in range(2 * N):
			index = (start + j) % N
			if index >= last and index < first:
				pass
			else:
				continue
			if A[index] == 1:
				count += 1
				et = index
			else:
				count = 0
				st = index + 1
			if max2_ < count:
				max2_ = count
				sma = st
				ema = et
	else:
		for j in range(2 * N):
			index = (start + j) % N
			if index >= smax and index <= emax:
				continue
			if A[index] == 1:
				count += 1
				et = index
			else:
				count = 0
				st = index + 1
			if max2_ < count:
				max2_ = count
				sma = st
				ema = et
	if max_ > len(A):
		max_ = max_ // 2
	return (max_, max2_, smax, emax)
(N, Q, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
S = input()
appyLoveOne(A, S, K, N)


def parseQueries(queries, q):
	move1 = []
	move2 = []
	prev = ''
	count = 1
	if queries[0] == '!':
		prev = '!'
	else:
		move1 = [0]
	for i in range(1, q):
		el = queries[i]
		if el == prev:
			count += 1
		else:
			if prev == '!':
				move1.append(count)
			else:
				move2.append(count)
			count = 1
			prev = el
	if prev == '!':
		move1.append(count)
	else:
		move2.append(count)
	return (move1, move2)

def getMax2(max2, endex2, start, end):
	if max2 > start + end:
		return [max2, endex2]
	else:
		return [start + end, start]

def updateTrack(track, shift, n):
	track[0][1] = (track[0][1] + shift) % n
	track[1][1] = (track[1][1] + shift) % n
	return track

def getResult(track, k):
	e1 = track[0]
	max1 = max(min(e1[0], e1[1]), e1[0] - e1[1])
	e2 = track[1]
	max2 = max(min(e2[0], e2[1]), e2[0] - e2[1])
	return min(k, max(max1, max2))
(n, q, k) = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))
queries = input()
(move1, move2) = parseQueries(queries, q)
countStart = True
start = 0
end = 0
temp = 0
max1 = 0
endex1 = 0
max2 = 0
endex2 = 0
for i in range(n):
	e = arr[i]
	if e == 1:
		if countStart:
			start += 1
		end += 1
		temp += 1
	else:
		if countStart:
			countStart = False
		elif temp >= max1:
			max2 = max1
			endex2 = endex1
			endex1 = i
			max1 = temp
		elif temp > max2:
			max2 = temp
			endex2 = i
		end = 0
		temp = 0
track = [[max1, endex1], getMax2(max2, endex2, start, end)]
query = False
i = 0
while True:
	try:
		if query:
			query = False
			result = getResult(track, k)
			for j in range(0, move2[i]):
				print(result)
			i += 1
		else:
			query = True
			updateTrack(track, move1[i], n)
	except IndexError:
		break


nqklist = list(map(int, input().split()))
nlist = list(map(int, input().split()))
n = nqklist[0]
q = nqklist[1]
k = nqklist[2]
dp = [0] * (n + 1)
qstr = input()
i = 0
fm = 0
fmi = -1
fmf = -1
sm = 0
smi = -1
for a in nlist:
	if a == 0 or i == 0:
		dp[i] = a
	else:
		dp[i] = dp[i - 1] + a
	i = i + 1
i = 0
if dp[n - 1] != n:
	for b in nlist:
		if b == 1:
			dp[i] = dp[i] + dp[n - 1]
		else:
			break
		i = i + 1
i = 0
for d in dp:
	if dp[i + 1] == 0:
		if fm < d:
			if i == n - 1 and dp[0] > dp[n - 1]:
				break
			sm = fm
			smi = fmi
			fm = d
			fmi = i
			fmf = (i - d + 1 + n) % n
		elif sm < d:
			sm = d
			smi = i
	i = i + 1
	if i == n - 1:
		break
if fmi == -1 and dp[n - 1] != 0:
	fm = dp[n - 1]
	fmi = n - 1
	fmf = n - dp[n - 1]
nindex = n - 1
for qr in qstr:
	if qr == '!':
		nindex = (nindex - 1 + n) % n
	elif fmi != -1:
		if fmf > fmi:
			if nindex < fmf and nindex >= fmi:
				print(min(fm, k))
			elif nindex < fmi:
				r = n - fmf + nindex + 1
				l = fm - r
				print(min(k, max(l, r, sm)))
			elif nindex >= fmf:
				r = nindex - fmf + 1
				l = fm - r
				print(min(k, max(l, r, sm)))
			else:
				r = n - fmf
				l = fm - r
				print(min(k, max(l, r, sm)))
		elif nindex < fmf or nindex >= fmi or dp[n - 1] == n:
			print(min(fm, k))
		else:
			r = fmi - nindex
			l = fm - r
			print(min(k, max(l, r, sm)))
	else:
		print(0)


from collections import Counter, deque
(N, Q, K) = map(int, input().split())
A = list(map(int, input().split()))
S = input()
(a, c, m) = (deque(), 0, 0)
m_count = Counter()
for i in range(N):
	if A[i]:
		c += 1
	else:
		if c:
			a.append(c)
			m = max(m, c)
			m_count[c] += 1
		c = 0
		a.append(0)
	if i == N - 1:
		if c:
			a.append(c)
			m = max(m, c)
			m_count[c] += 1
for i in range(Q):
	if S[i] == '?':
		print(min(m, K))
	elif a[-1]:
		if a[-1] == m and m_count[a[-1]] == 1:
			m -= 1
		m_count[a[-1]] -= 1
		a[-1] -= 1
		m_count[a[-1]] += 1
		if not a[-1]:
			a.pop()
		if not a[0]:
			a.appendleft(0)
		m_count[a[0]] -= 1
		a[0] += 1
		m_count[a[0]] += 1
		if a[0] > m:
			m += 1
	else:
		a.pop()
		a.appendleft(0)


class Group:

	def __init__(self, num, count):
		self.num = num
		self.count = count
(n, q, k) = map(int, input().split())
l = list(map(int, input().split()))
query = input()
groups = []
gIndex = None
i = 0
while i < n:
	count = 1
	while i < n - 1 and l[i] == l[i + 1]:
		count += 1
		i += 1
	g = Group(l[i], count)
	if l[i] == 1 and (gIndex == None or count > groups[gIndex].count):
		gIndex = len(groups)
	groups.append(g)
	i += 1

def rotate(groups, gIndex, k):
	groups[-1].count -= 1
	lastGroupNum = groups[-1].num
	if lastGroupNum == groups[0].num:
		groups[0].count += 1
	else:
		g = Group(lastGroupNum, 1)
		groups.insert(0, g)
		gIndex += 1
		gIndex %= len(groups)
	if gIndex == len(groups) - 1:
		gIndex = None
		for _ in range(0, len(groups)):
			if groups[_].num == 1 and (gIndex == None or groups[gIndex].count < groups[_].count):
				gIndex = _
	if groups[-1].count == 0:
		del groups[-1]
	if groups[0].num and min(k, groups[gIndex].count) <= min(k, groups[0].count):
		gIndex = 0
	if groups[-1].num and min(k, groups[gIndex].count) < min(k, groups[-1].count):
		gIndex = len(groups) - 1
	return (groups, gIndex)

def display(groups):
	for g in groups:
		print(str(g.num) + '=>' + str(g.count), end=',')
	print()

def answer(groups, gIndex, k):
	if gIndex is not None and len(groups) > gIndex:
		print(min(groups[gIndex].count, k))
	else:
		print(0)
for q in query:
	if q == '!':
		(groups, gIndex) = rotate(groups, gIndex, k)
	else:
		answer(groups, gIndex, k)


(n, q, k) = [int(x) for x in input().split()]
s = [int(x) for x in input().split()]
(b, t, l, r, p) = ([], 0, 0, 0, s[0])
if s[0] == 1:
	t = 1
for i in range(1, n):
	if s[i] == 1 and s[i] == p:
		t += 1
		r += 1
	else:
		if t > 0:
			b.append([t, l, r])
		if s[i] == 1:
			(t, l, r) = (1, i, i)
		else:
			t = 0
	p = s[i]
if t > 0:
	b.append([t, l, r])
if s[0] == s[n - 1] and s[0] == 1:
	b[0][0] += b[len(b) - 1][0]
	b[0][1] = b[len(b) - 1][1]
	if len(b) > 1:
		b.pop()
b.sort(reverse=True)
q = input()
for i in q:
	if i == '!' and len(b) > 0:
		b[0][1] = (b[0][1] + 1) % n
		b[0][2] = (b[0][2] + 1) % n
	elif i == '?':
		if len(b) > 0:
			if b[0][2] < b[0][1]:
				if len(b) > 1:
					print(min(k, max(b[1][0], n - b[0][1], b[0][2] + 1)))
				else:
					print(min(k, max(n - b[0][1], b[0][2] + 1)))
			else:
				print(min(k, b[0][0]))
		else:
			print(0)


(N, Q, K) = map(int, input().split())
A = input().split()
S = input()
c = 0
mx = [0, 0]
T = []
values = {}
for i in A:
	if i == '1':
		c += 1
		if c >= mx[0]:
			mx[0] = c
			mx[1] += 1
	else:
		if c != 0:
			T.append(c)
			if c in values:
				values[c] += 1
			else:
				values[c] = 1
		T.append(0)
		c = 0
		mx[1] = 0
if A[-1] != '0':
	T.append(c)
	if c in values:
		values[c] += 1
	else:
		values[c] = 1
T.reverse()
c = 0
for i in S:
	if i == '?':
		print(mx[0] if mx[0] <= K else K)
	elif T[c] != 0:
		if T[-1] != 0:
			values[T[-1]] -= 1
			T[-1] += 1
			if T[-1] not in values:
				values[T[-1]] = 1
			else:
				values[T[-1]] += 1
			mx[0] = max(mx[0], T[-1])
		else:
			T.append(1)
			if 1 in values:
				values[1] += 1
			else:
				values[1] = 1
		if T[c] - 1:
			if T[c] == mx[0]:
				if values[T[c]]:
					values[T[c]] -= 1
					if values[T[c]] == 0:
						mx[0] -= 1
				T[c] -= 1
				if T[c] not in values:
					values[T[c]] = 1
				else:
					values[T[c]] += 1
			else:
				values[T[c]] -= 1
				T[c] -= 1
				if T[c] not in values:
					values[T[c]] = 1
				else:
					values[T[c]] += 1
		else:
			values[T[c]] = 0
			c += 1
	else:
		T.append(0)
		c += 1


(n, q, k) = map(int, input().split())
intMax = 10 ** 10
a = 2 * list(map(int, input().split()))
for i in range(2 * n - 2, -1, -1):
	if a[i] == 1:
		a[i] += a[i + 1]
t = [-1 for i in range(8 * n + 2)]

def build(ss, se, nd):
	if ss == se:
		t[nd] = ss
		return
	mid = (ss + se) // 2
	build(ss, mid, 2 * nd)
	build(mid + 1, se, 2 * nd + 1)
	if a[t[2 * nd]] > a[t[2 * nd + 1]]:
		t[nd] = t[2 * nd]
	else:
		t[nd] = t[2 * nd + 1]
	return

def query(fs, fe, ss, se, nd):
	if fs <= ss and fe >= se:
		return t[nd]
	elif se < fs or ss > fe:
		return -50
	else:
		mid = (ss + se) // 2
		p = query(fs, fe, ss, mid, 2 * nd)
		q = query(fs, fe, mid + 1, se, 2 * nd + 1)
		if p < 0:
			return q
		if q < 0:
			return p
		if a[p] > a[q]:
			return p
		else:
			return q
build(0, 2 * n - 1, 1)
queries = input()
p = n
for q in queries:
	if q == '?':
		indx = query(p, p + n - 1, 0, 2 * n - 1, 1)
		if indx + a[indx] - 1 > p + n - 1:
			pos1 = p + n - indx
		else:
			pos1 = a[indx]
		if indx == p:
			print(min(pos1, k))
		else:
			pos2 = a[query(p, indx - 1, 0, 2 * n - 1, 1)]
			print(min(max(pos1, pos2), k))
	else:
		p -= 1
		if p == 0:
			p = n


import collections
(n, q, k) = map(int, input().split())
a = list(map(int, input().split()))
st = str(input())
de = collections.deque(a)
for f in range(q):
	if st[f] == '!':
		de.rotate(1)
	else:
		mi = 0
		prev = 0
		cnt = 0
		while 1:
			i = prev
			if de[i] == 1:
				while de[i] == 1:
					cnt += 1
					i += 1
					if i > n - 1:
						break
			else:
				i += 1
			prev = i
			if cnt > mi:
				mi = cnt
			if prev >= n - 1:
				break
			cnt = 0
		if mi < k:
			print(mi)
		else:
			print(k)


def func1(arr, n, k):
	first = 0
	i = 0
	while i < n and arr[i]:
		i += 1
	first = i
	if first != len(arr):
		j = n - 1
		last = 0
		while j > -1 and arr[j]:
			last += 1
			j -= 1
	else:
		return (True, min(k, first), 0, 0)
	high = first + last
	secondH = 0
	while i < j:
		count = 0
		while i < j and arr[i]:
			count += 1
			i += 1
		if count > high:
			secondH = high
			high = count
		elif count == high:
			secondH = high
		elif count > secondH:
			secondH = count
		i += 1
	arr2 = arr * 2
	indexF = []
	indexF.append(first)
	for i in range(n - 1, 0, -1):
		if arr2[i]:
			indexF.append(indexF[n - 1 - i] + 1)
		else:
			indexF.append(0)
	lastF = 0
	j = n
	while j > 0 and arr2[j]:
		lastF += 1
		j -= 1
	indexL = []
	indexL.append(lastF)
	for j in range(n + 1, 2 * n):
		if arr2[j]:
			indexL.append(indexL[j - (n + 1)] + 1)
		else:
			indexL.append(0)
	indexL.reverse()
	return (indexF, indexL, high, secondH)

def ans(arr, n, k, q, query):
	(a, b, high, secondH) = func1(arr, n, k)
	if a == True:
		for i in range(0, q):
			if query[i] == '?':
				print(b)
	else:
		j = 0
		for i in range(0, q):
			if query[i] == '?':
				if k <= secondH:
					print(k)
				elif a[j % n] + b[j % n] == high:
					val = max(a[j % n], b[j % n])
					val = max(val, secondH)
					print(min(val, k))
				else:
					print(min(high, k))
			else:
				j += 1

def func():
	inp = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	query = input()
	n = inp[0]
	q = inp[1]
	k = inp[2]
	ans(arr, n, k, q, query)
func()


import bisect
(n, q, k) = map(int, input().split())
Arr = [int(x) for x in input().split()]
qs = input()
ones = []
i = 0
while i < n:
	if Arr[i] == 1:
		j = i + 1
		while j < n and Arr[j] == 1:
			j += 1
		ones.append((i, j - i))
		i = j
	else:
		i += 1
(first, last) = (0, 0)
firstToStart = ones[0][0] == 0 if ones else False
lastToEnd = ones[-1][0] + ones[-1][1] >= n if ones else False
if firstToStart:
	first = ones[0][1]
if lastToEnd:
	last = ones[-1][1]
ol = len(ones)
(left, right) = ([0] * (ol + 1), [0] * (ol + 1))
mxone = 0
for i in range(1 if firstToStart else 0, ol):
	mxone = max(mxone, ones[i][1])
	left[i] = mxone
mxone = 0
for i in range(ol - 2 if lastToEnd else ol - 1, -1, -1):
	mxone = max(mxone, ones[i][1])
	right[i] = mxone
memo = {}

def query(start):
	if start in memo:
		return memo[start]
	res = 0
	i = bisect.bisect_right(ones, (start, float('inf')))
	l = 0
	if i > 0:
		if ones[i - 1][0] + ones[i - 1][1] <= start:
			l = left[i - 1]
		elif i - 2 >= 0:
			l = left[i - 2]
	r = right[i] if i < ol else 0
	res = max(l, r)
	if 0 < i < ol:
		(s, t) = ones[i - 1]
		if s + t > start:
			l = start - s
			r = t - l
			res = max(res, l, r)
	if firstToStart and lastToEnd:
		if ones[0][1] < ones[-1][0]:
			if ones[0][1] < start < ones[-1][0]:
				res = max(res, first + last)
			elif start <= ones[0][1]:
				res = max(res, start + last, ones[0][1] - start)
			else:
				l = start - ones[-1][0]
				res = max(res, l, first + last - l)
		else:
			res = ones[0][1]
	elif firstToStart:
		if start < ones[0][1]:
			res = max(res, start, ones[0][1] - start)
		else:
			res = max(res, ones[0][1])
	elif lastToEnd:
		if start >= ones[-1][0]:
			l = start - ones[-1][0]
			res = max(res, l, ones[-1][1] - l)
		else:
			res = max(res, ones[-1][1])
	res = min(res, k)
	memo[start] = res
	return res
start = 0
res = []
for Q in qs:
	if Q == '?':
		res.append(query(start))
	else:
		start = (start + n - 1) % n
print('\n'.join(map(str, res)))


(n, q, k1) = [int(i) for i in input().split()]
t = [int(i) for i in input().split()]
c1 = str(input())
d = []
e = []
i = 0
j = len(t) - 1
count = 0
for i1 in range(len(t)):
	if t[i1] == 1:
		count = count + 1
if len(t) >= 2 and count != len(t):
	while t[i] != 0:
		i = i + 1
	while t[j] != 0:
		j = j - 1
if i != 0 and j != len(t) - 1:
	d.append(len(t) - 1 - j + i)
	e.append([j + 1, i - 1])
	a = -1
	b = -1
	k = i
	while True:
		if t[k] == 1:
			a = k
			while k <= len(t) - 1 and t[k] != 0:
				k = k + 1
			b = k - 1
			d.append(b - a + 1)
			e.append([a, b])
		k = k + 1
		if k >= j + 1:
			break
if i == 0 or j == len(t) - 1:
	a = -1
	b = -1
	k = 0
	while True:
		if t[k] == 1:
			a = k
			while k <= len(t) - 1 and t[k] != 0:
				k = k + 1
			b = k - 1
			d.append(b - a + 1)
			e.append([a, b])
		k = k + 1
		if k >= len(t):
			break
c2 = -1
d1 = -1
a = -1
b = -1
if len(d) != 0:
	z1 = d.index(max(d))
	max1 = d.pop(z1)
	max1add = e.pop(z1)
	a = max1add[0]
	b = max1add[1]
if len(d) != 0:
	z2 = d.index(max(d))
	max2 = d.pop(z2)
	max2add = e.pop(z2)
	c2 = max2add[0]
	d1 = max2add[1]
for i in range(len(c1)):
	ans1 = 0
	ans2 = 0
	ans3 = 0
	anspre = 0
	if c1[i] == '?':
		if a == -1 and b == -1 and (c2 == -1) and (d1 == -1):
			ans1 = 0
			ans2 = 0
			ans3 = 0
		if b - a < 0:
			ans1 = b + 1
			ans2 = len(t) - a
			ans3 = 0
			if c2 != -1 and d1 != -1:
				ans3 = d1 - c2 + 1
		if b - a >= 0 and a != -1 and (b != -1):
			ans3 = b - a + 1
			if c2 != -1 and d1 != -1:
				if d1 - c2 < 0:
					ans1 = d1 + 1
					ans2 = len(t) - c2
				else:
					ans2 = d1 - c2 + 1
					ans1 = 0
		if count == len(t):
			ans1 = len(t)
			ans2 = len(t)
			ans3 = len(t)
		anspre = max(ans1, ans2, ans3)
		print(min(anspre, k1))
	else:
		if a != -1 and b != -1:
			a = (a + 1) % n
			b = (b + 1) % n
		if c2 != -1 and d1 != -1:
			c2 = (c2 + 1) % n
			d1 = (d1 + 1) % n


from collections import deque
(n, q, k) = map(int, input().split())
a = deque(map(int, input().split()))
s = list(input())
lengths = deque()
c = flag = 0
for x in range(n):
	if a[x] == 0:
		if c > 0:
			lengths.append(c)
		c = 0
		lengths.append(0)
	else:
		flag = 1
		c += 1
		if x == n - 1:
			lengths.append(c)
l = len(lengths)
if l == 1 or flag == 0:
	for i in s:
		if i == '?':
			print(lengths[0] if lengths[0] < k else k)
else:
	m = max(lengths)
	l_temp = [z for z in lengths]
	l_temp.remove(m)
	sm = max(l_temp)
	for i in s:
		if i == '!':
			if a[n - 1] == 1:
				if lengths[l - 1] == m:
					m -= 1
					if sm > m:
						m = sm
				elif lengths[0] + 1 == m:
					sm = m
				lengths[l - 1] -= 1
				if lengths[l - 1] == 0:
					lengths.pop()
					l -= 1
				if a[0] == 0:
					lengths.append(1)
					lengths.rotate()
					l += 1
				else:
					lengths[0] += 1
			else:
				lengths.rotate()
			a.rotate()
			if lengths[0] > m:
				m = lengths[0]
		if i == '?':
			if m >= k:
				print(k)
			else:
				print(m)


def maxi(A):
	(pad, i) = (0, len(A) - 1)
	if A[0] == 1 and A[-1] == 1:
		while i >= 0:
			if A[i] == 0:
				break
			i -= 1
		B = A[i + 1:]
		B.extend(A[:i])
		(A, pad) = (B, len(A) - i - 1)
	A.append(0)
	(index1, maxx, max1, max2, val) = (0, 0, 0, 0, 1)
	for j in range(len(A)):
		if A[j] == 1:
			maxx += 1
		elif A[j] == 0:
			if maxx > max1:
				max1 = maxx
				index1 = j - 1
			elif maxx <= max1 and maxx > max2:
				max2 = maxx
			maxx = 0
	return (index1 - pad, max1, max2)
(N, Q, K) = map(int, input().split())
string = [int(x) for x in input().split()]
string2 = list(string)
query = input()
(index1, max1, max2) = maxi(string2)
index1 += 1
for val in query:
	if val == '?':
		if index1 < max1:
			a = max(index1, max1 - index1, max2)
			if a > K:
				print(K)
			else:
				print(a)
		elif max1 > K:
			print(K)
		else:
			print(max1)
	elif val == '!':
		index1 += 1
		if index1 == len(string) + 1:
			index1 = 1


def queue(seq, counter, bcount, lcount, scount, n, f, latest, ln, ln2, cf):
	if n == size - 1:
		bcount = ref1
		lcount = ref2
		scount = ref3
		latest = 0
		ln = -2
		ln2 = -2
	if bcount == 0:
		bcount = ref1
	if lcount == 0:
		lcount = ref2
	if scount == 0:
		scount = ref3
	if seq[n] == 1 and n >= 0:
		counter += 1
		n -= 1
		if f == 1:
			bcount += 1
	elif seq[n] == 0 and n >= 0:
		if counter > latest:
			if cf == 0:
				latest = counter
				ln = ref1 - 1
				ln2 = -2
			elif cf == 1 and seq[size - 1] == seq[0] == 0:
				latest = counter
				ln = n + counter + 1
				ln2 = n + 1
			elif cf == 1 and seq[size - 1] == seq[0] == 1:
				latest = counter
				ln = ref1 - 1
				ln2 = -2
		counter = 0
		f = 0
		n -= 1
	if n < index1 and n >= index1 - ref2:
		lcount -= 1
	if n < index2 and n >= index2 - ref3:
		scount -= 1
	if n < lind:
		bcount -= 1
	if n < ln and n > ln2:
		latest -= 1
	if n < 0:
		n = size - 1
		cf = 1
	return [counter, bcount, lcount, scount, n, f, latest, ln, ln2, cf]
(n, q, k) = map(int, input().split())
a = list(map(int, input().split()))
ct1 = 0
d = []
b = []
flag = 0
f2 = 0
while ct1 < n and a[0] == 1 and (a[ct1] == 1):
	ct1 += 1
	flag = 1
ct = 0
lind = -1 + ct1
f = 1
for i in range(n - 1):
	if a[i] == 1 or a[i + 1]:
		flag = 1
	if a[i] == a[i + 1] and a[i] == 1:
		ct += 1
		flag = 1
		d.append(i)
		d.append(i + 1)
	else:
		b.append([ct, d])
		ct = 0
		d = []
	if a[i] == a[i + 1] and a[i] == 1 and (i + 1 == n - 1):
		b.append([ct, d])
b.sort(key=lambda x: x[0])
ct = max(b, key=lambda x: x[0])
b.sort(reverse=True, key=lambda x: x[0])
ct2 = 0
ct3 = 0
index1 = -2
index2 = -2
ln = -2
ln2 = -2
if len(b) > 0 and a.count(1) > 0 and (ct[0] > 0):
	i = 1
	ct2 = ct[0] + 1
	index1 = max(set(ct[1]))
	while i < len(b):
		if 0 not in b[i][1] and b[i][0] != 0:
			index2 = max(set(b[i][1]))
			ct3 = b[i][0] + 1
			break
		i += 1
elif ct[0] == 0 and a.count(1) > 0 and (a[0] != a[n - 1] != 1):
	f2 = 1
ref1 = ct1
ref2 = ct2
ref3 = ct3
size = n
n = n - 1
counter = 0
late = 0
cf = 0
qr = input()
c = []
for i in range(q):
	b = []
	if qr[i] == '!':
		if flag == 1:
			qlist = queue(a, counter, ct1, ct2, ct3, n, f, late, ln, ln2, cf)
			counter = qlist[0]
			ct1 = qlist[1]
			ct2 = qlist[2]
			ct3 = qlist[3]
			n = qlist[4]
			f = qlist[5]
			late = qlist[6]
			ln = qlist[7]
			ln2 = qlist[8]
			cf = qlist[9]
	if qr[i] == '?':
		if flag == 0 and f2 == 0:
			c.append(0)
			continue
		elif f2 == 1:
			c.append(1)
			continue
		c.append(max(counter, ct1, ct2, ct3, late))
for i in c:
	if i <= k and i <= size:
		print(i)
	elif i > size and size <= k:
		print(size)
	else:
		print(k)


from collections import deque

def find(l):
	(ans, sans) = (0, 0)
	i = -1
	(index, sindex) = (-1, -1)
	for (x, y) in l:
		i += 1
		if y == 1:
			if x > ans:
				(sans, sindex) = (ans, index)
				(ans, index) = (x, i)
			elif x > sans:
				(sans, sindex) = (x, i)
	return (ans, index, sans, sindex)
(n, q, k) = map(int, input().split(' '))
s = 1
str = input().split(' ')
pr = int(str[0])
l = []
for i in str[1:]:
	p = int(i)
	if p == pr:
		s += 1
	else:
		l.append([s, pr])
		s = 1
	pr = p
if s != 0:
	l.append([s, p])
s = input()
ln = len(l)
if ln == 1 and l[0][1] == 0:
	k = s.count('?')
	print(' '.join(['0'] * k))
else:
	l = deque(l)
	(ans, index, sans, sindex) = find(l)
	find = 0
	for i in range(q):
		if s[i] == '!':
			z = l[ln - 1][1]
			a = l[0][1]
			if z == a:
				l[ln - 1][0] -= 1
				l[0][0] += 1
				ans = l[index][0]
				sans = l[sindex][0]
				if z == 1:
					if ans < l[0][0]:
						(sans, sindex) = (ans, index)
						(ans, index) = (l[0][0], 0)
					elif l[0][0] > sans:
						(sans, sindex) = (l[0][0], 0)
				if l[ln - 1][0] <= 0:
					l.pop()
					ln = ln - 1
			else:
				l[ln - 1][0] -= 1
				l.appendleft([1, z])
				ln = ln + 1
				index += 1
				sindex += 1
				if z == 1:
					if ans < l[0][0]:
						(sans, sindex) = (ans, index)
						(ans, index) = (l[0][0], 0)
					elif l[0][0] > sans:
						(sans, sindex) = (l[0][0], 0)
				if l[ln - 1][0] <= 0:
					l.pop()
					ln = ln - 1
			ans = l[index][0]
			sans = l[sindex][0]
			if ans < sans:
				(ans, sans) = (sans, ans)
				(index, sindex) = (sindex, index)
		elif n <= 1000:
			for (x, y) in l:
				if y == 1:
					ans = max(ans, x)
			print(min(ans, k))
		else:
			print(min(ans, k))


(n, q, k) = map(int, input().split())
a = input()
a = a.replace(' ', '')
query = input()
count = []
temp = 0
m = 0
ind = 0
flag = False
for i in range(n):
	if a[i] == '1':
		temp += 1
	else:
		if temp != 0:
			count.append(temp)
			if temp > m:
				m = temp
		temp = 0
if temp != 0:
	count.append(temp)
	if temp > m:
		m = temp
for i in range(q):
	if query[i] == '!':
		last = a[-1]
		if last == '1':
			flag = True
			if m != count[-1]:
				flag = False
			if count[-1] - 1 != 0:
				count[-1] -= 1
			elif len(count) > 1:
				count.pop(-1)
			else:
				count[0] = 0
			if a[0] == '1':
				count[0] += 1
				if count[0] >= m:
					flag = True
			else:
				count = [1] + count
		else:
			flag = False
		a = last + a[:-1]
	elif len(count) > 0:
		if flag:
			flag = False
			m = max(count)
		if m < k:
			print(m)
		else:
			print(k)
	else:
		print(0)


def m(a, b, c, k):
	if a > b and a <= c:
		if a <= k:
			return a
		return k
	elif a > b and a > c:
		if c <= k:
			return c
		return k
	elif b > c:
		if c <= k:
			return c
			return k
	if b <= k:
		return b
	return k
(n, q, k) = map(int, input().split())
a = list(map(int, input().split()))
query = input()
max1 = 0
max2 = 0
m1cord = 0
count = 0
m1s = 0
si = -1
li = -1
for i in range(n):
	if a[i] == 0:
		break
if i < n - 1:
	si = i - 1
elif a[i] == 1:
	si = n - 1
for i in range(1, n + 1):
	if a[-i] == 0:
		break
li = n - i + 1
if a[-1] == 0:
	li = -1
if si != -1 and li != -1 and (si + 1 + n - li >= max1):
	max2 = max1
	max1 = si + 1 + n - li
	m1cord = si
	m1s = li
elif si != -1 and li != -1 and (si + 1 + n - li > max2):
	max2 = si + 1 + n - li
for i in range(n):
	if a[i] == 1:
		count += 1
	else:
		if count >= max1:
			max2 = max1
			max1 = count
			m1cord = i - 1
			m1s = m1cord - max1 + 1
		elif count > max2 and i != si + 1 and (li != n - count):
			max2 = count
		count = 0
	if i == n - 1 and count >= max1:
		max2 = max1
		max1 = count
		m1cord = i
		m1s = m1cord - max1 + 1
		count = 0
	elif i == n - 1 and count > max2 and (i != si) and (li != n - count):
		max2 = count
		count = 0
for j in query:
	if j == '!':
		m1cord += 1
		m1cord %= n
		m1s += 1
		m1s %= n
	elif m(m1cord + 1, n - m1s, max1, k) > max2:
		print(m(m1cord + 1, n - m1s, max1, k))
	else:
		print(m(max2, max2, max2, k))


(N, Q, K) = map(int, input().split())
A = list(map(int, input().split()))
s = input()
total_zeros = 0
B = [0] * N
C = [0] * N
skip = False
for i in range(len(A)):
	if A[i] == 0:
		total_zeros += 1
if total_zeros == 0:
	maxl = N - 1
	skip = True
if total_zeros == N or total_zeros == N - 1:
	maxl = N - total_zeros
	skip = True
if not skip:
	for i in range(len(A)):
		if A[i] == 0:
			index = i
			break
	T = N
	number_of_1s = 0
	while T:
		if A[i] == 1:
			number_of_1s += 1
		else:
			number_of_1s = 0
		B[i] = number_of_1s
		if i == N - 1:
			i = 0
		else:
			i += 1
		T -= 1
	T = N
	number_of_1s = 0
	while T:
		if A[i] == 1:
			number_of_1s += 1
		else:
			number_of_1s = 0
		C[i] = number_of_1s
		if i == N - 1:
			i = 0
		else:
			i -= 1
		T -= 1
	D = [0] * N
	for i in range(len(B)):
		D[B[i]] += 1
	maxl = 0
	number_of_1s = 0
	for i in range(N):
		if A[i] == 1:
			number_of_1s += 1
		else:
			number_of_1s = 0
		if number_of_1s > maxl:
			maxl = number_of_1s
	j = N - 1
for c in range(Q):
	if s[c] == '!':
		if not skip:
			if B[j] == maxl and D[maxl] == 1:
				maxl -= 1
			if C[j] > maxl:
				maxl = C[j]
			if j == 0:
				j = N - 1
			else:
				j -= 1
	elif s[c] == '?':
		print(min(K, maxl))


(n, q, k) = (int(x) for x in input().split())
li = [int(x) for x in input().split()]
qer = input()
qeries = list(qer)
lis = li[:]
l = len(lis)
for i in range(l):
	if lis[i] == 0:
		break
	elif lis[i] == 1:
		lis[i] = 0
for i in range(l - 1, -1, -1):
	if lis[i] == 0:
		break
	elif lis[i] == 1:
		lis[i] = 0
(current, top) = (0, 0)
i = 0
j = 0
start = 0
end = 0
while j < l:
	if lis[j] == 1:
		j += 1
		current += 1
		if current > top:
			top = current
			start = i
			end = j - 1
	elif lis[j] == 0:
		j += 1
		i = j
		current = 0
for i in range(start, end + 1):
	lis[i] = 0
largest = top
largest_remaining = l - end - 1
if largest == 0:
	largest_remaining = 0
(current, top) = (0, 0)
i = 0
j = 0
while j < l:
	if lis[j] == 1:
		j += 1
		current += 1
		if current > top:
			top = current
			start = i
			end = j - 1
	elif lis[j] == 0:
		j += 1
		i = j
		current = 0
second = top
second_remaining = l - end - 1
if second == 0:
	second_remaining = 0
first = 0
last = 0
for i in range(l):
	if li[i] == 0:
		break
	elif li[i] == 1:
		first += 1
for i in range(l - 1, -1, -1):
	if li[i] == 0:
		break
	elif li[i] == 1:
		last += 1
combine = first + last
combine_mid = combine // 2
if last > 0 and first == 0:
	combine_broken = 1
	combine_remaining = last
elif first > 0 and last == 0:
	combine_broken = 0
	combine_remaining = l - combine
else:
	combine_broken = 1
	combine_remaining = last
largest_mid = largest // 2
second_mid = second // 2
largest_broken = 0
second_broken = 0
if combine >= second:
	second = combine
	second_remaining = combine_remaining
	second_broken = combine_broken
	second_mid = combine_mid
val = max(largest, max(first, last))
for i in qeries:
	if i == '?':
		print(min(k, val))
	else:
		largest_remaining -= 1
		second_remaining -= 1
		largest_off = max(0, min(largest - largest_remaining, largest_remaining))
		second_off = max(0, min(second - second_remaining, second_remaining))
		if largest_remaining == 0:
			if largest_broken == 1:
				largest_broken = 0
				largest_remaining = l - largest
				largest_off = 0
			else:
				largest_broken = 1
				largest_remaining = largest
				largest_off = 0
		if second_remaining == 0:
			if second_broken == 1:
				second_broken = 0
				second_remaining = l - second
				second_off = 0
			else:
				second_broken = 1
				second_remaining = second
				second_off = 0
		val = max(second - second_broken * min(second_mid, second_off), largest - largest_broken * min(largest_mid, largest_off))


(n, q, k) = map(int, input().split())
a = list(input().split())
q = input()
ref = [-1 for _ in range(n)]
max_sequence = [-1 for _ in range(n)]
group = [-1 for _ in range(n)]
max_group = []
count = 0
tracking = []
check = 0
stop = k * 2 - 1
max_check = 0

def update_max(max_arr, max_a):
	while max_a >= len(max_arr):
		max_arr += [[]]
	max_arr[max_a].append(max_a)
for num in range(n):
	if a[num] == '1':
		count += 1
		if count >= stop:
			check = 1
			break
		if num == n - 1:
			group[n - count:] = [count] * count
			ref[n - count:] = [n - count] * count
			if count >= k:
				tracking.append(count)
				if len(tracking) > 1:
					check = 1
			else:
				update_max(max_group, count)
			count = 0
	else:
		group[num] = 0
		if count > 0:
			group[num - count:num] = [count] * count
			ref[num - count:num] = [num - count] * count
			if count >= k:
				tracking.append(count)
				if len(tracking) > 1:
					check = 1
					break
			else:
				update_max(max_group, count)
			count = 0
if len(max_group) < 1:
	max_group += [[0]]
setcheck = set(a)
if check:
	max_sequence[0] = k
elif len(setcheck) == 1:
	if len(tracking) > 0:
		max_sequence[0] = k
	else:
		max_sequence[0] = max_group[-1][0]
else:
	for i in range(len(max_group) - 1, -1, -1):
		while len(max_group[i]) > 0:
			tracking.append(max_group[i][0])
			max_group[i].pop()
			if len(tracking) > 1:
				break
		if len(tracking) > 1:
			break
	tracking.sort()
	max_sequence[0] = tracking[-1]
if not check and len(setcheck) > 1:
	max_check = tracking[-1]

def check_max(ii):
	if max_sequence[ii] != -1:
		return max_sequence[ii]
	else:
		num = n - ii
		if group[num] == max_check:
			shift_num = max_check - (num - ref[num])
			if ref[num] == ref[-1]:
				max_sequence[ii] = min(max(max_check - shift_num, tracking[0], group[0] + shift_num), k)
			elif ref[num] == ref[0]:
				shift_first = num - ref[num]
				max_sequence[ii] = min(max(max_check - shift_num, shift_num, tracking[0], group[-1] + shift_first), k)
			else:
				max_sequence[ii] = min(max(max_check - shift_num, shift_num, tracking[0], group[-1] + group[0]), k)
		else:
			shift_num = group[num] - (num - ref[num])
			if group[num] != 0:
				if ref[num] == ref[-1]:
					max_sequence[ii] = min(max(max_check, shift_num + group[0]), k)
				elif ref[num] == ref[0]:
					shift_first = num - ref[num]
					max_sequence[ii] = min(max(max_check, group[-1] + shift_first), k)
				else:
					max_sequence[ii] = min(max(max_check, group[-1] + group[0]), k)
			else:
				max_sequence[ii] = min(max(max_check, group[-1] + group[0]), k)
		return max_sequence[ii]
idex = 0
cc = 0
for char in q:
	if char == '!':
		if check:
			pass
		elif len(setcheck) > 1:
			idex += 1
			if idex == n:
				idex = 0
	elif char == '?':
		if check:
			print(max_sequence[0])
		else:
			print(check_max(idex))


import sys

def _int():
	return int(sys.stdin.readline())

def _ints():
	return map(int, sys.stdin.readline().split())

def _int_arr():
	return list(map(int, sys.stdin.readline().split()))

def _str():
	return sys.stdin.readline().strip('\n')

def _str_arr():
	return sys.stdin.readline().split()

class Node(object):

	def __init__(self, val, count, nxt, prev):
		self.val = val
		self.count = count
		self.nxt = nxt
		self.prev = prev

	def describe(self):
		pass

def shift(arr, s, e):
	if e is None:
		return (s, e, arr)
	if s.val == e.val:
		if e.count == 1:
			s.count += 1
			node = e.prev
			node.nxt = s
			s.prev = node
			if s.val == 1:
				arr = replace_count(arr, s.count - 1, s.count)
			return (s, node, arr)
		else:
			s.count += 1
			e.count -= 1
			if s.val == 1:
				arr = replace_count(arr, old_count=s.count - 1, new_count=s.count)
				arr = replace_count(arr, old_count=e.count + 1, new_count=e.count)
			return (s, e, arr)
	if s.val == 1 and e.val == 0:
		if e.count == 1:
			return (e, e.prev, arr)
		else:
			e.count -= 1
			node = Node(0, 1, s, e)
			s.prev = node
			e.nxt = node
			return (node, e, arr)
	if s.val == 0 and e.val == 1:
		if e.count == 1:
			return (e, e.prev, arr)
		else:
			e.count -= 1
			node = Node(1, 1, s, e)
			s.prev = node
			e.nxt = node
			arr = add_count(arr, 1)
			arr = replace_count(arr, e.count + 1, e.count)
			return (node, e, arr)

def tree_arr(s, e):
	_tree = []
	if s.nxt is None:
		_tree.append([s.val, s.count])
		return _tree
	i_node = s
	while i_node is not None and i_node != e:
		_tree.append([i_node.val, i_node.count])
		i_node = i_node.nxt
	if i_node is not None:
		_tree.append([i_node.val, i_node.count])
	return _tree

def add_count(arr, count):
	for i in range(0, 5):
		if arr[i] < count:
			arr[i] = count
			arr = sorted(arr)
			break
	return arr

def replace_count(arr, old_count, new_count):
	for i in range(0, 5):
		if arr[i] == old_count:
			arr[i] = new_count
			arr = sorted(arr)
			break
	return arr

def run():
	(_n, _q, k) = _ints()
	a = _int_arr()
	q = _str()
	q = [c for c in q]
	n = len(a)
	max_arr = [0, 0, 0, 0, 0]
	start_node = None
	end_node = None
	prev_node = None
	count = 0
	counting_z = False if a[0] == 1 else True
	for i in range(n):
		if counting_z:
			if a[i] == 1:
				node = Node(0, count, None, prev_node)
				if prev_node is not None:
					prev_node.nxt = node
				if start_node is None:
					start_node = node
				prev_node = node
				prev_node.describe()
				counting_z = False
				count = 1
			else:
				count += 1
		elif a[i] == 1:
			count += 1
		else:
			node = Node(1, count, None, prev_node)
			if prev_node is not None:
				prev_node.nxt = node
			if start_node is None:
				start_node = node
			prev_node = node
			prev_node.describe()
			max_arr = add_count(max_arr, count)
			counting_z = True
			count = 1
	val = 0 if counting_z else 1
	if start_node is None:
		if val == 1:
			max_arr = add_count(max_arr, count)
		start_node = Node(val, count, None, None)
		start_node.nxt = None
		start_node.prev = None
		start_node.describe()
	else:
		if val == 1:
			max_arr = add_count(max_arr, count)
		end_node = Node(val, count, start_node, prev_node)
		prev_node.nxt = end_node
		start_node.prev = end_node
		end_node.describe()
	q_max = max_arr[4]
	for _q in q:
		if _q == '!':
			(start_node, end_node, max_arr) = shift(max_arr, start_node, end_node)
			q_max = max_arr[4]
		else:
			print(min(q_max, k))
run()


x = [int(y) for y in input().split(' ')]
a = [int(y) for y in input().split(' ')]
s = input()
l = []
c = 0
m = 0
d = {}
d[x[0]] = 0
for j in range(0, x[0]):
	d[j] = 0
	if a[j]:
		c = c + 1
	else:
		if c != 0:
			a[j - 1] = c
			a[j - c] = c
			if c not in d:
				d[c] = 1
			else:
				d[c] = d[c] + 1
			m = max(m, c)
		c = 0
if c != 0:
	a[-1] = c
	a[-c] = c
	d[c] = d[c] + 1
	m = max(m, c)
l = 0
r = -1
p = {}
u = 0
while l != -x[0] + 1:
	p[u] = min(m, x[2])
	u = u + 1
	l = l - 1
	r = r - 1
	if a[r + 1] >= 1:
		a[r] = a[r + 1] - 1
		d[a[r + 1]] = d[a[r + 1]] - 1
		if d[m] == 0:
			m = m - 1
		a[(r - a[r] + 1) % x[0]] = a[r]
		d[a[r]] = d[a[r]] + 1
		if a[l + 1]:
			d[a[l + 1]] = d[a[l + 1]] - 1
			a[l] = a[l + 1] + 1
			a[l + a[l] - 1] = a[l]
			d[a[l]] = d[a[l]] + 1
			m = max(m, a[l])
		else:
			a[l] = 1
			d[1] = d[1] + 1
c = 0
p[x[0] - 1] = min(m, x[2])
for j in range(0, len(s)):
	if s[j] == '!':
		c = (c + 1) % x[0]
	else:
		print(p[c])


(n, q, m) = map(int, input().split())
lis = list(map(int, input().split()))
tree = [[0, 0, 0, 0] for i in range(8 * n + 1)]

def build(arr, start, end, node):
	if start == end:
		if arr[start - 1] == 1:
			ans = 1
		else:
			ans = 0
		tree[node] = [ans, ans, 1 - ans, ans]
	else:
		mid = (start + end) // 2
		left_child = 2 * node
		right_child = left_child + 1
		build(arr, start, mid, left_child)
		build(arr, mid + 1, end, right_child)
		if tree[left_child][2] == 0:
			tree[node][0] = tree[left_child][0] + tree[right_child][0]
		else:
			tree[node][0] = tree[left_child][0]
		if tree[right_child][2] == 0:
			tree[node][1] = tree[left_child][1] + tree[right_child][1]
		else:
			tree[node][1] = tree[right_child][1]
		tree[node][2] = tree[left_child][2] + tree[right_child][2]
		tree[node][3] = max(tree[left_child][3], tree[right_child][3], tree[left_child][1] + tree[right_child][0])

def query(start, end, qstart, qend, node):
	if start > qend or end < qstart:
		return None
	if qstart <= start and end <= qend:
		return tree[node]
	mid = (start + end) // 2
	left_child = 2 * node
	right_child = left_child + 1
	left_query = query(start, mid, qstart, qend, left_child)
	right_query = query(mid + 1, end, qstart, qend, right_child)
	if not left_query:
		return right_query
	if not right_query:
		return left_query
	ans = [0, 0, 0, 0]
	if left_query[2] == 0:
		ans[0] = left_query[0] + right_query[0]
	else:
		ans[0] = left_query[0]
	if right_query[2] == 0:
		ans[1] = left_query[1] + right_query[1]
	else:
		ans[1] = right_query[1]
	ans[2] = left_query[2] + right_query[2]
	ans[3] = max(left_query[3], right_query[3], left_query[1] + right_query[0])
	return ans
lis += lis
last = 2 * n
build(lis, 1, last, 1)
query_string = input()
shift = 0
for i in range(q):
	if query_string[i] == '?':
		shift %= n
		ans = query(1, last, n + 1 - shift, last - shift, 1)
		print(min(m, ans[3]))
	else:
		shift += 1


(n, q, k) = map(int, input().strip().split(' '))
lst = list(map(int, input().strip().split(' ')))
c = input()
Q = [0] * n
(Max, size, p) = (0, 0, 0)
L = []
l = []
r = []
if lst.count(1) == n:
	for i in range(q):
		if c[i] == '?':
			if n >= k:
				print(k)
			else:
				print(n)
elif lst.count(0) == n:
	for i in range(q):
		if c[i] == '?':
			print(0)
else:
	x = lst.index(1)
	l.append(x)
	size = size + 1
	for i in range(x, n - 1):
		if lst[i] == 1 and lst[i + 1] == 0:
			r.append(i)
		elif lst[i] == 0 and lst[i + 1] == 1:
			l.append(i + 1)
			size = size + 1
	if lst[n - 1] != 0:
		r.append(n - 1)
	for i in range(size):
		L.append(r[i] - l[i] + 1)
		if r[i] - l[i] + 1 > Max:
			Max = r[i] - l[i] + 1
			cur = l[i]
	La = sorted(L)
	if size == 1:
		Max2 = 0
	elif size == 2 and lst[0] == 1 and (lst[-1] == 1):
		p = L[0] + L[-1]
		if p > Max:
			Max = p
			cur = l[-1]
		Max2 = 0
	elif lst[0] == 1 and lst[-1] == 1:
		p = L[0] + L[-1]
		if size != 3:
			g = sorted(L[1:size - 1])
			Max2 = g[-2]
		if size == 3:
			if p >= L[1]:
				Max = p
				cur = l[-1]
				Max2 = L[1]
			else:
				Max = L[1]
				cur = l[-2]
				Max2 = p
		elif p > Max:
			if cur == l[-1] or cur == 0:
				Max = p
				if cur == 0:
					cur = l[-1]
					g = sorted(L[1:size - 1])
					Max2 = g[-1]
			else:
				Max2 = Max
				Max = p
				cur = l[-1]
		elif p <= Max and p > Max2:
			Max2 = p
	else:
		Max2 = La[-2]
	if Max >= k:
		m = k
	else:
		m = Max
	for i in range(n - Max + 1):
		Q[i] = m
	for i in range(n - Max + 1, n):
		if n - i >= Max2 and n - i >= Max - n + i:
			if n - i >= k:
				Q[i] = k
			else:
				Q[i] = n - i
		elif n - i <= Max2 and Max2 >= Max - n + i:
			if Max2 >= k:
				Q[i] = k
			else:
				Q[i] = Max2
		elif Max - n + i >= k:
			Q[i] = k
		else:
			Q[i] = Max - n + i
	for i in range(q):
		if c[i] == '?':
			print(Q[cur])
		elif c[i] == '!':
			cur = cur + 1
			cur = cur % n


Zeroes = {0: []}
possLengths = []
cornerArr = []
maxPossLen = 0
case_0 = False
case_1 = False
case_2 = False
case_3 = False
currMaxLen = 0
(N, Q, K) = map(int, input().split())
seq = [int(_) for _ in input().split()]
queries = list(input())
pattern = []

def shift(A):
	B = []
	B.append(A[len(A) - 1])
	for i in range(len(A) - 1):
		B.append(A[i])
	return B

def cornerPattern(maxLen):
	counter = maxLen
	for i in range(maxLen // 2):
		cornerArr.append(counter - i - 1)
	counter = cornerArr[maxLen // 2 - 1]
	if not maxLen % 2:
		for i in range(maxLen // 2 - 1):
			cornerArr.append(counter + i + 1)
	else:
		for i in range(maxLen // 2):
			cornerArr.append(counter + i)

def maxSeqO1(arr):
	maxLength = []
	length = 1
	for i in range(len(arr)):
		if i == len(arr) - 1:
			if arr[i] == 1 and length != 0:
				maxLength.append(length)
		elif arr[i] == arr[i + 1] and i != len(arr) - 1:
			if arr[i] == 1:
				length += 1
		else:
			maxLength.append(length)
			length = 1
	return max(maxLength)

def checkMaxIndex(givenLen):
	indMax = possLengths.index(givenLen)
	if case_0:
		return Zeroes[0][indMax + 1]
	if case_1:
		if indMax == len(possLengths) - 1:
			return N
		return Zeroes[0][indMax + 1]
	if case_2:
		if indMax == len(possLengths) - 1:
			return maxPossLen
		return Zeroes[0][indMax + 1]
	if case_3:
		if indMax == len(possLengths) - 2:
			return N + possLengths[len(possLengths) - 1][0]
		return Zeroes[0][indMax + 1]
	return Zeroes[0][indMax + 1]
if N <= 10 ** 3 and Q <= 3 * 10 ** 3:
	for i in queries:
		if i == '!':
			seq = shift(seq)
		else:
			temp = maxSeqO1(seq)
			finAns = min(temp, K)
			print(finAns)
elif not seq.count(1):
	for i in range(queries.count('?')):
		print('0')
elif not seq.count(0):
	for i in range(queries.count('?')):
		print(min(K, N))
elif seq.count(0) == 1:
	ind0 = seq.index(0)
	for i in queries:
		left = ind0
		right = N - ind0 - 1
		if i == '!':
			ind0 = (ind0 + 1) % N
		else:
			finAns = max(left, right)
			if finAns > K:
				print(K)
			else:
				print(finAns)
else:
	if seq[0] == 0 and seq[N - 1] == 0:
		case_0 = True
	elif seq[0] == 0 and seq[N - 1] == 1:
		case_1 = True
	elif seq[0] == 1 and seq[N - 1] == 0:
		case_2 = True
	else:
		case_3 = True
	for i in range(N):
		if seq[i] is 0:
			Zeroes[0].append(i)
	for i in range(len(Zeroes[0]) - 1):
		possLengths.append(Zeroes[0][i + 1] - Zeroes[0][i] - 1)
	if case_1:
		possLengths.append(N - Zeroes[0][len(Zeroes[0]) - 1] - 1)
	elif case_2:
		possLengths.append(Zeroes[0][0])
	elif case_3:
		right = N - Zeroes[0][len(Zeroes[0]) - 1] - 1
		left = Zeroes[0][0]
		possLengths.append(left + right)
		maxPossLen = max(possLengths)
		possLengths.append([left, right])
	if not case_3:
		maxPossLen = max(possLengths)
	if maxPossLen == 1:
		for i in range(queries.count('?')):
			print('1')
	else:
		rotation = 0
		maxPossRot = N - maxPossLen
		indOfMax = checkMaxIndex(maxPossLen)
		cornerPattern(maxPossLen)
		possLengths.remove(maxPossLen)
		currPossRot = N - indOfMax
		finAns = min(maxPossLen, K)
		if currPossRot < 0:
			rightt = maxPossLen + currPossRot
			for i in range(rightt):
				pattern.append(cornerArr[abs(currPossRot) + i - 1])
			for i in range(maxPossRot + 1):
				pattern.append(maxPossLen)
			for i in range(abs(currPossRot) - 1):
				pattern.append(cornerArr[i])
		else:
			for i in range(currPossRot + 1):
				pattern.append(maxPossLen)
			for i in range(len(cornerArr)):
				pattern.append(cornerArr[i])
			for i in range(maxPossRot - currPossRot):
				pattern.append(maxPossLen)
			if not case_3:
				currMaxLen = max(possLengths)
			else:
				currMaxLen = max(possLengths[:len(possLengths) - 1])
		for i in queries:
			if i == '!':
				rotation += 1
			else:
				ind = rotation % N
				temp = max(currMaxLen, pattern[ind])
				finAns = min(K, temp)
				print(finAns)


best1 = (0, 0)
best2 = (0, 0)
cur = [0, 0]
start = 0
end = 0
tokens = input().split()
n = int(tokens[0])
q = int(tokens[1])
k = int(tokens[2])
digits = input().split()
for i in range(n):
	if digits[i] == '1':
		cur[1] += 1
		if cur[1] > best1[1]:
			if cur[0] != best1[0]:
				best2 = best1
			best1 = (cur[0], cur[1])
		elif cur[1] > best2[1]:
			best2 = (cur[0], cur[1])
	if digits[i] == '0':
		cur[0] = i + 1
		cur[1] = 0
	if cur[0] == 0:
		start = cur[1]
	if cur[0] + cur[1] == n:
		end = cur[1]
idx = 0
queries = input()

def largest(pair, idx):
	t = 0
	if idx > pair[0] and idx < pair[0] + pair[1]:
		return max(idx - pair[0], pair[1] + pair[0] - idx)
	return pair[1]
for c in queries:
	if c == '!':
		idx = (idx - 1 + n) % n
	if c == '?':
		res = 0
		if best1[1] == n:
			res = n
		elif idx < start:
			res = max(end + idx, start - idx)
		elif idx > n - end:
			res = max(start + n - idx, idx - n + end)
		else:
			res = start + end
		res = max(res, largest(best1, idx))
		res = max(res, largest(best2, idx))
		res = min(res, k)
		print(res)


ar = [int(e) for e in input().split()]
a = [int(e) for e in input().split()]
s = input()
m = {}
mx = 0
c = 0
l = []
for i in range(-1, -ar[0] - 1, -1):
	if a[i] == 0 and c > 0:
		l.append(c)
		if c >= mx:
			mx = c
			idx = len(l) - 1
		c = 0
	elif a[i] == 1:
		c += 1
l.append(c)
if c >= mx:
	mx = c
	idx = len(l) - 1
if a[-1] == 0 and a[0] == 0:
	del l[-1]
m[0] = mx
sidx = 0
k = 0
mx = 0
f = 0
for j in range(1, ar[0]):
	if a[-j] == 0:
		l.append(0)
		m[j] = m[j - 1]
	else:
		l[k] -= 1
		l[-1] += 1
		if l[idx] <= l[-1]:
			idx = len(l) - 1
		elif k == idx and f == 0:
			for i in range(k + 1, len(l)):
				if mx <= l[i]:
					sidx = i
					mx = l[i]
				f = 1
		if l[idx] <= l[sidx]:
			idx = sidx
		if l[k] == 0:
			k += 1
		m[j] = l[idx]
c = 0
for i in s:
	if i == '!':
		c += 1
	else:
		x = int(c % ar[0])
		if m[x] < ar[2]:
			print(m[x])
		else:
			print(ar[2])


def prevIndex(cur, n):
	return (cur - 1) % n

def nextIndex(cur, n):
	return (cur + 1) % n

def absIndex(cur, n):
	return cur % n

def do(s):
	s = [int(s[i]) for i in range(0, len(s), 2)]
	print(s)
	for i in range(len(s) - 1):
		s.insert(0, s.pop())
		print(s)
dic = {'item': 0, 'max_left': 1, 'max_cont_left': 2, 'max_right': 3, 'max_cont_right': 4, 'ans': 5}

def prepareForBattle(s):
	s = [int(s[i]) for i in range(0, len(s), 2)]
	(start, end) = (int(0), int(len(s)) - 1)
	s1 = [[0 for i in range(len(s))] for j in range(6)]
	s1[0] = s
	s = s1
	globalMax = 0
	localMax = 0
	for i in range(start, end + 1, 1):
		if s[dic['item']][i] == 0:
			localMax = 0
		else:
			localMax += 1
			globalMax = max(globalMax, localMax)
		s[dic['max_left']][i] = globalMax
		s[dic['max_cont_left']][i] = localMax
	if s[dic['item']][start] == 1 and s[dic['item']][end] == 1:
		cur = start
		while s[dic['item']][cur] == 1:
			s[dic['max_cont_left']][cur] = s[dic['max_cont_left']][prevIndex(cur, end + 1)] + 1
			cur = nextIndex(cur, end + 1)
	globalMax = 0
	localMax = 0
	for i in range(end, start - 1, -1):
		if s[dic['item']][i] == 0:
			localMax = 0
		else:
			localMax += 1
			globalMax = max(globalMax, localMax)
		s[dic['max_right']][i] = globalMax
		s[dic['max_cont_right']][i] = localMax
	if s[dic['item']][start] == 1 and s[dic['item']][end] == 1:
		cur = end
		while s[dic['item']][cur] == 1:
			s[dic['max_cont_right']][cur] = s[dic['max_cont_right']][nextIndex(cur, end + 1)] + 1
			cur = prevIndex(cur, end + 1)
	s[dic['ans']][end] = s[dic['max_left']][end]
	for i in range(end - 1, start - 1, -1):
		startComponent = 0
		endComponent = 0
		if s[dic['item']][start] == 1 and s[dic['item']][end] == 1:
			startComponent = s[dic['max_cont_right']][start]
			indexOfFirstContStarted = start + s[dic['max_cont_right']][start] - 1
			if i < indexOfFirstContStarted:
				startComponent -= s[dic['max_cont_right']][nextIndex(i, end + 1)]
			indexOfLastMaxContStarted = end - s[dic['max_cont_left']][end] + 1
			endComponent = s[dic['max_cont_left']][end]
			if i >= indexOfLastMaxContStarted:
				endComponent -= s[dic['max_cont_left']][i]
		s[dic['ans']][i] = max(s[dic['max_left']][i], s[dic['max_right']][nextIndex(i, end + 1)], startComponent + endComponent)
	return s
(n, q, k) = map(int, input().strip().split(' '))
s = input()
exp = input()
ans = []
if s.count('0') == 0:
	ans = [n for i in range(n)]
else:
	ans = prepareForBattle(s)[dic['ans']]
index = 0
for x in exp:
	if x is '!':
		index += 1
	else:
		print(min(ans[n - absIndex(index, n) - 1], k))


from sys import stdin, stdout
best1 = (0, 0)
best2 = (0, 0)
cur = [0, 0]
start = 0
end = 0
tokens = stdin.readline().split()
n = int(tokens[0])
q = int(tokens[1])
k = int(tokens[2])
digits = stdin.readline().split()
for i in range(n):
	if digits[i] == '1':
		cur[1] += 1
		if cur[1] > best1[1]:
			if cur[0] != best1[0]:
				best2 = best1
			best1 = (cur[0], cur[1])
		elif cur[1] > best2[1]:
			best2 = (cur[0], cur[1])
	if digits[i] == '0':
		cur[0] = i + 1
		cur[1] = 0
	if cur[0] == 0:
		start = cur[1]
	if cur[0] + cur[1] == n:
		end = cur[1]
idx = 0
queries = stdin.readline()

def largest(pair, idx):
	t = 0
	if idx > pair[0] and idx < pair[0] + pair[1]:
		return max(idx - pair[0], pair[1] + pair[0] - idx)
	return pair[1]
for c in queries:
	if c == '!':
		idx = (idx - 1 + n) % n
	if c == '?':
		res = 0
		if best1[1] == n:
			res = n
		elif idx < start:
			res = max(end + idx, start - idx)
		elif idx > n - end:
			res = max(start + n - idx, idx - n + end)
		else:
			res = start + end
		res = max(res, largest(best1, idx))
		res = max(res, largest(best2, idx))
		res = min(res, k)
		print(res)


(n, q, k) = map(int, input().split())
a = [int(x) for x in input().split()]
s = input()
m = 0
l = 0
for i in a:
	if i == 1:
		m += 1
	else:
		m = 0
	if m >= k:
		l = k
		break
	elif m > l:
		l = m
for i in s:
	if i == '?':
		print(l)
	else:
		a.insert(0, a[n - 1])
		a.pop()
		if a[0] != 0:
			m = 0
			l = 0
			for j in a:
				if j == 1:
					m += 1
				else:
					m = 0
				if m >= k:
					l = k
					break
				elif m > l:
					l = m


from collections import defaultdict
res = []

def findAllOne(seq):
	(cnt, s, pos) = (0, 0, defaultdict(list))
	for i in range(len(seq)):
		if seq[i] == 1 and i == 0:
			cnt += 1
			s = i
		elif seq[i] == 1 and seq[i - 1] == 0 and (i > 0):
			cnt += 1
			s = i
		elif seq[i - 1] == 1 and seq[i] == 1 and (i > 0):
			cnt += 1
		elif seq[i] == 0 and seq[i - 1] == 1 and (i > 0):
			pos[cnt].append([s, s + cnt])
			cnt = 0
	nn = []
	if cnt > 0:
		pos[cnt].append([s, s + cnt])
		nn += [s, s + cnt]
		cnt = 0
	l = list(pos.keys())
	l.sort(reverse=True)
	for i in l:
		if len(nn) <= 5:
			for pp in pos[i]:
				if pp[0] not in nn:
					nn.append(pp[0])
					nn.append(pp[1])
	nn.sort()
	return nn
(N, Q, K) = map(int, input().split())
seq = list(map(int, input().split()))
N = len(seq)
query = input().strip()
position = findAllOne(seq)
for i in query:
	if i == '!':
		if len(position):
			position = [j + 1 for j in position]
			if position[-1] > N:
				position = [0, 1] + position
				position[-1] -= 1
			nw = [position[0]]
			for p in position[1:]:
				if nw[-1] != p:
					nw.append(p)
				else:
					del nw[-1]
			position = []
			position = nw[:]
	else:
		mx = 0
		for i in range(0, len(position), 2):
			mx = max(mx, position[i + 1] - position[i])
		res.append(min(mx, K))
print(*res, sep='\n')


from collections import namedtuple
import sys
RED = 1
BLACK = 0

class RBTree:

	class Node:

		def __init__(self, val, par=None, left=None, right=None, col=RED):
			self.val = val
			self.par = par
			self.left = left
			self.right = right
			self.col = col

		@property
		def uncle(self):
			assert self.par
			return self.par.sib

		@property
		def grandpa(self):
			assert self.par
			return self.par.par

		@property
		def sib(self):
			assert self.par
			return self.par.left if self.par.right == self else self.par.right

		@property
		def is_left(self):
			assert self.par
			return self.par.left == self

		@property
		def is_right(self):
			assert self.par
			return self.par.right == self

		def replace(self, old_child, new_child):
			assert old_child == self.left or old_child == self.right
			if old_child == self.left:
				self.left = new_child
			if old_child == self.right:
				self.right = new_child

		def __repr__(self):
			return '(val={}; p={}; l={}; r={}; c={})'.format(self.val, self.par.val if self.par else None, self.left.val if self.left else None, self.right.val if self.right else None, 'BLACK' if self.col == BLACK else 'RED')

	class NullNode(Node):

		def __init__(self, par):
			super().__init__(None, par=par, col=BLACK)

		@property
		def sib(self):
			assert self.par
			assert not self.par.left or not self.par.right
			return self.par.left if self.par.left else self.par.right

		@property
		def is_left(self):
			assert self.par
			assert not self.par.left or not self.par.right
			return not self.par.left

		@property
		def is_right(self):
			assert self.par
			assert not self.par.left or not self.par.right
			return not self.par.right

		def replace(self, old_child, new_child):
			raise NotImplementedError('NullNode can not have children')

	def __init__(self):
		self._root = None
		self._size = 0

	def __iter__(self):
		return self._traverse(self._root)

	def __len__(self):
		return self._size

	def __contains__(self, x):
		if not self._root:
			return False
		return self._find(self._root, x) is not None

	def __repr__(self):
		return 'RBTree(root={})'.format(self._root)

	def insert(self, x):
		self._size += 1
		n = RBTree.Node(x)
		if not self._root:
			self._root = n
			n.col = BLACK
			return
		self._insert_node(self._root, n)
		self._rebalance_addition(n)

	def remove(self, x):
		n = self._find(self._root, x)
		if not n:
			raise KeyError(x)
		(n, s) = self._remove_node(n)
		if not s.par:
			if not isinstance(s, RBTree.NullNode):
				self._root = s
			else:
				self._root = None
				return
		if n.col == RED:
			return
		if s.col == RED or self._root == s:
			s.col = BLACK
			return
		self._rebalance_removal(s)

	def min(self):
		if not self._root:
			raise ValueError('Can not find min element of an empty tree')
		return self._left_most_node(self._root).val

	def max(self):
		if not self._root:
			raise ValueError('Can not find max element of an empty tree')
		return self._right_most_node(self._root).val

	def validate(self):
		(is_valid, _) = self._validate_and_get_black_height(self._root)
		return is_valid

	def _traverse(self, n):
		if n.left:
			yield from self._traverse(n.left)
		yield n.val
		if n.right:
			yield from self._traverse(n.right)
		if not n:
			return

	def _validate_and_get_black_height(self, n):
		if n is None:
			return (True, 0)
		if n.par and n.par.col == RED and (n.col == RED):
			print('Found two red nodes in a row: {} and {}'.format(n.par, n))
			return (False, -1)
		if n.left and n.left.par != n:
			print('Child {} of a node {} has invalid parent'.format(n.left, n))
			return (False, -1)
		if n.right and n.right.par != n:
			print('Child {} of a node {} has invalid parent'.format(n.right, n))
			return (False, -1)
		(l_valid, l_bh) = self._validate_and_get_black_height(n.left)
		(r_valid, r_bh) = self._validate_and_get_black_height(n.right)
		if not l_valid or not r_valid:
			return (False, -1)
		if l_bh != r_bh:
			print('Node {} has subtrees of different black height: left={}, right={}'.format(n, l_bh, r_bh))
			return (False, -1)
		return (True, l_bh if n.col == RED else l_bh + 1)

	def _find(self, n, x):
		if n.val == x:
			return n
		if x < n.val and n.left:
			return self._find(n.left, x)
		elif x > n.val and n.right:
			return self._find(n.right, x)
		return None

	def _left_most_node(self, n):
		while n.left:
			n = n.left
		return n

	def _right_most_node(self, n):
		return n if not n.right else self._right_most_node(n.right)

	def _insert_node(self, par, n):
		if n.val < par.val:
			if par.left:
				self._insert_node(par.left, n)
			else:
				par.left = n
				n.par = par
		elif par.right:
			self._insert_node(par.right, n)
		else:
			par.right = n
			n.par = par

	def _rebalance_addition(self, n):
		if n.col == BLACK:
			return
		if self._root == n:
			n.col = BLACK
			return
		if n.par.col == BLACK:
			return
		if n.uncle and n.uncle.col == RED:
			n.par.col = BLACK
			n.uncle.col = BLACK
			n.grandpa.col = RED
			self._rebalance_addition(n.grandpa)
			return
		if n.is_left and n.par.is_left:
			self._handle_left_left(n)
		elif n.is_right and n.par.is_left:
			self._handle_left_right(n)
		elif n.is_right and n.par.is_right:
			self._handle_right_right(n)
		elif n.is_left and n.par.is_right:
			self._handle_right_left(n)

	def _remove_node(self, n):
		if n.left and n.right:
			successor = self._left_most_node(n.right)
			val = n.val
			n.val = successor.val
			successor.val = val
			return self._remove_node(successor)
		elif n.left:
			if n.par:
				n.par.replace(n, n.left)
			n.left.par = n.par
			return (n, n.left)
		elif n.right:
			if n.par:
				n.par.replace(n, n.right)
			n.right.par = n.par
			return (n, n.right)
		else:
			if n.par:
				n.par.replace(n, None)
			return (n, RBTree.NullNode(n.par))

	def _rebalance_removal(self, n):
		s = n.sib
		assert s
		if s.col == BLACK and (s.left and s.left.col == RED or (s.right and s.right.col == RED)):
			r = s.right if s.right and s.right.col == RED else s.left
			if s.is_left and r.is_left:
				self._rotate_right(n.par)
				r.col = BLACK
			elif s.is_left and r.is_right:
				self._rotate_left(s)
				self._rotate_right(n.par)
				s.col = BLACK
			elif s.is_right and r.is_left:
				self._rotate_right(s)
				self._rotate_left(n.par)
				s.col = BLACK
			elif s.is_right and r.is_right:
				self._rotate_left(n.par)
				r.col = BLACK
		elif s.col == BLACK:
			s.col = RED
			if n.par.col == RED:
				n.par.col = BLACK
			elif n.par.col == BLACK and n.par != self._root:
				self._rebalance_removal(n.par)
		else:
			if s.is_right:
				self._rotate_left(n.par)
			else:
				self._rotate_right(n.par)
			self._rebalance_removal(n)

	def _handle_left_left(self, n):
		self._rotate_right(n.grandpa)

	def _handle_left_right(self, n):
		self._rotate_left(n.par)
		self._handle_left_left(n.left)

	def _handle_right_right(self, n):
		self._rotate_left(n.grandpa)

	def _handle_right_left(self, n):
		self._rotate_right(n.par)
		self._handle_right_right(n.right)

	def _rotate_right(self, n):
		assert n.left
		l = n.left
		lr = l.right
		par = n.par
		col = n.col
		l.right = n
		n.par = l
		l.par = par
		n.col = l.col
		l.col = col
		n.left = lr
		if lr:
			lr.par = n
		if n == self._root:
			self._root = l
		else:
			par.replace(n, l)

	def _rotate_left(self, n):
		assert n.right
		r = n.right
		rl = r.left
		par = n.par
		col = n.col
		r.left = n
		n.par = r
		r.par = par
		n.col = r.col
		r.col = col
		n.right = rl
		if rl:
			rl.par = n
		if n == self._root:
			self._root = r
		else:
			par.replace(n, r)

class Node:

	def __init__(self, pos, l, next, prev):
		self.pos = pos
		self.l = l
		self.next = next
		self.prev = prev

	def __repr__(self):
		return '({};{})'.format(self.pos + 1, self.l)

def read_data():
	(n, _, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	q = input()
	return (n, q, k, a)

def construct_dlist(a, tree):
	last_node = None
	curr_node = None
	first_node = None
	for (i, x) in enumerate(a):
		if x == 0:
			if curr_node:
				tree.insert(curr_node.l)
			curr_node = None
		elif curr_node:
			curr_node.pos = i
			curr_node.l += 1
		else:
			curr_node = Node(i, 1, None, last_node)
			if last_node:
				last_node.next = curr_node
			last_node = curr_node
			if not first_node:
				first_node = curr_node
	if curr_node:
		tree.insert(curr_node.l)
	if not last_node:
		return None
	first_node.prev = last_node
	last_node.next = first_node
	return last_node

def update_node(node, offset, n, tree):
	if (node.pos + offset) % n != 0:
		return node
	node.pos = (node.pos + n - 1) % n
	tree.remove(node.l)
	node.l -= 1
	tree.insert(node.l)
	if (node.next.pos - node.next.l + n + offset) % n == 0:
		tree.remove(node.next.l)
		node.next.l += 1
		tree.insert(node.next.l)
	else:
		next = node.next
		node.next = Node((node.pos + 1) % n, 1, next, node)
		next.prev = node.next
		tree.insert(node.next.l)
	if node.l == 0:
		prev = node.prev
		prev.next = node.next
		node.next.prev = prev
		tree.remove(node.l)
		return prev
	else:
		return node

def to_len_list(node):
	temp = node
	arr = []
	while True:
		arr.append(-temp.l)
		if temp.prev == node:
			return arr
		temp = temp.prev

def handle_no_ones(q):
	for req in q:
		if req == '?':
			print(0)
(n, q, k, a) = read_data()
tree = RBTree()
curr_node = construct_dlist(a, tree)
if not curr_node:
	handle_no_ones(q)
	sys.exit()
offset = 0
for req in q:
	if req == '!':
		offset += 1
		curr_node = update_node(curr_node, offset, n, tree)
	else:
		if not curr_node:
			print(0)
			continue
		print(min(tree.max(), k))


from collections import deque
(N, Q, K) = map(int, input().split())
arrZO = list(map(int, input().split()))
arrZO = arrZO[::-1]
arrZO.append(0)
queries = input()
segmentQueues = deque()
tempSeg = 0
for i in range(len(arrZO)):
	if arrZO[i] == 1:
		tempSeg += 1
	elif tempSeg != 0:
		while segmentQueues and segmentQueues[-1][1] <= tempSeg:
			segmentQueues.pop()
		segmentQueues.append([i - tempSeg, tempSeg])
		tempSeg = 0
arrZO.pop()
arrZO = arrZO + arrZO + arrZO
counter = 0
for i in range(Q):
	if queries[i] == '?':
		if segmentQueues:
			print(min(segmentQueues[0][1], K))
		else:
			print(0)
	elif queries[i] == '!':
		if segmentQueues and segmentQueues[0][0] == counter:
			tSeg = segmentQueues.popleft()
			tSeg[1] -= 1
			tSeg[0] += 1
			if segmentQueues and segmentQueues[0][1] < tSeg[1]:
				segmentQueues.appendleft(tSeg)
			elif len(segmentQueues) == 0 and tSeg[1] > 0:
				segmentQueues.append(tSeg)
		if arrZO[N + counter] == 1:
			if segmentQueues and segmentQueues[-1][0] + segmentQueues[-1][1] == N + counter:
				tSeg = segmentQueues.pop()
				tSeg[1] += 1
				while segmentQueues and tSeg[1] >= segmentQueues[-1][1]:
					segmentQueues.pop()
				segmentQueues.append(tSeg)
			else:
				while segmentQueues and segmentQueues[-1][1] < 2:
					segmentQueues.pop()
				segmentQueues.append([N + counter, 1])
		counter += 1


import os
import math
import collections
(n, qu, z) = map(int, input().split())
l = list(map(int, input().split()))
string = input()
if n == 1:
	for i in string:
		if i == '?':
			print(1) if l[0] == 1 else print(0)
elif n == 2:
	ccnt = 0
	for i in range(n):
		if l[i] == 1:
			ccnt += 1
	if ccnt == 2:
		for i in string:
			if i == '?':
				print(ccnt) if ccnt <= z else print(z)
	if ccnt == 0:
		for i in string:
			if i == '?':
				print(0)
	if ccnt == 1:
		for i in string:
			if i == '!':
				(l[0], l[1]) = (l[1], [0])
			else:
				print(1)
else:
	b = [0, [0, 0]]
	count = 0
	s = -1
	for i in range(len(l)):
		if l[i] == 1:
			count += 1
			if s == -1:
				s = i
		else:
			if count != 0:
				e = i
				b = [count, [s, e - 1]]
			break
	if count != 0 and b[0] == 0:
		b = [count, [0, len(l) - 1]]
	j = i + 1
	if j < len(l):
		x = []
		count = 0
		(s, e) = (0, 0)
		for i in range(j, len(l)):
			if l[i] == 1:
				count += 1
				if s == 0:
					s = i
			else:
				if count != 0:
					e = i
					x.append([count, [s, e - 1]])
					(s, e) = (0, 0)
				count = 0
		if count != 0:
			x.append([count, [s, len(l) - 1]])
		len_x = len(x)
		if b == 0 and len_x == 0:
			for i in string:
				if i == '?':
					print(0)
		if len_x == 0:
			(ww1, ww2) = ([0, [0, 0]], [0, [0, 0]])
		elif len_x == 1:
			ww1 = x[0]
			ww2 = [0, [0, 0]]
		elif len_x >= 2:
			x = sorted(x, reverse=True)
			ww1 = x[0]
			ww2 = x[1]
		last = n - 1
		k = n - 1
		for i in string:
			if i == '!':
				if l[k] == 0 and l[(k + 1) % n] == 0:
					ww1[1][0] += 1
					ww1[1][1] += 1
					ww2[1][0] += 1
					ww2[1][1] += 1
				elif l[k] == 0 and l[(k + 1) % n] == 1:
					if b[0] > ww1[0]:
						if ww1[0] > ww2[0]:
							ww2 = ww1
							ww1 = b
							b = [0, [0, 0]]
						else:
							ww1 = b
							b = [0, [0, 0]]
					elif b[0] > ww2[0]:
						ww2 = b
						b = [0, [0, 0]]
					else:
						b = [0, [0, 0]]
					ww1[1][0] += 1
					ww1[1][1] += 1
					ww2[1][0] += 1
					ww2[1][1] += 1
				elif l[k] == 1 and l[(k + 1) % n] == 0:
					b = [1, [0, 0]]
					if last >= ww1[1][0] and last <= ww1[1][1]:
						ww1[0] -= 1
						if ww1[0] == 0:
							ww1[1][0] = 0
							ww1[1][1] = 0
						else:
							ww1[1][0] += 1
						ww2[1][0] += 1
						ww2[1][1] += 1
					elif last >= ww2[1][0] and last <= ww2[1][1]:
						ww2[0] -= 1
						if ww2[0] == 0:
							ww2[1][0] = 0
							ww2[1][1] = 0
						else:
							ww2[1][0] += 1
						ww1[1][0] += 1
						ww1[1][1] += 1
					else:
						ww1[1][0] += 1
						ww1[1][1] += 1
						ww2[1][0] += 1
						ww2[1][1] += 1
				elif l[k] == 1 and l[(k + 1) % n] == 1:
					b[0] += 1
					b[1][1] += 1
					if last >= ww1[1][0] and last <= ww1[1][1]:
						ww1[0] -= 1
						if ww1[0] == 0:
							ww1[1][0] = 0
							ww1[1][1] = 0
						else:
							ww1[1][0] += 1
						ww2[1][0] += 1
						ww2[1][1] += 1
					elif last >= ww2[1][0] and last <= ww2[1][1]:
						ww2[0] -= 1
						if ww2[0] == 0:
							ww2[1][0] = 0
							ww2[1][1] = 0
						else:
							ww2[1][0] += 1
						ww1[1][0] += 1
						ww1[1][1] += 1
					else:
						ww1[1][0] += 1
						ww1[1][1] += 1
						ww2[1][0] += 1
						ww2[1][1] += 1
				k -= 1
				if k < 0:
					k = n - 1
			else:
				M = max(b[0], ww1[0], ww2[0])
				if M <= z:
					print(M)
				else:
					print(z)
	elif b[0] == n:
		for i in string:
			if i == '?':
				if b[0] <= z:
					print(b[0])
				else:
					print(z)
	else:
		last = n - 1
		b = b[0]
		beg = b
		for i in string:
			if i == '!':
				if l[last] == 1 and l[(last + 1) % n] == 0:
					b = 1
					beg -= 1
					last -= 1
				elif l[last] == 1 and l[(last + 1) % n] == 1:
					b += 1
					beg -= 1
					last -= 1
				elif l[last] == 0 and l[(last + 1) % n] == 1:
					b = 0
					last -= 1
				else:
					last -= 1
				if last < 0:
					last = n - 1
			elif max(b, beg) <= z:
				print(max(b, beg))
			else:
				print(z)


(n, q, k) = map(int, input().split())
arr = list(map(int, input().split()))
query = list(input())
q_ = len(query)
c1 = query.count('?')
c = arr.count(0)
if c == n:
	for i in range(c1):
		print(0)
else:
	for i in range(q_):
		if i != 0 and (query[i] == '?' and query[i - 1] == '?'):
			print(max_c)
		elif query[i] == '?':
			max_c = cnt = 0
			for j in range(n):
				if j != n - 1 and (arr[j] == 1 and arr[j + 1] == 1):
					cnt += 1
				else:
					max_c = max(max_c, cnt + 1)
					cnt = 0
				if k < max_c:
					max_c = k
					break
			print(max_c)
		elif query[i] == '!':
			temp = arr[n - 1]
			del arr[n - 1]
			arr.insert(0, temp)


def calc(x, n):
	if len(x) < 2:
		return 0
	if x[1] >= x[0]:
		return x[1] - x[0] + 1
	else:
		return max(x[1] - 0 + 1, n - x[0])
(n, q, k) = (int(x) for x in input().split())
a = list(input().split())
queries = input()
if n <= 1000 or q <= 3000:
	maxlen = 0
	length = 0
	for i in queries:
		if i == '!':
			a.insert(0, a[-1])
			a.pop()
		if i == '?':
			maxlen = 0
			length = 0
			for x in a:
				if x == '1':
					length += 1
				if x == '0':
					if length > maxlen:
						maxlen = length if length < k else k
					length = 0
			if a[-1] != '0':
				if length > maxlen:
					maxlen = length if length < k else k
			print(maxlen)
else:
	segments = []
	start = -1
	j = 0
	maxlength = 0
	maxsegment = []
	secmax = 0
	secmaxsegment = []
	for i in a:
		if i == '1' and start == -1:
			start = j
		if i == '0' and j != 0 and (a[j - 1] == '1'):
			segments.append([start, j - 1])
			if j - start >= maxlength:
				secmax = maxlength
				secmaxsegment = maxsegment
				maxlength = j - start
				maxsegment = [start, j - 1]
			start = -1
		j += 1
	if a[-1] != '0':
		segments.append([start, n - 1])
		if n - start >= maxlength:
			secmax = maxlength
			secmaxsegment = maxsegment
			maxlength = n - start
			maxsegment = [start, n - 1]
	if len(secmaxsegment):
		for seg in segments:
			if seg[0] != maxsegment[0] and seg[1] != maxsegment[1]:
				if calc(seg, n) > secmax:
					secmax = calc(seg, n)
					secmaxsegment = seg
	fixed = 0
	if a[0] == '0' or a[-1] == '0':
		fixed = 1
	if len(segments):
		firstsegment = [segments[-1][0], segments[0][1]]
	for x in queries:
		if fixed:
			if x == '?':
				if len(maxsegment) and maxsegment[1] > maxsegment[0]:
					print(min(maxlength, k))
				else:
					print(min(max(calc(maxsegment, n), secmax), k))
			elif len(maxsegment):
				maxsegment[0] = (maxsegment[0] + 1) % n
				maxsegment[1] = (maxsegment[1] + 1) % n
		elif x == '?':
			print(min(max(calc(firstsegment, n), calc(secmaxsegment, n), calc(maxsegment, n)), k))
		else:
			if len(maxsegment):
				maxsegment[0] = (maxsegment[0] + 1) % n
				maxsegment[1] = (maxsegment[1] + 1) % n
			if len(firstsegment):
				firstsegment[0] = (firstsegment[0] + 1) % n
				firstsegment[1] = (firstsegment[1] + 1) % n
			if len(secmaxsegment):
				secmaxsegment[0] = (secmaxsegment[0] + 1) % n
				secmaxsegment[1] = (secmaxsegment[1] + 1) % n


w = input().split()
n = int(w[0])
q = int(w[1])
k = int(w[2])
a = [int(j) for j in input().split()]
s = input()
count = 0
prevmax = 0
maxcount = 0
var = 0
tempvar = 0
firstind = 0
lastind = 0
for x in range(n):
	if a[x] == 0:
		var = 1
		ind = x
		break
if var == 1:
	for x in range(ind, -n + ind - 1, -1):
		var2 = 1
		if a[x] == 1:
			count += 1
			if tempvar == 0:
				ind = x
				tempvar = 1
		else:
			if count > maxcount:
				prevmax = maxcount
				maxcount = count
				firstind = ind
				lastind = x + 1
				var2 = 0
			if count > prevmax and var2 == 1:
				prevmax = count
			count = 0
			tempvar = 0
	if lastind < 0:
		lastind += n
	if firstind < 0:
		firstind += n
	for x in s:
		if x == '!':
			firstind += 1
			if firstind == n:
				firstind = 0
			lastind += 1
			if lastind == n:
				lastind = 0
		else:
			if firstind >= lastind:
				ans = maxcount
			else:
				ans = max(prevmax, firstind + 1, n - lastind)
			if ans >= k:
				print(k)
			else:
				print(ans)
else:
	for x in s:
		if x == '?':
			ans = n
			if ans >= k:
				print(k)
			else:
				print(ans)


from sys import exit
(n, q, k) = map(int, input().split())
a = list(map(int, input().split()))
s = input()
if a.count(1) == n:
	for i in range(s.count('?')):
		print(min(k, n))
	exit()
cnt = dict()
S = set()

def upd(l, delta):
	if l in S:
		cnt[l] += delta
	if delta == 1 and l not in S:
		S.add(l)
		cnt[l] = delta
	if delta == -1 and cnt[l] == 0:
		S.remove(l)
l = 0
for i in a:
	if i == 1:
		l += 1
	else:
		upd(l, 1)
		l = 0
upd(l, 1)
(pre, suf, i) = (0, 0, 0)
while i < n and a[i] == 1:
	(pre, i) = (pre + 1, i + 1)
i = n - 1
while i >= 0 and a[i] == 1:
	(suf, i) = (suf + 1, i - 1)
(st, en) = (0, n - 1)
for t in s:
	if t == '!':
		if a[en] == 1:
			upd(pre, -1)
			pre += 1
			upd(pre, 1)
			upd(suf, -1)
			suf -= 1
			upd(suf, 1)
		else:
			(pre, suf, i) = (0, 0, (en - 1) % n)
			while i != st and a[i] == 1:
				(suf, i) = (suf + 1, (i - 1) % n)
		(st, en) = ((st - 1) % n, (en - 1) % n)
	else:
		ans = 0 if len(S) == 0 else max(S)
		print(min(k, ans))


def plus(i):
	if i < n - 1:
		return i + 1
	else:
		return 0
[n, q, k] = [int(j) for j in input().split()]
l = input().split()
querry = list(input())
if l == n * ['0']:
	for ko in range(q):
		if querry[ko] == '?':
			print(0)
else:
	m = [0]
	m2 = [(0, 0)]
	try:
		br = l.index('0')
		i = br + 1
		while i != br:
			if l[i] == '1':
				ct = 1
				pst = i
				i = plus(i)
				while l[i] == '1' and i != br:
					ct = ct + 1
					i = plus(i)
				m.append(ct)
				m2.append((pst, i - 1))
			else:
				i = plus(i)
	except:
		i = 0
		while i < n - 1:
			if l[i] == '1':
				ct = 1
				pst = i
				i = plus(i)
				while l[i] == '1' and i < n - 1:
					ct += 1
					i = plus(i)
				m.append(ct)
				m2.append((pst, i - 1))
			else:
				i = plus(i)
	max_len = max(m)
	w = m.index(max_len)
	st = m2[w][0]
	end = m2[w][1]
	m.remove(max_len)
	sec_max = max(m)
	for i in range(q):
		if querry[i] == '!':
			end = plus(end)
			st = plus(st)
		elif end - st + 1 == max_len:
			print(min(k, max_len))
		else:
			x = n - st
			y = end + 1
			z = max(sec_max, x, y)
			print(min(k, z))


(N, Q, K) = [int(s) for s in input().split(' ') if s != '']
A = [int(s) for s in input().split(' ') if s != '']
pref = [0] * N
suf = [0] * N
beg1 = [0] * N
end1 = [0] * N
ret = 0
cur = 0
stop = False
for i in range(0, N):
	if A[i] == 0:
		cur = 0
		stop = True
		if i > 0:
			beg1[i] = beg1[i - 1]
	else:
		cur += 1
		ret = max(ret, cur)
		if not stop:
			beg1[i] = cur
		else:
			beg1[i] = beg1[i - 1]
	pref[i] = ret
ret = 0
cur = 0
stop = False
for i in reversed(range(0, N)):
	if A[i] == 0:
		cur = 0
		stop = True
		if i < N - 1:
			end1[i] = end1[i + 1]
	else:
		cur += 1
		ret = max(ret, cur)
		if not stop:
			end1[i] = cur
		else:
			end1[i] = end1[i + 1]
	suf[i] = ret
beg = 0
for q in input():
	if q == '!':
		beg -= 1
		if beg < 0:
			beg = N - 1
	elif beg == 0:
		print(min(K, suf[beg]))
	else:
		a = max(suf[beg], pref[beg - 1], beg1[beg - 1] + end1[beg])
		print(min(K, a))


def ma(a, b, c):
	if a > b:
		if a > c:
			return a
		else:
			return c
	elif b > c:
		return b
	else:
		return c
from collections import deque
(n, q, k) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = list(input())
f = 0
fi = 0
si = 0
s = 0
count = 0
m = 0
c = [0 for i in range(n)]
if a[0] == 1:
	count = 1
for i in range(1, n):
	if a[i] == 1 and a[i - 1] == 1:
		count += 1
	elif a[i] == 1 and a[i - 1] == 0:
		count = 1
	else:
		count = 0
	if count > m:
		m = count
		fi = i
f = m
m = 0
count = 0
for i in range(fi - f + 1, fi + 1):
	c[i] = 1
if a[0] == 1 and c[0] == 0:
	count = 1
	si = 0
	m = 1
for i in range(1, n):
	if a[i] == 1 and a[i - 1] == 1 and (c[i] == 0):
		count += 1
	elif a[i] == 1 and a[i - 1] == 0 and (c[i] == 0):
		count = 1
	else:
		count = 0
	if count > m and count <= f:
		m = count
		si = i
s = m
fr = 0
de = deque(a)
for i in range(n):
	if a[i] == 1:
		fr += 1
	else:
		break
for i in range(q):
	if b[i] == '?':
		print(min(ma(fr, f, s), k))
	else:
		r = de.pop()
		if r == 1:
			fr += 1
			fi += 1
			si += 1
			if fr > n:
				fr = n
			if si == n:
				si = n - 1
				s += -1
			if fi == n:
				fi = n - 1
				f += -1
		else:
			if fr > f:
				fi = fr - 1
				f = fr
			elif fr > s:
				si = fr - 1
				s = fr
			fr = 0
			fi += 1
			si += 1
		de.appendleft(r)


t = [int(j) for j in input().split()]
g = input().split()
u = list(input())
if t[0] <= 1000:
	s = ''.join(g)
	for i in u:
		if i == '!':
			s = s[-1] + s[0:t[0] - 1]
		else:
			a = 0
			b = 0
			for u in range(t[0]):
				if int(s[u]) == 1:
					a += 1
				elif int(s[u]) == 0:
					if a >= b:
						b = a
						a = 0
					else:
						a = 0
			print(min(max(a, b), t[2]))
else:
	h = [int(u) for u in g]
	a = [0, 0]
	b = [0, 0]
	m1 = 0
	m2 = 0
	m3 = 0
	c1 = 0
	c2 = 0
	c3 = 0
	d1 = 0
	d2 = 0
	d3 = 0
	f = t[0] - 1
	mode = 0
	for i in range(t[0]):
		if h[i] == 0:
			break
		a[0] += 1
		a[1] = i
	if t[0] == 1:
		for y in range(t[1]):
			if u[y] == '?':
				print(h[0])
	elif t[0] == 2:
		for y in range(t[1]):
			if u[y] == '?':
				print(min(h.count(1), t[2]))
	elif a[1] + 1 == t[0]:
		for y in range(t[1]):
			if u[y] == '?':
				print(min(t[0], t[2]))
	else:
		for J in range(t[0]):
			j = t[0] - J - 1
			if h[j] == 0:
				break
			b[0] += 1
			b[1] = j
		if h[0] == 0:
			a = [0, -1]
		if h[t[0] - 1] == 0:
			b = [0, t[0]]
		m1 = int(a[1] + 2)
		for I in range(a[1] + 2, b[1]):
			if int(h[I]) == 0:
				m3 = I - 1
				if m2 > max(c2, d2) and h[m1] == 1 and (h[m3] == 1):
					c1 = m1
					c2 = m2
					c3 = m3
				elif m2 > min(c2, d2) and m2 != c2 and (h[m1] == 1) and (h[m3] == 1):
					d1 = m1
					d2 = m2
					d3 = m3
				m1 = I + 1
				m2 = 0
			elif int(h[I]) == 1:
				m2 += 1
		c = [c1, c2, c3]
		d = [d1, d2, d3]
		if c[1] < a[0] + b[0]:
			mode = 1
		elif d[1] < a[0] + b[0] and mode != 1:
			mode = 2
		for k in range(t[1]):
			if u[k] == '!':
				if f == 0:
					f = t[0] - 1
				else:
					f = f - 1
			elif u[k] == '?':
				if mode == 0:
					if f >= c[0] and f < c[2]:
						print(min(max(c[1] - (c[2] - f), c[2] - f, d[1]), t[2]))
					else:
						print(min(c[1], t[2]))
				if mode == 1:
					if f <= a[1]:
						print(min(max(b[0] + a[0] - (a[1] - f), a[1] - f, c[1]), t[2]))
					elif f >= b[1]:
						print(min(max(a[0] + b[0] - (f - b[1] + 1), f - b[1] + 1, c[1]), t[2]))
					else:
						print(min(a[0] + b[0], t[2]))
				if mode == 2:
					if f >= c[0] and f < c[2]:
						print(min(max(c[1] - (c[2] - f), c[2] - f, a[0] + b[0]), t[2]))
					else:
						print(min(c[1], t[2]))


def getMaxLength(arr):
	count = 0
	arr = np.append(arr, 0)
	ls = []
	for i in arr:
		if i == 0:
			if count != 0:
				ls.append(count)
			count = 0
		else:
			count += 1
	return ls
import numpy as np
lst = np.array([int(x) for x in input().split()])
k = int(lst[2])
val = np.array([int(x) for x in input().split()])
query = input()
n = len(val)
if np.array_equal(np.zeros_like(val), val):
	count = query.count('?')
	for i in range(1, count + 1):
		print(0)
else:
	ar1 = np.empty(n)
	ar1[::2] = 1
	ar1[1::2] = 0
	if np.array_equal(ar1, val):
		count = query.count('?')
		for i in range(1, count + 1):
			print(1)
	else:
		ar1[::2] = 0
		ar1[1::2] = 1
		if np.array_equal(ar1, val):
			count = query.count('?')
			for i in range(1, count + 1):
				print(1)
		else:
			start = val[0]
			end = val[n - 1]
			index_start = 0
			index_end = n - 1
			ls = getMaxLength(val)
			a = np.array(ls)
			maximum = np.argmax(a)
			maxi = a[maximum]
			siz = np.size(a)
			for i in query:
				if i == '!':
					start = val[index_start]
					end = val[index_end]
					index_start = index_start - 1
					index_end = index_end - 1
					if index_end < 0:
						index_end = n - 1
					if index_start < 0:
						index_start = n - 1
					if start == end:
						if start == 1:
							a[0] = a[0] + 1
							a[np.size(a) - 1] = a[np.size(a) - 1] - 1
							if a[np.size(a) - 1] == 0:
								a = np.delete(a, np.size(a) - 1)
							if maximum > siz - 2:
								maximum = np.argmax(a)
					elif end == 1:
						a = np.append([1], a)
						a[np.size(a) - 1] = a[np.size(a) - 1] - 1
						if a[np.size(a) - 1] == 0:
							a = np.delete(a, np.size(a) - 1)
						maximum = maximum + 1
						if maximum > siz - 2:
							maximum = np.argmax(a)
					if a[maximum] < a[0]:
						maximum = 0
					maxi = a[maximum]
				elif maxi > k:
					print(k)
				else:
					print(maxi)


def solve(segment, pointer):
	(length, left, right) = segment
	intersects = False
	(left_rim, right_rem) = (-1, -1)
	if left <= right:
		intersects = True if pointer >= left and pointer <= right else False
		if intersects == True:
			right_rem = right - pointer + 1
			left_rim = length - right_rem
	else:
		intersects = True if pointer >= left or pointer <= right else False
		if intersects == True:
			if pointer >= left:
				left_rim = pointer - left
				right_rem = length - left_rim
			else:
				right_rem = right - pointer + 1
				left_rim = length - right_rem
	return (intersects, left_rim, right_rem)
(total_lenght, m, k) = map(int, input().split())
arr = [int(x) for x in input().split()]
query = input()
(l, r) = (-1, -1)
dictionery = {}
for (index, e) in enumerate(arr):
	r = index
	if e == 1:
		if l in dictionery:
			dictionery[l] += 1
		else:
			dictionery[l] = 1
	else:
		l = index
if arr[0] == arr[-1] and arr[0] == 1:
	if len(dictionery) not in [0, 1]:
		dictionery[l] += dictionery[-1]
		del dictionery[-1]
remember = []
for key in dictionery:
	a = key + 1
	b = key + dictionery[key]
	remember.append((b - a + 1, a, b % total_lenght))
remember.sort(reverse=True)
if len(remember) == 0:
	for ch in query:
		if ch != '!':
			print(0)
else:
	ptr = 0
	for ch in query:
		if ch == '!':
			ptr -= 1
			if ptr == -1:
				ptr = total_lenght - 1
		elif ch == '?':
			(ans, a, b) = solve(remember[0], ptr)
			if ans == False:
				ans = remember[0][0]
			elif len(remember) > 1:
				ans = max([remember[1][0], a, b])
			else:
				ans = max(a, b)
			print(ans if ans <= k else k)


from sys import stdin
(n, q, k) = map(int, stdin.readline().split())
ays = list(map(int, stdin.readline().split()))
qs = stdin.readline().strip()
asum = sum(ays)
if asum == n or asum < 2 or k < 2:
	out = [min(asum, k)] * qs.count('?')
else:
	out = []
	run = []
	last = 0
	for (ix, a) in enumerate(ays):
		if a == 1:
			if last == 0:
				run.append([1, ix])
			else:
				run[-1][0] += 1
		last = a
	mark = 0
	if last == 1 and ays[0] == 1:
		(mark, _) = run.pop()
		run[0][0] += mark
	run.sort(reverse=True)
	(main, st) = run[0]
	if st > 0:
		mark = 0
	en = st + main
	if len(run) > 1:
		spare = run[1][0]
	else:
		spare = 0
	mk = min(main, k)
	if spare >= k or main >= 2 * k or main == spare:
		out = [mk] * qs.count('?')
	else:
		ans = [mk] * n
		st += main - mk
		en -= main - mk
		while st < en - 1:
			mk -= mk > spare
			st += 1
			en -= 1
			ans[st] = mk
			ans[en] = mk
		for c in qs:
			if c == '!':
				mark -= 1
				if mark < 0:
					mark += n
			else:
				out.append(ans[mark])
print('\n'.join(map(str, out)))


(n, q, k) = [int(x) for x in list(input().split())]
seq = [x for x in list(input().split())]
string = list(input())
seq += seq

def findMax():
	arr = []
	if '1' not in seq:
		return [[], [], [], [], []]
	if '0' in seq:
		end = n
		if seq[0] == '1' and seq[n - 1] == '1':
			end = n + seq.index('0') + 1
		c = 0
		a = []
		for i in range(0, end):
			if seq[i] == '1':
				if c == 0:
					a.append(i)
				c += 1
			else:
				if c > 0:
					a.append(i)
					arr.append(a)
					a = []
				c = 0
		if seq[end - 1] == '1':
			a.append(n)
			arr.append(a)
		arr = sorted(arr, key=lambda x: x[1] - x[0])
		while len(arr) > 2:
			arr.pop(0)
		return arr
	else:
		return [[], [], [], [], [], []]

def getLen(a, b):
	x = a[0] if a[0] > b[0] else b[0]
	y = a[1] if a[1] < b[1] else b[1]
	return y - x

def finder(ind):
	l = len(lengths)
	if l > 0 and l < 3:
		result = 0
		for val in lengths:
			temp1 = getLen([val[0], val[1]], [ind, ind + n])
			temp2 = getLen([val[0] + n, val[1] + n], [ind, ind + n])
			result = max(result, max(temp1, temp2))
		print(min(result, k))
	elif l == 5:
		print(0)
	elif l == 6:
		print(min(n, k))
lengths = findMax()
counter = 0
for s in string:
	if s == '!':
		counter += 1
		if counter >= n:
			counter -= n
	else:
		finder(n - counter)


(n, q, k) = map(int, input().split())
l = list(map(int, input().split()))
s = str(input())
a = []
b = []
c = []
f = 0
for i in range(n):
	if l[i] == 1:
		if f == 0:
			a.append(i + 1)
		if i == n - 1:
			b.append(i + 1)
		f += 1
	else:
		if f > 0:
			b.append(i)
		f = 0
f = len(a)
for i in range(f):
	c.append(b[i] - a[i] + 1)
l1 = []
l2 = []
l3 = []
if len(a) > 0:
	if a[0] == 1:
		l1.append(a[0])
		l2.append(b[0])
		l3.append(c[0])
		a.remove(a[0])
		b.remove(b[0])
		c.remove(c[0])
for i in range(2):
	if len(c) > 0:
		t = c.index(max(c))
		l1.append(a[t])
		l2.append(b[t])
		l3.append(c[t])
		a.remove(a[t])
		b.remove(b[t])
		c.remove(c[t])
a = []
b = []
c = []
for i in range(len(l1)):
	t = l1.index(min(l1))
	a.append(l1[t])
	b.append(l2[t])
	c.append(l3[t])
	l1.remove(l1[t])
	l2.remove(l2[t])
	l3.remove(l3[t])
d = {}
co = 0
if len(c) != 0:
	d[0] = k if max(c) > k else max(c)
else:
	d[0] = 0
if d[0] == 0:
	for i in range(q):
		if s[i] == '?':
			print('0')
	exit()
for i in range(q):
	if s[i] == '!':
		co += 1
		if co % n not in d:
			f = len(a)
			for i in range(f):
				a[i] += 1
				b[i] += 1
			if b[f - 1] == n + 1:
				if a[0] == 2:
					a[0] -= 1
					c[0] += 1
				else:
					a.insert(0, 1)
					f += 1
					c.insert(0, 1)
					b.insert(0, 1)
				if a[f - 1] == n + 1:
					a.pop()
					b.pop()
					c.pop()
				else:
					b[f - 1] -= 1
					c[f - 1] -= 1
			d[co] = k if max(c) > k else max(c)
	else:
		print(d[co % n])


(n, q, k) = map(int, input().split())
a = list(map(int, input().split()))
s = input()
ar = []
i = 0
while i < n:
	if a[i] == 0:
		ar.append(0)
		i += 1
	elif a[i] == 1:
		co = 0
		while i < len(a) and a[i] == 1:
			co += 1
			i += 1
		ar.append(co)
ans = [0] * n
c = [0] * 1000021
for i in range(len(ar)):
	if ar[i] != 0:
		c[ar[i]] += 1
ans[0] = max(ar)
ma = ans[0]
nn = len(ar)
for i in range(1, n):
	if ar[nn - 1] == 0:
		ar.pop(nn - 1)
		ar.insert(0, 0)
		ans[i] = ma
	elif ar[nn - 1] > 0:
		if ar[nn - 1] > 1:
			if ar[0] == 0:
				x = ar[nn - 1]
				c[x] -= 1
				c[x - 1] += 1
				c[1] += 1
				ar[nn - 1] -= 1
				nn += 1
				ar.insert(0, 1)
			elif ar[0] > 0:
				x = ar[nn - 1]
				y = ar[0]
				c[x] -= 1
				c[y] -= 1
				c[x - 1] += 1
				c[y + 1] += 1
				ar[nn - 1] -= 1
				ar[0] += 1
		elif ar[nn - 1] == 1:
			if ar[0] == 0:
				ar.pop()
				ar.insert(0, 1)
			elif ar[0] > 0:
				x = ar[0]
				c[x] -= 1
				c[x + 1] += 1
				c[1] -= 1
				ar.pop()
				ar[0] += 1
				nn -= 1
		if c[ma + 1] > 0:
			ma = ma + 1
		elif c[ma] > 0:
			ma = ma
		elif c[ma - 1] > 0:
			ma = ma - 1
		ans[i] = ma
co = 0
if len(ar) == 1:
	for i in range(q):
		if s[i] == '?':
			print(min(k, ar[0]))
else:
	for i in range(q):
		if s[i] == '!':
			co += 1
		elif s[i] == '?':
			print(min(k, ans[co % n]))


from collections import deque as dq
(n, q, k) = map(int, input().split())
chandu = list(map(str, input().split()))
n = len(chandu)
x = ''.join(chandu)
gandi = list((len(a) for a in x.split('0')))
chlhat = []
chlhat2 = []
chlhat2.extend(gandi)
chlhat.extend(gandi)
chlhat.sort(reverse=True)
nazar = chlhat[0]
chab = nazar
if len(chlhat) > 1:
	chab = chlhat[1]
chlhat2.reverse()
kabir1 = len(chlhat2) - chlhat2.index(nazar) - 1
ihate = dq(gandi)
aruna = dq(chandu)
dipankar = list(input())
srk = dict()
choprs = 0
srk[0] = min(k, nazar)
for i in range(len(dipankar)):
	if dipankar[i] == '!':
		aruna.rotate(1)
		choprs += 1
		if aruna[0] == '1':
			ihate[0] += 1
			ihate[len(ihate) - 1] -= 1
			if kabir1 == len(ihate) - 1:
				nazar -= 1
		if ihate[len(ihate) - 1] == 0:
			ihate.rotate(1)
			kabir1 = (kabir1 + 1) % len(ihate)
			if kabir1 == 0:
				kabir1 += 1
			nazar = ihate[kabir1]
		if choprs % n not in srk:
			if n <= 10 ** 3:
				chlhatsrk = max(ihate)
			else:
				chlhatsrk = max(nazar, chab, ihate[0])
			x = min(k, chlhatsrk)
			srk[choprs % n] = x
	else:
		print(srk[choprs % n])


(n, q, k) = map(int, input().split())
arr = list(map(int, input().split()))
queR = input()
temp = 0
sol = []
for i in range(n):
	if arr[i] == 1 and temp == 0:
		sol.append([i, 1])
		temp = 1
	elif arr[i] == 1:
		sol[-1][1] += 1
	else:
		temp = 0
if arr[0] == 1 and arr[-1] == 1 and (len(sol) > 1):
	sol[-1][1] += sol[0][1]
	sol.pop(0)
sol = sorted(sol, key=lambda x: x[1])
if sol:
	p = sol[-1][1]
	c = sol[-1][0]
	v = None
else:
	p = 0
	c = 0
	v = None
if len(sol) > 1:
	v = sol[-2][1]
bi = 0
for i in range(q):
	if queR[i] == '?':
		if (c + bi) % n + p - 1 > n - 1:
			e = n - (c + bi) % n
			r = p - e
			if v:
				print(min(k, max(v, e, r)))
			else:
				print(min(k, max(e, r)))
		else:
			print(min(k, p))
	else:
		bi += 1


import sys
(n, q, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
zeroflag = 0
oneflag = 0
if sum(a) == 0:
	zeroflag = 1
if sum(a) == n:
	oneflag = 1
if zeroflag == 1:
	queries = input()
	for i in queries:
		if i == '?':
			print(0)
	sys.exit()
if oneflag == 1:
	queries = input()
	for i in queries:
		if i == '?':
			print(min(n, k))
	sys.exit()
largest = {}
s = 0
smax = 0
f = 0
for i in range(n):
	if a[i] != 0:
		if f == 0:
			start = i
			f = 1
		s += 1
	else:
		f = 0
		if s > smax:
			smax = s
			largest['start'] = start
			largest['end'] = start + s - 1
		s = 0
if s > smax:
	smax = s
	largest['start'] = start
	largest['end'] = start + s - 1
slargest = {}
s = 0
smax = 0
f = 0
for i in range(n):
	if i < largest['start'] or i > largest['end']:
		if a[i] != 0:
			if f == 0:
				start = i
				f = 1
			s += 1
		else:
			f = 0
			if s > smax:
				smax = s
				slargest['start'] = start
				slargest['end'] = start + s - 1
			s = 0
if s > smax:
	smax = s
	slargest['start'] = start
	slargest['end'] = start + s - 1
firstlen = a.index(0)
first = {}
first['start'] = 0
first['end'] = max(0, firstlen - 1)
lastlen = a[::-1].index(0)
last = {}
last['end'] = n - 1
last['start'] = n - lastlen
if firstlen + lastlen >= largest['end'] - largest['start'] + 1 and firstlen > 0 and (lastlen > 0):
	slargest['start'] = largest['start']
	slargest['end'] = largest['end']
	largest['start'] = last['start']
	largest['end'] = first['end']
elif firstlen + lastlen > slargest['end'] - slargest['start'] + 1 and firstlen > 0 and (lastlen > 0):
	slargest['start'] = last['start']
	slargest['end'] = first['end']

def fn_ls(start, end):
	f = 0
	if start > n - 1:
		start -= n
	if end > n - 1:
		end -= n
	if start > end:
		f = 1
	return (start, end, f)

def longest_subsequence(c):
	lstart = largest['start']
	lend = largest['end']
	slstart = slargest['start']
	slend = slargest['end']
	lstart += c
	lend += c
	slstart += c
	slend += c
	(slstart, slend, fsl) = fn_ls(slstart, slend)
	(lstart, lend, fl) = fn_ls(lstart, lend)
	if fsl == 1:
		v1 = max(n - slstart, slend + 1)
	else:
		v1 = slend - slstart + 1
	if fl == 1:
		v2 = max(n - lstart, lend + 1)
	else:
		v2 = lend - lstart + 1
	return min(max(v1, v2), k)
queries = input()
c = 0
for i in queries:
	if i == '?':
		print(longest_subsequence(c))
	else:
		c += 1
		c = c % n


(n, q, k) = map(int, input().split())
a = list(map(int, input().split()))
q = list(input())
if a.count(1) > 0:
	flag = 0
	c = 0
	b = []
	for i in range(n):
		if a[i] == 1:
			c += 1
			flag = 1
		elif flag == 1:
			b.append(c)
			c = 0
			flag = 0
	if flag == 1:
		b.append(c)
	flag = a[0]
	v = [min(max(b), k)]
	for i in range(n - 1):
		temp = a[(n - i - 1) % n]
		if temp == 0:
			flag = 0
			v.append(v[-1])
		else:
			b[-1] -= 1
			if flag == 1:
				b[0] += 1
			else:
				b.insert(0, 1)
			if b[-1] + 1 == v[-1]:
				v.append(min(max(b), k))
			elif b[0] > v[-1]:
				v.append(min(b[0], k))
			else:
				v.append(v[-1])
			if b[-1] == 0:
				del b[-1]
			flag = 1
	j = 0
	for i in q:
		if i == '?':
			print(v[j])
		else:
			j = (j + 1) % n
else:
	for i in q:
		if i == '?':
			print(0)


(n, q, k) = map(int, input().strip().split())
li = [int(x) for x in input().strip().split()]
s = (-1, -1)
m = (-1, -1)
l = (-1, -1)
e = (-1, -1)
f = 0
b = -1
for (i, x) in enumerate(li):
	if x == 1 and f == 0:
		b = i
		f = 1
	if x == 0 and f == 1 or i == n - 1:
		if x == 1:
			y = i
		else:
			y = i - 1
		if b == 0:
			s = (b, y)
		if i == n - 1:
			e = (b, y)
		if l[0] == -1:
			l = (b, y)
		elif l[1] - l[0] < y - b:
			m = l
			l = (b, y)
		elif m[1] - m[0] < y - b:
			m = (b, y)
		f = 0

def comp(a, b):
	if a[0] < b[0]:
		return True
	return False

def cmp_to_key(mycmp):

	class K:

		def __init__(self, obj, *args):
			self.obj = obj

		def __lt__(self, other):
			return mycmp(self.obj, other.obj)
	return K
quer = str(input())
f = 0
for x in quer:
	if x == '!':
		f += 1
	else:
		ti = []
		if s[0] != -1:
			t0 = s[0] + f
			t1 = s[1] + f
			while t0 > n - 1:
				t0 = t0 - n
			while t1 > n - 1:
				t1 = t1 - n
			s = (t0, t1)
		if e[0] != -1:
			t0 = e[0] + f
			t1 = e[1] + f
			while t0 > n - 1:
				t0 = t0 - n
			while t1 > n - 1:
				t1 = t1 - n
			e = (t0, t1)
		if m[0] != -1:
			t0 = m[0] + f
			t1 = m[1] + f
			while t0 > n - 1:
				t0 = t0 - n
			while t1 > n - 1:
				t1 = t1 - n
			m = (t0, t1)
		if l[0] != -1:
			t0 = l[0] + f
			t1 = l[1] + f
			while t0 > n - 1:
				t0 = t0 - n
			while t1 > n - 1:
				t1 = t1 - n
			l = (t0, t1)
		ti = [y for y in list(set([s, e, m, l])) if y[0] != -1]
		ti.sort(key=cmp_to_key(comp))
		start = 0
		first = 0
		v1 = 0
		f = 0
		p = 0
		v = 0
		for (i, x) in enumerate(ti):
			if i == 0:
				start = x[0] - 1
				first = x[1] - x[0] + 1
			if i == len(ti) - 1 and start == x[1]:
				v1 = first + start + 1
			if ti[i - 1][1] + 1 == x[0] and i != 0:
				if x[1] >= x[0]:
					f += x[1] - x[0] + 1
					v = max(v, f)
				else:
					f += n - x[0]
					v = max(max(v, f), x[1] + 1)
			elif x[1] >= x[0]:
				v = max(v, x[1] - x[0] + 1)
				f = x[1] - x[0] + 1
			else:
				v = max(v, max(n - x[0], x[1] + 1))
				f = x[1] + 1
		print(min(k, max(v, v1)))
		f = 0


(n, q, k) = map(int, input().strip().split(' '))
list1 = list(map(int, input().strip().split(' ')))
str1 = str(input())
start = 0
count = 0
count = 0
arr = []
list2 = []
for x in range(n):
	if list1[x] == 1:
		if count == 0:
			start = x
			count = 1
		if x == n - 1:
			list2 = list2 + [start, n]
	elif count == 1:
		end = x - 1
		count = 0
		arr.append([start, end])
for x in arr:
	z = x[1] - x[0] + 1
	x.append(z)
list3 = sorted(arr, key=lambda x: x[2], reverse=True)
for x in list3:
	if len(list2) <= 5:
		if x[0] not in list2:
			list2.append(x[0])
			list2.append(x[1] + 1)
list2 = sorted(list2)
for r in str1:
	if r == '!':
		if len(list2) > 0:
			list2 = [x + 1 for x in list2]
			if list2[-1] > n:
				list2.insert(0, 1)
				list2.insert(0, 0)
				list2[-1] = list2[-1] - 1
			list4 = [list2[0]]
			for z in range(1, len(list2)):
				if list4[-1] != list2[z]:
					list4.append(list2[z])
				else:
					list4.pop()
			list2 = list4
	else:
		count = 0
		x = 0
		while x < len(list2):
			count = max(count, list2[x + 1] - list2[x])
			x = x + 2
		if count > k:
			print(k)
		else:
			print(count)


from collections import deque as deq

def makeString(arr):
	a = ''.join(arr)
	return a

def findSequences(s):
	l = list((len(x) for x in s.split('0')))
	return l

def adjust(x, k):
	if x >= k:
		return k
	else:
		return x

def main():
	(n, q, k) = [int(x) for x in input().strip().split()]
	arr = [str(x) for x in input().strip().split()]
	queryString = list(str(input()))
	arrString = makeString(arr)
	seq = findSequences(arrString)
	seq1 = seq[:]
	seq1.sort(reverse=True)
	seq2 = seq[:]
	(max1, max2) = (seq1[0], seq1[0])
	if len(seq) > 1:
		max2 = seq1[1]
	seq2 = seq2[::-1]
	table = {}
	state = 0
	ind1 = len(seq2) - seq2.index(max1) - 1
	items = deq(arr)
	itemLens = deq(seq)
	l = len(itemLens)
	table[0] = adjust(max1, k)
	maxUpdates = min(n, queryString.count('!'))
	while maxUpdates > 0:
		maxUpdates -= 1
		state = state + 1
		items.rotate()
		if items[0] == '1':
			itemLens[0] += 1
			itemLens[l - 1] -= 1
			if ind1 == l - 1:
				max1 -= 1
		if itemLens[l - 1] == 0:
			itemLens.rotate()
			ind1 += 1
			ind1 = ind1 % l
			if ind1 == 0:
				ind1 = 1
			max1 = itemLens[ind1]
		if not state % n in table:
			if n <= 1000:
				table[state % n] = adjust(max(itemLens), k)
			else:
				table[state % n] = adjust(max(max1, max2, itemLens[0]), k)
	state = 0
	for quer in queryString:
		if quer == '!':
			state = (state + 1) % n
		elif quer == '?':
			print(adjust(table[state], k))
main()


def find_sequences_indexes_lengths(n, values):
	index = 0
	start_index = -1
	indexes_lengths = []
	for value in values:
		if value == '1':
			if start_index == -1:
				start_index = index
		elif start_index != -1:
			indexes_lengths.append((start_index, index, index - start_index))
			start_index = -1
		index += 1
	if start_index != -1:
		indexes_lengths.append((start_index, index, index - start_index))
	return indexes_lengths

def find_two_longest_sequences(n, values, sequences):
	if len(sequences) == 0:
		return []
	if len(sequences) > 1 and values[0] == '1' and (values[-1] == '1'):
		start_seq = sequences[0]
		end_seq = sequences[-1]
		new_seq = ((n - end_seq[0]) * -1, start_seq[1], end_seq[2] + start_seq[2])
		sequences = [new_seq] + sequences[1:-1]
	sequences_sorted = sorted(sequences, key=lambda x: x[2], reverse=True)
	if len(sequences_sorted) > 1:
		return [sequences_sorted[0], sequences_sorted[1]]
	return [sequences_sorted[0]]

def rotate_sequences(n, sequences, rotate):
	if rotate == 0 or len(sequences) == 0:
		return sequences
	for index in range(len(sequences)):
		(start, end, length) = sequences[index]
		start += rotate
		end += rotate
		if end > n:
			end = end - n
			start = start - n
		sequences[index] = (start, end, length)
	return sequences

def get_sequence_max_length(seq):
	if seq[0] < 0:
		return max(abs(seq[0]), seq[2] + seq[0])
	return seq[2]

def get_longest_length(sequences):
	if len(sequences) == 0:
		return 0
	if len(sequences) == 1:
		return get_sequence_max_length(sequences[0])
	seq1 = sequences[0]
	seq2 = sequences[1]
	return max(get_sequence_max_length(seq1), get_sequence_max_length(seq2))
(n, q, k) = map(int, input().split(' '))
values = input().split(' ')
queries = input()
nb_rotations = 0
(start_index, length) = (None, None)
sequences = find_sequences_indexes_lengths(n, values)
longest_sub_sequences = find_two_longest_sequences(n, values, sequences)
for index in range(q):
	query = queries[index]
	if query == '?':
		nb_rotations = nb_rotations % n
		longest_sub_sequences = rotate_sequences(n, longest_sub_sequences, nb_rotations)
		print(min(k, get_longest_length(longest_sub_sequences)))
		nb_rotations = 0
	elif query == '!':
		nb_rotations += 1


def max1(count, b, c):
	a = 0
	for i in range(c):
		if b[i] == 1:
			if a < count[i]:
				a = count[i]
	return a
(n, q, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
s = input()
b = [a[0]]
count = [1]
c = 1
for i in range(1, n):
	if a[i] == b[c - 1]:
		count[c - 1] += 1
	else:
		b.append(a[i])
		count.append(1)
		c = c + 1
l = max1(count, b, c)
check = 0
for i in range(q):
	if s[i] == '?':
		if l < k and check == 1:
			l = max1(count, b, c)
			check = 0
			print(l)
		elif l < k:
			print(l)
		else:
			print(k)
	else:
		if l == count[c - 1] and b[c - 1] == 1:
			l = l - 1
			check = 1
		if count[c - 1] == 1:
			item = b.pop()
			count.pop()
			c = c - 1
		else:
			count[c - 1] -= 1
			item = b[c - 1]
		if item == b[0]:
			count[0] += 1
		else:
			b.insert(0, item)
			count.insert(0, 1)
			c = c + 1
		if l < count[0] and b[0] == 1:
			l = count[0]