Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n,x,m=map(int,input().split())
i=int(2)
a=[x]
q=int(0)
while (i <= n) and (q == 0):
	x=(x**2)%m
	if x in a:
		q=1
	else:
		a.append(x)
	i=i+1

if len(a) == n:
	print(sum(a))	
else:
	j=a.index(x)
	b=a[0:j]
	c=a[j:]
	lb=len(b)
	lc=len(c)
	k=(n-lb)%lc
	l=(n-lb)//lc
	d=c[0:k]
	print(sum(b)+sum(c)*l+sum(d))

Fixed submission:
n,x,m=map(int,input().split())
i=int(2)
a=[x]
q=int(0)
while (i <= n) and (q == 0):
	x=(x**2)%m
	if x in a:
		q=1
	else:
		a.append(x)
	i=i+1

if len(a) == n:
	print(sum(a))	
else:
	j=a.index(x)
	b=a[0:j]
	c=a[j:]
	lb=len(b)
	lc=len(c)
	k=(n-lb)%lc
	l=(n-lb)//lc
	d=c[0:k]
	print(sum(b)+sum(c)*l+sum(d))

Buggy python submission (verdict: Runtime Error):
n,x,m=map(int,input().split())
i=int(2)
a=[x]
while (i <= n):
	x=(x**2)%m
	if x in a:
		goto .abc
	else:
		a.append(x)
label .abc
if len(a) == n:
	print(sum(a))	
else:
	j=a.index(x)
	b=a[0:j]
	c=a[j:]
	lb=len(b)
	lc=len(c)
	k=(n-lb)%lc
	l=(n-lb)//lc
	d=c[0:k]
	print(sum(b)+sum(c)*l+sum(d))

Fixed submission:
n,x,m=map(int,input().split())
i=int(2)
a=[x]
q=int(0)
while (i <= n) and (q == 0):
	x=(x**2)%m
	if x in a:
		q=1
	else:
		a.append(x)
	i=i+1

if len(a) == n:
	print(sum(a))	
else:
	j=a.index(x)
	b=a[0:j]
	c=a[j:]
	lb=len(b)
	lc=len(c)
	k=(n-lb)%lc
	l=(n-lb)//lc
	d=c[0:k]
	print(sum(b)+sum(c)*l+sum(d))

Buggy python submission (verdict: Time Limit Exceeded):
n,x,m=map(int,input().split())
i=int(2)
a=[x]
q=int(0)
while (i <= n) and (q == 0):
	x=(x**2)%m
	if x in a:
		q=1
	else:
		a.append(x)

if len(a) == n:
	print(sum(a))	
else:
	j=a.index(x)
	b=a[0:j]
	c=a[j:]
	lb=len(b)
	lc=len(c)
	k=(n-lb)%lc
	l=(n-lb)//lc
	d=c[0:k]
	print(sum(b)+sum(c)*l+sum(d))

Fixed submission:
n,x,m=map(int,input().split())
i=int(2)
a=[x]
q=int(0)
while (i <= n) and (q == 0):
	x=(x**2)%m
	if x in a:
		q=1
	else:
		a.append(x)
	i=i+1

if len(a) == n:
	print(sum(a))	
else:
	j=a.index(x)
	b=a[0:j]
	c=a[j:]
	lb=len(b)
	lc=len(c)
	k=(n-lb)%lc
	l=(n-lb)//lc
	d=c[0:k]
	print(sum(b)+sum(c)*l+sum(d))
Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
ans=max[a*c,a*d,b*c,b*d]
print(ans)

Fixed submission:
a,b,c,d=map(int,input().split())
print(max([a*c,a*d,b*c,b*d]))

Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
print(max[a*c,a*d,b*c,b*c])

Fixed submission:
a,b,c,d=map(int,input().split())
print(max([a*c,a*d,b*c,b*d]))
Buggy python submission (verdict: Time Limit Exceeded):
s=str(input())
n=len(s)
i=0
ans=0
c=0
d=0
while i < n:
	if s[i] == "<":
		c=c+1
		ans=ans+c
	else:
		j=1
		while (i >= j) and (s[i-j] == ">"):
			j=j+1
		if j > 1:
			if d >= j:
				ans=ans+j-1
			else:
				ans=ans+j
		elif i == 0:
			ans=1
		else:
			d=c
		c=0
	i=i+1
print(ans)

Fixed submission:
s=str(input())
n=len(s)
i=0
ans=0
c=0
d=0
j=0
while i < n:
	if s[i] == "<":
		c=c+1
		ans=ans+c
		j=0
	else:
		j=j+1
		if j > 1:
			if d >= j:
				ans=ans+j-1
			else:
				ans=ans+j
		elif i == 0:
			ans=1
		else:
			d=c
		c=0
	i=i+1
print(ans)

Buggy python submission (verdict: Runtime Error):
s=str(input())
n=len(s)
i=0
ans=0
c=0
while i < n:
	if s[i] == "<":
		c=c+1
		ans=ans+c
	else:
		j=1
		while (i >= j) and (s[i-j] == ">"):
			j=j+1
		if j > 1:
			if d >= j:
				ans=ans+j-1
			else:
				ans=ans+j
		elif i == 0:
			ans=1
		else:
			d=c
		c=0
	i=i+1
print(ans)

Fixed submission:
s=str(input())
n=len(s)
i=0
ans=0
c=0
d=0
j=0
while i < n:
	if s[i] == "<":
		c=c+1
		ans=ans+c
		j=0
	else:
		j=j+1
		if j > 1:
			if d >= j:
				ans=ans+j-1
			else:
				ans=ans+j
		elif i == 0:
			ans=1
		else:
			d=c
		c=0
	i=i+1
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
i=1
while i < 10:
  if n%i==0:
    if n/i < 10:
      print(Yes)
      i=10
  i=i+1
if i=10:
  print(No)

Fixed submission:
n=int(input())
i=1
while i < 10:
  if n%i==0:
    if n/i < 10:
      print("Yes")
      i=10
  i=i+1
if i == 10:
  print("No")
Buggy python submission (verdict: Time Limit Exceeded):
a = int(input())
i = list(map(int, input().split()))

ans = 1
flag = 0
for x in range(len(i)):
    ans = ans * i[x]
    if ans > 1000000000000000000:
        flag = 1
    if i[x] == 0:
        flag = 2

if flag == 1:
    print(-1)
elif flag == 2:
    print(0)
else:
    print(ans)

Fixed submission:
a = int(input())
i = list(map(int, input().split()))

ans = 1
flag = 0

if i.count(0) > 0:
    print(0)
    flag = 1

if flag == 0:
    for x in range(len(i)):
        ans = ans * i[x]
        if ans > 1000000000000000000:
            flag = 1
            break

    if flag == 1:
        print(-1)
    elif flag == 2:
        print(0)
    else:
        print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
a = int(input())
i = list(map(int, input().split()))

ans = 1
flag = 0
for x in range(len(i)):
    ans = ans * i[x]
    if ans > 1000000000000000000:
        flag = 1
    if i[x] == 0:
        flag = 2

if flag == 1:
    print(-1)
elif flag == 2:
    print(0)
else:
    print(ans)

Fixed submission:
a = int(input())
i = list(map(int, input().split()))

ans = 1
flag = 0

if i.count(0) > 0:
    print(0)
    flag = 1

if flag == 0:
    for x in range(len(i)):
        ans = ans * i[x]
        if ans > 1000000000000000000:
            flag = 1
            break

    if flag == 1:
        print(-1)
    elif flag == 2:
        print(0)
    else:
        print(ans)
Buggy python submission (verdict: Runtime Error):
r = input()
print(3*r*r)



Fixed submission:
r = int(input())
print(3*r*r)
Buggy python submission (verdict: Runtime Error):
def main():
    N = int(input())
    A_list = list(map(int, input().split()))
    mod = 10**9 + 7

    ans = 0
    A_ = sum(A_list) % mod
    for i in range(N-1):
        A = A_list[i]
        A_ = A_ - A
        ans = (ans + (A * A_) % mod)) % mod
    print(ans)
    return


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N = int(input())
    A_list = list(map(int, input().split()))
    mod = 10**9 + 7

    ans = 0
    A_ = sum(A_list) % mod
    for i in range(N-1):
        A = A_list[i]
        A_ = A_ - A
        ans = (ans + (A * A_) % mod) % mod
    print(ans)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    N = int(input())
    A_list = list(map(int, input().split()))
    mod = 10**9 + 7

    ans = 0
    A_ = sum(A_list) % mod
    for i in range(N):
        A = A_list[i]
        A_ = A_ - A
        ans = (ans + (A * A_) % mod)) % mod
    print(ans)
    return


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N = int(input())
    A_list = list(map(int, input().split()))
    mod = 10**9 + 7

    ans = 0
    A_ = sum(A_list) % mod
    for i in range(N-1):
        A = A_list[i]
        A_ = A_ - A
        ans = (ans + (A * A_) % mod) % mod
    print(ans)
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A_list = list(map(int, input().split()))
    mod = 10**9 + 7

    ans = 0
    for i in range(N):
        A = A_list[i]
        A_ = A_list[i+1:]
        ans = (ans + (A * sum(A_) % mod)) % mod
    print(ans)
    return



if __name__ == '__main__':
    main()
    

Fixed submission:
def main():
    N = int(input())
    A_list = list(map(int, input().split()))
    mod = 10**9 + 7

    ans = 0
    A_ = sum(A_list) % mod
    for i in range(N-1):
        A = A_list[i]
        A_ = A_ - A
        ans = (ans + (A * A_) % mod) % mod
    print(ans)
    return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import math

N = int(input())
a_lis = list(map(int, input().split()))

ans = 1
for i in a_lis:
    if math.log(i, 10) + math.log(ans + 10) > 18:
        ans = -1
        break
    
    else:
        ans += i
        
print(ans)

Fixed submission:
N = int(input())
a_lis = list(map(int, input().split()))

ans = 1
if 0 in a_lis:
    ans = 0
    
else:
    for i in a_lis:
        ans *= i
        if ans > pow(10, 18):
            ans = -1
            break
        
print(ans)
Buggy python submission (verdict: Runtime Error):
A, B = map(input().split())

A = int(A)
B = float(B)

print(int((A * (B * 100)) / 100)) 

Fixed submission:
A, B = input().split()

A = int(A)
B = int(float(B) * 100 + 0.5)
ans = A * B // 100

print(ans)

Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())

print((A * (B * 100)) / 100) 

Fixed submission:
A, B = input().split()

A = int(A)
B = int(float(B) * 100 + 0.5)
ans = A * B // 100

print(ans)

Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())

print(A * (B * 100) / 100) 

Fixed submission:
A, B = input().split()

A = int(A)
B = int(float(B) * 100 + 0.5)
ans = A * B // 100

print(ans)

Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())

print(int(A*B))

Fixed submission:
A, B = input().split()

A = int(A)
B = int(float(B) * 100 + 0.5)
ans = A * B // 100

print(ans)

Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())

print(int(A*B))

Fixed submission:
A, B = input().split()

A = int(A)
B = int(float(B) * 100 + 0.5)
ans = A * B // 100

print(ans)

Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())

print(A*B*10//10)

Fixed submission:
A, B = input().split()

A = int(A)
B = int(float(B) * 100 + 0.5)
ans = A * B // 100

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))

    dp = [0] * N
    for i in range(1, N):
        dp[i] = dp[i-1] + abs(h[i] - h[i-1])
        for j in range(2, K+1):
            if i-j < 0:
                break
            else:
                dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))

    print(dp[-1])
    return


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))

    dp = [0] * n
    for i in range(1, n):
        j = max(0, i-k)
        dp[i] = min(x + abs(h[i] - y) for x, y in zip(dp[j:i], h[j:i]))

    print(dp[-1])
    return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def expectedVal(p):
    res = 0
    for i in range(1, p+1):
        res += i / p
    # print("p:{} {}".format(p,res))
    return res

n, k = map(int, input().split())
P = list(map(int, input().split()))

setP = set(P)
exDict = {}
for x in setP:
    exDict[x] = expectedVal(x)

m = n - k + 1

ans = 0
for i in range(m):
    total = 0
    # print(P[i:i+k])
    for p in P[i:i+k]:
        total += exDict[p]
    ans = max(ans, total)
    # print("i:{} ans:{}".format(i,ans))
print(ans)

Fixed submission:
N, K = map(int, input().split())
p = list(map(int, input().split()))
ex_vals = [(pi+1) / 2 for pi in p]
cumsum = [0]
for i,e in enumerate(ex_vals):
    cumsum.append(cumsum[i] + e)
ans = 0
for i in range(N-K+1):
    ans = max(ans, cumsum[i+K] - cumsum[i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
INF = 1000000007
keta = len(bin(max(A))) - 2
ans = 0
shift = 0
for _ in range(keta):
    num_1 = 0
    for a in A:
        if a>>shift&1:
            num_1 += 1
    ans += num_1 * (N-num_1) * 2 ** shift
    shift += 1
print(ans % INF)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
INF = 1000000007
keta = len(bin(max(A))) - 2
ans = 0
shift = 0
for _ in range(keta):
    num_1 = 0
    for a in A:
        if a>>shift&1:
            num_1 += 1
    ans += num_1 * (N-num_1) * 2 ** shift
    shift += 1
print(ans % INF)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
INF = 1000000007
ans = 0
keta = len(bin(max(A)))-2
shift = 0
while(shift < keta):
    c1 = 0
    c0 = 0
    for a in A:
        if a>>shift &1:
            c1 += 1
        else:
            c0 += 1
    ans += c1 * c0 * 2**shift
    shift += 1
print(ans % INF)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
INF = 1000000007
keta = len(bin(max(A))) - 2
ans = 0
shift = 0
for _ in range(keta):
    num_1 = 0
    for a in A:
        if a>>shift&1:
            num_1 += 1
    ans += num_1 * (N-num_1) * 2 ** shift
    shift += 1
print(ans % INF)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
INF = 1000000007
# 愚直な回答
ans = 0
for i in range(0, N-1):
    for j in range(i+1, N):
        ans += A[i]^A[j]
print(ans % INF)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
INF = 1000000007
keta = len(bin(max(A))) - 2
ans = 0
shift = 0
for _ in range(keta):
    num_1 = 0
    for a in A:
        if a>>shift&1:
            num_1 += 1
    ans += num_1 * (N-num_1) * 2 ** shift
    shift += 1
print(ans % INF)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
INF = 1000000007
# 愚直な回答
ans = 0
for i in range(0, N-1):
    for j in range(i+1, N):
        ans += A[i]^A[j]
print(ans % INF)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
INF = 1000000007
keta = len(bin(max(A))) - 2
ans = 0
shift = 0
for _ in range(keta):
    num_1 = 0
    for a in A:
        if a>>shift&1:
            num_1 += 1
    ans += num_1 * (N-num_1) * 2 ** shift
    shift += 1
print(ans % INF)
Buggy python submission (verdict: Time Limit Exceeded):
from math import factorial
def pow_with_mod(a, b, p):
    if b==0: return 1
    if b%2==0:
        d=pow_with_mod(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*pow_with_mod(a,b-1,p ))%p

def comb_with_mod(n, k, p):

    if n<0 or k<0 or n<k: 
        return 0
    if n==0 or k==0:
        return 1
    a=factorial(n) %p
    b=factorial(k) %p
    c=factorial(n-k) %p
    return (a*pow_with_mod(b,p-2,p)*pow_with_mod(c,p-2,p))%p

div = 10 ** 9 + 7
X, Y = map(int, input().split())

if((X+Y) % 3 != 0):
    print(0)
    exit()

n = (X+Y) // 3
X -= n
Y -= n
if(X < 0 or Y < 0):
    print(0)
    exit()

ans = comb_with_mod(X+Y, X, div)
print(ans)


Fixed submission:
def inv(x, mod=1):
    return pow(x, mod-2, mod)

def fact(x, mod=1):
    res = 1 
    for i in range(1, x + 1): 
        res *= i
        res %= mod    
    return res

def comb(n, k, mod=1):
    return (fact(n, mod) * inv(fact(n-k, mod), mod) * inv(fact(k, mod), mod)) % mod

div = 10 ** 9 + 7
X, Y = map(int, input().split())

if (X+Y) % 3 != 0:
    print(0)
    exit()

n = (X+Y) // 3
X -= n
Y -= n
if X < 0 or Y < 0:
    print(0)
    exit()

ans = comb(X+Y, X, div)
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
root = int(N**0.5)
print(min([i + N //i -2 for i in range(1, root+1) if N % i == 0]))

Fixed submission:
A, B = map(int,input().split())
ans = A*B if (1 <= A <= 9) and (1 <= B <= 9) else -1
print(ans)

Buggy python submission (verdict: Runtime Error):
N = int(input())
root = int(N**0.5)
print(min([i + N //i -2 for i in range(1, root+1) if N % i == 0])

Fixed submission:
A, B = map(int,input().split())
ans = A*B if (1 <= A <= 9) and (1 <= B <= 9) else -1
print(ans)
Buggy python submission (verdict: Runtime Error):
root = int(int(input())**0.5)
print(min([i + N //i -2 for i in range(1, root+1) if N % i == 0])

Fixed submission:
N = int(input())
root = int(N**0.5)

pairs = [[i, N //i] for i in range(1, root+1) if N % i == 0]

move = min([pair[0] + pair[1] -2 for pair in pairs])
print(move)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = list(map(int, input().split()))

ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if(L[i] < (L[j] + L[k]) and L[j] < (L[k] + L[i]) and L[k] < (L[i] + L[j])):
                ans += 1

print(ans)

Fixed submission:
import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        k = bisect.bisect_left(L, L[i]+L[j])
        ans += max(0, k-j-1)
print(ans)
Buggy python submission (verdict: Runtime Error):
RDULULDURURLRDULRLR

Fixed submission:
S = input()
odd = set(["R","U","D"])
even = set(["L","U","D"])
ok = True
for s in S[::2]:
    if s not in odd:
        ok = False
if len(S) > 1:
    for s in S[1::2]:
        if s not in even:
            ok = False
print("Yes" if ok else "No")

Buggy python submission (verdict: Runtime Error):
RDULULDURURLRDULRLR

Fixed submission:
S = input()
odd = set(["R","U","D"])
even = set(["L","U","D"])
ok = True
for s in S[::2]:
    if s not in odd:
        ok = False
if len(S) > 1:
    for s in S[1::2]:
        if s not in even:
            ok = False
print("Yes" if ok else "No")
Buggy python submission (verdict: Time Limit Exceeded):
print(sum([i for i in range(1, int(input()))]))

Fixed submission:
n = int(input())
print(n*(n-1)//2)
Buggy python submission (verdict: Time Limit Exceeded):
def sigma(n):
    return (n+1) * n//2 if n % 2 == 0 else sigma(n-1)+n

n = int(input())
Ss = [sorted(input()) for _ in range(n)]
Ss.sort()
src = []
ans = 0
for i in range(n):
    if(src == Ss[i]):
        continue
    else:
        src = [] 
    if not src:
        ans += sigma(Ss.count(Ss[i])-1)
        src = Ss[i]
print(ans)

Fixed submission:
n = int(input())
S = ["".join(sorted(input())) for _ in range(n)]
ans = 0
dict = {}
for s in S:
    tmp = dict.get(s, 0)
    ans += tmp
    dict[s] = tmp + 1
print(ans)
Buggy python submission (verdict: Runtime Error):
import heapq
n = int(input())
A = [int(input()) for _ in range(n)]

lerge1, lerge2  = sorted(A)[-2:]
for i in range(n):
    if a[i]==m1:
        pritn(m2)
    else:
        print(m1)



Fixed submission:
n = int(input())
A = [int(input()) for _ in range(n)]

m2, m1  = sorted(A)[-2:]
for i in range(n):
    if A[i]==m1:
        print(m2)
    else:
        print(m1)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
broken = [i in a for i in range(n)]
mod = 1000000007
dp = [0 for _ in range(n+2)]
dp[n] = 1
for i in range(n)[::-1]:
    if(broken[i]):
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % mod
print(dp[0])

Fixed submission:
n, m = map(int, input().split())
broken = [0 for _ in range(n)]
for _ in range(m):
    broken[int(input())] = 1
mod = 1000000007
dp = [0 for _ in range(n+2)]
dp[n] = 1
for i in range(n)[::-1]:
    if(broken[i]):
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % mod
print(dp[0])
Buggy python submission (verdict: Time Limit Exceeded):
def move(start,end,city):
    if( a[start-1] > city[start]):
        # tmp1 = city[start]
        city[end] += city[start]
        city[start] = 0
    else:
        city[end] += a[start-1]
        city[start] -= a[start-1]
    return city

n = int(input())
a = [int(input()) for i in range(5)]
city = [0,n,0,0,0,0,0,0]

time = 0
while(city[6] < n):
    time += 1
    for i in range(5):
        city = move(5-i,6-i,city)
print(time)

Fixed submission:
N = int(input())
A = [int(input()) for _ in range(5)]
print(-(-N // min(A))+4)
Buggy python submission (verdict: Time Limit Exceeded):
# import re
N, Q = map(int, input().split())
S = input()
qs = [tuple(map(int, input().split())) for _ in range(Q)]

# print(qs)

# regex =  re.compile('AC')
for q in qs:
    # print(q)
    print(S[q[0]-1:q[1]].count('AC'))

Fixed submission:
N, Q = map(int, input().split())
S = input()
query = [list(map(int,input().split())) for _ in range(Q)]

cum_sum = [0,0]
tmp = 0
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C":
        tmp += 1
    cum_sum.append(tmp)
# print(cum_sum)

for q in query:
    print(cum_sum[q[1]] - cum_sum[q[0]])

Buggy python submission (verdict: Time Limit Exceeded):
import re
N, Q = map(int, input().split())
S = input()
qs = [tuple(map(int, input().split())) for _ in range(Q)]

# print(qs)

regex =  re.compile('AC')
for q in qs:
    # print(q)
    print(len(regex.findall(S[q[0]-1:q[1]])))

Fixed submission:
N, Q = map(int, input().split())
S = input()
query = [list(map(int,input().split())) for _ in range(Q)]

cum_sum = [0,0]
tmp = 0
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C":
        tmp += 1
    cum_sum.append(tmp)
# print(cum_sum)

for q in query:
    print(cum_sum[q[1]] - cum_sum[q[0]])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, K = map(int, input().split())
    h = [0] + list(map(int, input().split())) # 便宜上、先頭に[0]

    dp = [1000000007 for _ in range(N+1)] # dp[i]：足場iに移動する最小コスト
    dp[1] = 0 # 初期位置のため、0
    dp[2] = abs(h[2]-h[1]) # 足場2への移動は1パターンのみのため

    for dst in range(3, N+1):
        for k in range(1,K+1):
            src = dst-k
            if src < 1:
                break
            dp[dst] = min(dp[dst], dp[src] + abs(h[dst]-h[src]))
    print(dp[N])

if __name__ == "__main__":
    main()

Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, K = map(int, input().split())
    h = [0] + list(map(int, input().split())) # 便宜上、先頭に[0]

    dp = [1000000007 for _ in range(N+1)] # dp[i]：足場iに移動する最小コスト
    dp[1] = 0 # 初期位置のため、0
    dp[2] = abs(h[2]-h[1]) # 足場2への移動は1パターンのみのため

    for dst in range(3, N+1):
        for k in range(1,K+1):
            src = dst-k
            if src < 1:
                break
            dp[dst] = min(dp[dst], dp[src] + abs(h[dst]-h[src]))
    print(dp[N])

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
h = [0] + list(map(int, input().split())) # 便宜上、先頭に[0]

dp = [1000000007 for _ in range(N+1)] # dp[i]：足場iに移動する最小コスト
dp[1] = 0 # 初期位置のため、0
dp[2] = abs(h[2]-h[1]) # 足場2への移動は1パターンのみのため

for dst in range(3, N+1):
    for k in range(1,K+1):
        src = dst-k
        if src < 1:
            break
        dp[dst] = min(dp[dst], dp[src] + abs(h[dst]-h[src]))
print(dp[N])

Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, K = map(int, input().split())
    h = [0] + list(map(int, input().split())) # 便宜上、先頭に[0]

    dp = [1000000007 for _ in range(N+1)] # dp[i]：足場iに移動する最小コスト
    dp[1] = 0 # 初期位置のため、0
    dp[2] = abs(h[2]-h[1]) # 足場2への移動は1パターンのみのため

    for dst in range(3, N+1):
        for k in range(1,K+1):
            src = dst-k
            if src < 1:
                break
            dp[dst] = min(dp[dst], dp[src] + abs(h[dst]-h[src]))
    print(dp[N])

if __name__ == "__main__":
    main()