Read problems statements in Mandarin Chinese  and Russian. 

You are given a string S of length N consisting only of 0s and 1s. You are also given an integer K.

You have to answer Q queries. In the i^{th} query, two integers L_{i} and R_{i} are given. Then you should print the number of substrings of S[L, R] which contain at most K 0s and at most K 1s where S[L, R] denotes the substring from L^{th} to R^{th} characters of the string S. 
In other words, you have to count number of pairs (i, j) of integers such that L ≤ i ≤ j ≤ R such that no character in substring S[i, j] occurs more than K times.

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

The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow.
The first line of each test case contains three space-separated integers N, K and Q as described in the problem. The second line contains a string S of length N. Then the next Q lines describe the query, where the i^{th} line of them contains two space-separated integers L_{i} and R_{i}.

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

For each query, print the required answer in a single line.

------ 
------ Constraints -----
$1 ≤ T ≤ 10^{5}$
$1 ≤ K ≤ N ≤ 10^{5}$
$1 ≤ Q ≤ 10^{5}$
$1 ≤ L_{i} ≤ R_{i} ≤ N$
$Sum of N over all test cases in one test file does not exceed 10^{5}$
$Sum of Q over all test cases in one test file does not exceed 10^{5}$
$S consists only of 0s and 1s.$
Subtask 1: 10 points
$Sum of N over all test cases in one test file does not exceed 100$
Subtask 2: 10 points
$Q = 1$
$1 ≤ K ≤ min(5, N)$
Subtask 3: 20 points
$1 ≤ Q ≤ 10$
Subtask 4: 60 points
$Original constraints.$

----- Sample Input 1 ------ 
1
8 2 3
01110000
1 4
2 4
5 8
----- Sample Output 1 ------ 
8
5
7
----- explanation 1 ------ 
Query 1: Consider substring P = S[1, 4] = "0111".Out of 10 total substrings of P, substrings P[1, 4] and P[2, 4] are not valid because both contain more than two 1s. Other substrings contains at most two 0s and at most two 1s, thus the answer is 8.

Query 2: Consider substring P = S[2, 4] = "111".Out of 6 total substrings of P, substrings P[1, 3] is  not valid because it contains more than two 1s.

Query 3: Consider substring P = S[5, 8] = "0000".Out of 10 total substrings of P, substrings P[1, 3], P[1, 4] and P[2, 4] are not valid because all contain more than two 0s.

Source: codechef | Difficulty: HARD
Tags: String algorithms

Sorting

Preprocessing

Range queries

Complete search

Segment trees revisited

Dynamic programming

Data structures


Solutions:
cases = int(input())
for _ in range(cases):
	(n, k, q) = list(map(int, input().split()))
	s = input().strip()
	far = [0] * n
	sumfar = [0] * (n + 1)
	count0 = count1 = 0
	j = -1
	for i in range(n):
		while j < n and count0 <= k and (count1 <= k):
			j += 1
			if j == n:
				break
			if s[j] == '0':
				count0 += 1
			else:
				count1 += 1
		far[i] = j
		if s[i] == '0':
			count0 -= 1
		else:
			count1 -= 1
	for i in range(1, n + 1):
		sumfar[i] = sumfar[i - 1] + far[i - 1]
	for i in range(q):
		(l, r) = tuple(map(int, input().split()))
		l -= 1
		r -= 1
		(lo, hi) = (l, r)
		while lo < hi:
			mid = (lo + hi) // 2
			if far[mid] <= r:
				lo = mid + 1
			else:
				hi = mid
		k = lo - 1
		ans = sumfar[k + 1] - sumfar[l] + (r + 1) * (r - k) - (r * (r + 1) // 2 - l * (l - 1) // 2)
		print(ans)


def precompute(strr, n, k, far, sumfar):
	count = count0 = 0
	if strr[1] == '1':
		count += 1
	else:
		count0 += 1
	j = 1
	for i in range(1, n):
		while j < n and count <= k and (count0 <= k):
			j += 1
			if j >= n:
				break
			if strr[j] == '1':
				count += 1
			else:
				count0 += 1
		far[i] = j
		if strr[i] == '1':
			count -= 1
		else:
			count0 -= 1
	sumfar[1] = far[1]
	for i in range(2, n):
		sumfar[i] = sumfar[i - 1] + far[i]

def answerQ(strr, l, r, far, sumfar):
	answer = 0
	kl = l - 1
	kr = r + 1
	while kr - kl > 1:
		km = (kl + kr) // 2
		if far[km] <= r:
			kl = km
		else:
			kr = km
	k = kl
	answer = sumfar[k] - sumfar[l - 1] + (r - k) * (r + 1) - (r * (r + 1) // 2 - l * (l - 1) // 2)
	return answer
for _ in range(int(input())):
	(n, k, q) = list(map(int, input().split()))
	strr = input()
	strr = '2' + strr
	n = len(strr)
	far = [0] * n
	sumfar = [0] * n
	precompute(strr, n, k, far, sumfar)
	for _ in range(q):
		(l, r) = list(map(int, input().split()))
		print(answerQ(strr, l, r, far, sumfar))


def pre(N, S, K):
	j = 1
	count1 = count0 = 0
	if int(S[j - 1]) == 1:
		count1 += 1
	else:
		count0 = 1
	for i in range(1, N + 1):
		while j <= N and count1 <= K and (count0 <= K):
			j += 1
			if j > N:
				break
			if int(S[j - 1]) == 1:
				count1 += 1
			else:
				count0 += 1
		far[i] = j
		sumfar[i] = sumfar[i - 1] + far[i]
		if int(S[i - 1]) == 1:
			count1 -= 1
		else:
			count0 -= 1

def query(S, L, R):
	k1 = L - 1
	k2 = R + 1
	p = 17
	while p != 0:
		km = (k1 + k2) // 2
		if far[km] <= R:
			k1 = km
		else:
			k2 = km
		p -= 1
	k = k1
	answer = sumfar[k] - sumfar[L - 1] + (R - k) * (R + 1) - (R * (R + 1) // 2 - L * (L - 1) // 2)
	return answer
T = int(input(''))
while T != 0:
	T -= 1
	A = input(' ').split()
	N = int(A[0])
	K = int(A[1])
	Q = int(A[2])
	S = input(' ')
	far = [0] * (N + 1)
	sumfar = [0] * (N + 1)
	pre(N, S, K)
	for i in range(0, Q):
		B = input(' ').split()
		L = int(B[0])
		R = int(B[1])
		print(query(S, L, R))


def precompute(s, n, k, far, sumfar):
	(j, count0, count1) = (1, 0, 0)
	if s[0] == '0':
		count0 += 1
	else:
		count1 += 1
	for i in range(1, n + 1):
		while j <= n and count0 <= k and (count1 <= k):
			j += 1
			if j > n:
				break
			if s[j - 1] == '1':
				count1 += 1
			else:
				count0 += 1
		far[i] = j
		if s[i - 1] == '0':
			count0 -= 1
		else:
			count1 -= 1
	for i in range(1, n + 1):
		sumfar[i] = sumfar[i - 1] + far[i]

def answer_query(l, r):
	k1 = l - 1
	k2 = r + 1
	while k2 - k1 > 1:
		km = (k1 + k2) // 2
		if far[km] <= r:
			k1 = km
		else:
			k2 = km
	k = k1
	answer = sumfar[k] - sumfar[l - 1] + (r - k) * (r + 1) - (r * (r + 1) // 2 - l * (l - 1) // 2)
	return answer
for _ in range(int(input().strip())):
	(n, k, q) = map(int, input().strip().split())
	string = input().strip()
	far = [0 for i in range(n + 1)]
	sumfar = [0 for i in range(n + 1)]
	precompute(string, n, k, far, sumfar)
	for idx in range(q):
		(l, r) = map(int, input().strip().split())
		ans = answer_query(l, r)
		print(ans)


from _bisect import *

def search1(l, r, zeroes, ones, k):
	lo = l
	hi = r
	while lo < hi:
		mid = lo + (hi - lo) // 2
		z = zeroes[mid]
		o = ones[mid]
		if r + 1 < len(zeroes):
			z -= zeroes[r + 1]
			o -= ones[r + 1]
		if z <= k and o <= k:
			hi = mid
		else:
			lo = mid + 1
	return r - lo + 1

def search2(l, r, zeroes, ones, k):
	lo = l
	hi = r
	while lo <= hi:
		mid = lo + (hi - lo) // 2
		z = zeroes[mid]
		o = ones[mid]
		if l > 0:
			z -= zeroes[l - 1]
			o -= ones[l - 1]
		if z <= k and o <= k:
			lo = mid + 1
		else:
			hi = mid - 1
	return lo - 1

def search3(r, a, key):
	if r < 0:
		return 0
	lo = 0
	hi = r
	while lo <= hi:
		mid = lo + (hi - lo) // 2
		if key >= a[mid]:
			lo = mid + 1
		else:
			hi = mid - 1
	return lo
for T in range(int(input())):
	(n, k, q) = map(int, input().split())
	s = str(input())
	zeroesEnd = [0 for x in range(n)]
	onesEnd = [0 for x in range(n)]
	if s[n - 1] == '1':
		zeroesEnd[n - 1] = 0
		onesEnd[n - 1] = 1
	else:
		zeroesEnd[n - 1] = 1
		onesEnd[n - 1] = 0
	for i in range(n - 2, -1, -1):
		z = zeroesEnd[i + 1]
		o = onesEnd[i + 1]
		if s[i] == '1':
			o += 1
		else:
			z += 1
		zeroesEnd[i] = z
		onesEnd[i] = o
	zeroesStart = []
	onesStart = []
	if s[0] == '1':
		zeroesStart.append(0)
		onesStart.append(1)
	else:
		zeroesStart.append(1)
		onesStart.append(0)
	for i in range(1, n):
		z = zeroesStart[i - 1]
		o = onesStart[i - 1]
		if s[i] == '1':
			o += 1
		else:
			z += 1
		zeroesStart.append(z)
		onesStart.append(o)
	contributionForIEndingAtI = [0 for x in range(n)]
	contributionForIStartingAtI = [0 for x in range(n)]
	contributionForIStartingAtI[n - 1] = n - 1
	contributionForIEndingAtI[0] = 1
	for i in range(1, n):
		contributionForIEndingAtI[i] = contributionForIEndingAtI[i - 1] + search1(0, i, zeroesEnd, onesEnd, k)
	for i in range(n - 2, -1, -1):
		contributionForIStartingAtI[i] = search2(i, n - 1, zeroesStart, onesStart, k)
	prefix = []
	prefix.append(contributionForIStartingAtI[0] - i + 1)
	for i in range(1, n):
		prefix.append(prefix[i - 1] + contributionForIStartingAtI[i] - i + 1)
	for Q in range(q):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		sum = 0
		k = search3(l - 1, contributionForIStartingAtI, r) - 1
		if k > -1:
			sum += prefix[k]
		if k + 1 <= l - 1 and l != 0:
			x = (l - k - 1) * r + l - k - 1
			y = (l - 1) * l // 2
			if k != -1:
				y -= k * (k + 1) // 2
			x -= y
			sum += x
		print(contributionForIEndingAtI[r] - sum)


def answer_query(L, R, far, sofar):
	k1 = L - 1
	k2 = R + 1
	while k2 - k1 > 1:
		km = (k1 + k2) // 2
		if far[km] <= R:
			k1 = km
		else:
			k2 = km
	k = k1
	print(sofar[k] - sofar[L - 1] + (R - k) * (R + 1) - (R * (R + 1) // 2 - L * (L - 1) // 2))
for t in range(int(input())):
	ip = list(map(int, input().split()))
	n = ip[0]
	k = ip[1]
	q = ip[2]
	lp = []
	s = '0' + input()
	c1 = 0
	c0 = 0
	b = 1
	if s[1] == '1':
		c1 += 1
	else:
		c0 += 1
	far = [0 for j in range(n + 1)]
	sofar = [0 for k in range(n + 1)]
	for a in range(1, n + 1):
		while b <= n and c0 <= k and (c1 <= k):
			b += 1
			if b > n:
				break
			if s[b] == '1':
				c1 += 1
			else:
				c0 += 1
		far[a] = b
		if s[a] == '1':
			c1 -= 1
		else:
			c0 -= 1
	for a in range(1, n + 1):
		sofar[a] = sofar[a - 1] + far[a]
	for i in range(q):
		lp.append(list(map(int, input().split())))
		answer_query(lp[i][0], lp[i][1], far, sofar)


for _ in range(int(input())):
	(n, k, q) = map(int, input().split())
	string = input()
	n_z = [0] * n
	n_o = [0] * n
	for i in range(n):
		if i == 0:
			n_z[0] = int('0' == string[i])
			n_o[0] = int('1' == string[i])
		else:
			n_z[i] = n_z[i - 1] + int('0' == string[i])
			n_o[i] = n_o[i - 1] + int('1' == string[i])

	def solve(s, e):
		(S, E) = (s, e)
		ans = E
		while s <= e:
			m = (s + e) // 2
			if m == 0:
				c_z = n_z[E]
				c_o = n_o[E]
			else:
				c_z = n_z[E] - n_z[m - 1]
				c_o = n_o[E] - n_o[m - 1]
			if c_z <= k and c_o <= k:
				ans = m
				e = m - 1
			else:
				s = m + 1
		return ans
	ans = [0] * n
	re = [0] * n
	for i in range(n):
		temp = solve(0, i)
		re[i] = temp
		ans[i] = i - temp + 1
	reans = [ans[0]]
	for i in range(1, n):
		temp = ans[i] + reans[i - 1]
		reans.append(temp)

	def solved(l, r):
		(L, R) = (l, r)
		ans = L
		while l <= r:
			m = (l + r) // 2
			if re[m] <= L:
				l = m + 1
				ans = m
			else:
				r = m - 1
		return ans
	for _ in range(q):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		ind = solved(l, r)
		fa = reans[r] - reans[ind]
		val = ind - l + 1
		fa += val * (val + 1) // 2
		print(fa)


def ans(l, r):
	low = l - 1
	high = r + 1
	while high - low > 1:
		mid = (high + low) // 2
		if far[mid] <= r:
			low = mid
		else:
			high = mid
	k = low
	return sumfar[k] - sumfar[l - 1] + (r - k) * (r + 1) - (r * (r + 1) // 2 - l * (l - 1) // 2)
for _ in range(int(input())):
	(n, k, q) = map(int, input().split())
	s = input()
	far = [0] * (n + 1)
	sumfar = [0] * (n + 1)
	j = 1
	count0 = count1 = 0
	if s[j - 1] == '1':
		count1 += 1
	else:
		count0 += 1
	for i in range(1, n + 1):
		while j <= n and count0 <= k and (count1 <= k):
			j += 1
			if j > n:
				break
			if s[j - 1] == '1':
				count1 += 1
			else:
				count0 += 1
		far[i] = j
		sumfar[i] = sumfar[i - 1] + far[i]
		if s[i - 1] == '1':
			count1 -= 1
		else:
			count0 -= 1
	for i in range(q):
		(l, r) = map(int, input().split())
		print(ans(l, r))


def check(freq, K, i, j):
	if i == 0:
		if freq[j][0] <= K and freq[j][1] <= K:
			return True
	elif freq[j][0] - freq[i - 1][0] <= K and freq[j][1] - freq[i - 1][1] <= K:
		return True
	return False

def search(freq, K, low, high):
	olow = low
	while low < high:
		mid = low + (high - low + 1) // 2
		if check(freq, K, olow, mid) == True:
			low = mid
		else:
			high = mid - 1
	return low

def solve(sumfar, lastIndex, a, b):
	low = a - 1
	high = b + 1
	while high - low > 1:
		mid = low + (high - low) // 2
		if lastIndex[mid] <= b:
			low = mid
		else:
			high = mid
	ans = sumfar[low] - sumfar[a - 1]
	ans += (b - low) * (b + 1)
	ans -= b * (b + 1) // 2
	ans += a * (a - 1) // 2
	return ans
for _ in range(int(input())):
	(N, K, Q) = map(int, input().split())
	freq = [[0, 0] for i in range(N)]
	arr = list(input())
	if arr[0] == '0':
		freq[0] = [1, 0]
	else:
		freq[0] = [0, 1]
	for i in range(1, N):
		if arr[i] == '0':
			freq[i][0] = freq[i - 1][0] + 1
			freq[i][1] = freq[i - 1][1]
		else:
			freq[i][0] = freq[i - 1][0]
			freq[i][1] = freq[i - 1][1] + 1
	lastIndex = []
	sumfar = []
	lastIndex.append(0)
	sumfar.append(0)
	for i in range(1, N + 1):
		lastIndex.append(search(freq, K, i - 1, N - 1) + 2)
		sumfar.append(sumfar[i - 1] + lastIndex[i])
	for __ in range(Q):
		(a, b) = map(int, input().split())
		print(solve(sumfar, lastIndex, a, b))


def check_cond(mid, H, K, tot_1, tot_0):
	if mid != 0 and tot_0[H] - tot_0[mid - 1] <= K and (tot_1[H] - tot_1[mid - 1] <= K):
		return True
	if mid == 0 and tot_0[H] <= K and (tot_1[H] <= K):
		return True
	return False

def find_index(tot_0, tot_1, L, H, K):
	(l, h) = (L, H)
	ans = H
	while l <= h:
		mid = (l + h) // 2
		if check_cond(mid, H, K, tot_1, tot_0):
			ans = mid
			h = mid - 1
		else:
			l = mid + 1
	return ans

def find_ind(res, L, R):
	(l, h) = (L, R)
	ans = L
	while l <= h:
		mid = (l + h) // 2
		if max(L, mid - res[mid] + 1) == L:
			ans = mid
			l = mid + 1
		else:
			h = mid - 1
	return ans
for _ in range(int(input())):
	(N, K, Q) = map(int, input().split())
	S = input()
	tot_0 = [0 for _ in range(N)]
	tot_1 = [0 for _ in range(N)]
	for i in range(N):
		if i == 0:
			if S[i] == '0':
				tot_0[i] += 1
			else:
				tot_1[i] += 1
		elif S[i] == '0':
			tot_0[i] = tot_0[i - 1] + 1
			tot_1[i] = tot_1[i - 1]
		else:
			tot_1[i] = tot_1[i - 1] + 1
			tot_0[i] = tot_0[i - 1]
	res = [0 for _ in range(N)]
	res[0] = 1
	for j in range(1, N):
		ind = find_index(tot_0, tot_1, 0, j, K)
		ans = j - ind + 1
		res[j] = ans
	re = [res[0]]
	tot = res[0]
	for i in range(1, N):
		tot += res[i]
		re.append(tot)
	for j in range(Q):
		(L, R) = map(int, input().split())
		(L, R) = (L - 1, R - 1)
		ind = find_ind(res, L, R)
		count = (ind - L + 1) * (L + ind) // 2 - (L - 1) * (ind - L + 1)
		count += re[R] - re[ind]
		print(count)


import sys
input = sys.stdin.readline

def print(x, end='\n'):
	sys.stdout.write(str(x) + end)
t = int(input())
for i in range(t):
	(n, k, q) = tuple(map(int, input().split()))
	s = input()
	s_ls = [0 for j in range(n)]
	for i in range(n):
		s_ls[i] = int(s[i])
	far = [0 for o in range(n)]
	sum_far = [0 for m in range(n)]
	temp = 0
	r = 0
	for z in range(n):
		while r != n:
			if temp + s_ls[r] <= k and r - z + 1 - (temp + s_ls[r]) <= k:
				temp = temp + s_ls[r]
				r += 1
			else:
				break
		far[z] = r - 1
		if z != 0:
			sum_far[z] = sum_far[z - 1] + r - 1
		else:
			sum_far[z] = r - 1
		temp = temp - s_ls[z]
	for e in range(q):
		(l, r) = tuple(map(int, input().split()))
		l = l - 1
		r = r - 1
		left = l
		right = r
		while left <= right:
			mid = (left + right) // 2
			if far[mid] > r:
				right = mid - 1
			else:
				left = mid + 1
		y = right
		if y >= l:
			ans = (r + 1) * (r - y)
			ans = ans + (r - l + 1) * (-r - l) // 2
			if l == 0:
				ans = ans + sum_far[y] + y + 1
			else:
				ans = ans + sum_far[y] + y - (l - 1) - sum_far[l - 1]
		else:
			ans = (r - l + 1) * (-r - l) // 2 + (r + 1) * (r - l + 1)
		print(ans)


for _ in range(int(input())):
	(n, k, q) = map(int, input().split())
	s = input()
	s = [int(s[i]) for i in range(n)]
	Count = [0, 0]
	j = 0
	L = [0] * n
	R = [0] * n
	for i in range(n):
		while j < n and Count[s[j]] + 1 <= k:
			Count[s[j]] += 1
			j += 1
		L[i] = j - 1
		Count[s[i]] -= 1
	Count[0] = Count[1] = 0
	j = n - 1
	for i in range(n - 1, -1, -1):
		while j >= 0 and Count[s[j]] + 1 <= k:
			Count[s[j]] += 1
			j -= 1
		R[i] = j + 1
		Count[s[i]] -= 1
	Sum = [0] * (n + 1)
	for i in range(n):
		Sum[i + 1] = Sum[i] + L[i]
	for __ in range(q):
		(li, ri) = map(int, input().split())
		li -= 1
		ri -= 1
		k = R[ri] - 1
		res = 0
		if li <= k:
			res += Sum[k + 1] - Sum[li] + (ri - k) * ri
			res -= (li + ri - 2) * (ri - li + 1) // 2
		else:
			res += (ri - li + 2) * (ri - li + 1) // 2
		print(res)


from itertools import accumulate
from bisect import bisect
from sys import stdin
_data = iter(stdin.read().split('\n'))
input = lambda : next(_data)
buf = []
for _ in range(int(input())):
	(n, k, q) = [int(x) for x in input().split()]
	a = tuple((int(c) for c in input()))
	p = 0
	ct = [0] * 2
	ub = [0] * n
	for i in range(n):
		while p < n and ct[a[p]] + 1 <= k:
			ct[a[p]] += 1
			p += 1
		ub[i] = p
		ct[a[i]] -= 1
	ubs = [0]
	ubs.extend(accumulate(ub))
	for _ in range(q):
		(l, r) = [int(x) for x in input().split()]
		l -= 1
		p = bisect(ub, r, l, r)
		d = r - l
		ans = 0
		ans += ubs[p] - ubs[l]
		ans += r * (r - p)
		ans -= l * d
		ans -= d * (d - 1) // 2
		buf.append(str(ans))
print('\n'.join(buf))


def precompute(s, k, far, sumfar, n):
	count1 = 0
	count0 = 0
	j = 1
	if s[0] == '0':
		count0 += 1
	if s[0] == '1':
		count1 += 1
	for i in range(1, n + 1):
		while j <= n and count0 <= k and (count1 <= k):
			j += 1
			if j > n:
				break
			if s[j - 1] == '0':
				count0 += 1
			if s[j - 1] == '1':
				count1 += 1
		far[i] = j
		if s[i - 1] == '0':
			count0 -= 1
		if s[i - 1] == '1':
			count1 -= 1
	for k in range(1, n + 1):
		sumfar[k] = sumfar[k - 1] + far[k]

def ans_query(l, r):
	low = l - 1
	high = r + 1
	while high - low > 1:
		k = (low + high) // 2
		if far[k] <= r:
			low = k
		else:
			high = k
	km = low
	answer = sumfar[km] - sumfar[l - 1] + (r - km) * (r + 1) - (r * (r + 1) // 2 - l * (l - 1) // 2)
	return answer
for a in range(int(input())):
	(n, k, q) = map(int, input().split())
	s = list(input())
	far = [0 for i in range(n + 1)]
	sumfar = [0 for i in range(n + 1)]
	precompute(s, k, far, sumfar, n)
	for idx in range(q):
		(l, r) = map(int, input().split())
		ans = ans_query(l, r)
		print(ans)


def maximum_satisfied_index(s, ep, sp):
	index = [0]
	sum_ = [0]
	sum1 = [0]
	for j in range(n):
		sum_.append(sum_[j] + s[j + 1])
		if s[j + 1] == 0:
			sum1.append(sum1[j] + 1)
		else:
			sum1.append(sum1[j])
	while ep <= n:
		if sum_[ep] - sum_[sp - 1] <= k and sum1[ep] - sum1[sp - 1] <= k:
			index.append(ep - sp)
			ep += 1
		else:
			sp += 1
	return index
t = int(input())
for i in range(t):
	(n, k, q) = map(int, input().split())
	s = [int(i) for i in input()]
	s1 = s[:]
	s.insert(0, 0)
	s1.append(0)
	ep = 1
	sp = 1
	index1 = maximum_satisfied_index(s, ep, sp)
	index2 = maximum_satisfied_index(s1[::-1], ep, sp)
	cumsum = [0]
	for i in range(1, n + 1):
		cumsum.append(cumsum[i - 1] + index1[i] + 1)
	for ij in range(q):
		(l, r) = map(int, input().split())
		val = index2[n - l + 1] + 1
		inde = l + val - 1
		if inde >= r:
			q = r - l + 1
			print(int(q * (q + 1) / 2))
		else:
			print(int(cumsum[r] - cumsum[inde] + val * (val + 1) / 2))


def solve_query(l, r):
	lo = l
	hi = r
	while lo < hi:
		mid = (lo + hi) // 2
		if far[mid] < r + 1:
			lo = mid + 1
		else:
			hi = mid
	return cumfar[lo] - cumfar[l] + (r - lo + 1) * (r + 1) - (r * (r + 1) // 2 - l * (l - 1) // 2)
t = int(input())
for z in range(t):
	(n, k, q) = tuple(map(int, input().split()))
	sr = input()
	far = [i for i in range(n)]
	countz = 0
	counto = 0
	if sr[0] == '0':
		countz += 1
	else:
		counto += 1
	j = 0
	for i in range(n):
		while j < n and countz <= k and (counto <= k):
			j += 1
			if j == n:
				break
			if sr[j] == '0':
				countz += 1
			else:
				counto += 1
		far[i] = j
		if sr[i] == '0':
			countz -= 1
		else:
			counto -= 1
	cumfar = [0] * (n + 1)
	for i in range(1, n + 1):
		cumfar[i] = cumfar[i - 1] + far[i - 1]
	for i in range(q):
		(l, r) = tuple(map(int, input().split()))
		print(int(solve_query(l - 1, r - 1)))


t = int(input())

def precompute(n, k):
	(count0, count1) = (0, 0)
	if s[1] == '1':
		count1 = 1
	else:
		count0 = 1
	j = 1
	for i in range(1, n + 1):
		while j < n + 1 and count0 <= k and (count1 <= k):
			j += 1
			if j > n:
				break
			if s[j] == '0':
				count0 += 1
			else:
				count1 += 1
		far.append(j)
		if s[i] == '1':
			count1 -= 1
		else:
			count0 -= 1
	sumfar.append(0)
	for i in range(1, n + 1):
		sumfar.append(sumfar[i - 1] + far[i])

def count_substring(l, r, k):
	left = l - 1
	right = r + 1
	while right - left > 1:
		mid = int((left + right) / 2)
		if far[mid] <= r:
			left = mid
		else:
			right = mid
	k = left
	total_count = sumfar[k] - sumfar[l - 1] + (r - k) * (r + 1) - int(r * (r + 1) / 2) + int(l * (l - 1) / 2)
	return total_count
for i in range(t):
	(n, k, q) = map(int, input().split())
	s = list(input().strip())
	s.insert(0, '-1')
	far = [0]
	query = []
	sumfar = []
	precompute(n, k)
	for i in range(q):
		(l, r) = map(int, input().split())
		query.append((l, r))
	for i in range(q):
		print(count_substring(query[i][0], query[i][1], k))


def solve(l, r):
	(L, R) = (l, r)
	ans = R
	while l <= r:
		m = l + (r - l) // 2
		if m == 0:
			cZero = nZero[R]
			cOne = nOne[R]
		else:
			cZero = nZero[R] - nZero[m - 1]
			cOne = nOne[R] - nOne[m - 1]
		if cOne <= k and cZero <= k:
			ans = m
			r = m - 1
		else:
			l = m + 1
	return ans

def solved(l, r):
	(L, R) = (l, r)
	ans = L
	while l <= r:
		m = l + (r - l) // 2
		if re[m] <= L:
			l = m + 1
			ans = m
		else:
			r = m - 1
	return ans
for _ in range(int(input())):
	(n, k, q) = map(int, input().split())
	bString = input()
	nZero = [0] * n
	nOne = [0] * n
	for i in range(n):
		if i == 0:
			nZero[0] = int('0' == bString[i])
			nOne[0] = int('1' == bString[i])
		else:
			nZero[i] = nZero[i - 1] + int('0' == bString[i])
			nOne[i] = nOne[i - 1] + int('1' == bString[i])
	ans = [0] * n
	re = [0] * n
	for i in range(n):
		temp = solve(0, i)
		re[i] = temp
		ans[i] = i - temp + 1
	reans = [ans[0]]
	for i in range(1, n):
		temp = ans[i] + reans[i - 1]
		reans.append(temp)
	for _ in range(q):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		index = solved(l, r)
		val = index - l + 1
		fa = reans[r] - reans[index] + val * (val + 1) // 2
		print(fa)


for _ in range(int(input())):
	(n, k, q) = map(int, input().split())
	s = input()
	cnt = [0] * 2
	j = 0
	L = [0] * n
	R = [0] * n
	for i in range(n):
		while j < n and cnt[int(s[j])] + 1 <= k:
			cnt[int(s[j])] += 1
			j += 1
		L[i] = j - 1
		cnt[int(s[i])] -= 1
	cnt[0] = 0
	cnt[1] = 0
	j = n - 1
	for i in range(n - 1, -1, -1):
		while j >= 0 and cnt[int(s[j])] + 1 <= k:
			cnt[int(s[j])] += 1
			j -= 1
		R[i] = j + 1
		cnt[int(s[i])] -= 1
	add = [0] * (n + 1)
	for i in range(n):
		add[i + 1] = add[i] + L[i]
	for i in range(q):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		u = R[r] - 1
		if l <= u:
			res = add[u + 1] - add[l] + (r - u) * r
			res -= (l + r - 2) * (r - l + 1) // 2
		else:
			res = (r - l + 2) * (r - l + 1) // 2
		print(res)


t = int(input())
for i in range(t):
	(n, k, q) = [int(i) for i in input().split()]
	arr = [int(i) for i in input()]
	temp = [[0 for i in range(4)] for i in range(n + 1)]
	for i in range(1, n + 1):
		temp[i][0] = arr[i - 1]
	ptr = 0
	count_0 = 0
	count_1 = 0
	j = 1
	while j <= n:
		if temp[j][0] == 0:
			count_0 += 1
		else:
			count_1 += 1
		if count_0 <= k and count_1 <= k:
			ptr = j
		else:
			if temp[j][0] == 0:
				count_0 -= 1
			else:
				count_1 -= 1
			break
		j += 1
	temp[1][1] = ptr
	j = 2
	while j <= n:
		if temp[j - 1][0] == 0:
			count_0 -= 1
		else:
			count_1 -= 1
		z = ptr + 1
		while z <= n:
			if temp[z][0] == 0:
				count_0 += 1
			else:
				count_1 += 1
			if count_0 <= k and count_1 <= k:
				ptr = z
			else:
				if temp[z][0] == 0:
					count_0 -= 1
				else:
					count_1 -= 1
				break
			z += 1
		temp[j][1] = ptr
		j += 1
	for i in range(1, n + 1):
		temp[i][2] = temp[i - 1][2] + temp[i][1]
	ptr2 = n
	for i in range(n, 0, -1):
		while ptr2 > 0 and temp[ptr2][1] >= i:
			ptr2 -= 1
		temp[i][3] = ptr2
	for i in range(q):
		(l, r) = [int(i) for i in input().split()]
		k = temp[r][3]
		ans = 0
		if k < l:
			ans += r * (r - l + 1)
			ans -= (r - l + 1) * (r + l) // 2
			ans += r - l + 1
			print(ans)
		else:
			ans += temp[temp[r][3]][2] - temp[l - 1][2]
			ans -= (temp[r][3] - l + 1) * (temp[r][3] + l) // 2
			ans += temp[r][3] - l + 1
			ans += r * (r - temp[r][3])
			ans -= (r - temp[r][3]) * (temp[r][3] + r + 1) // 2
			ans += r - temp[r][3]
			print(ans)