Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
mod = 2019
l = [0]*mod
ans = 0

for i in range(len(s)):
    a = int(s[i:])%mod
    l[a] += 1
l[0] += 1

for i in range(2019):
    ans += l[i]*(l[i] - 1)//2

print(ans)

Fixed submission:
s = input()
mod = 2019
l = [0]*mod
l[0] = 1 #余りが0の場合が1足りないので補う
ans = 0
r = 0
t = 1

for i in s[::-1]:
    r += int(i)*t
    r %= mod # 余りをrに代入してしまっても、後の計算に支障が無い。
    l[r] += 1
    t *= 10
    t %= mod # t *= 10を使用しても、ここの余りを使用しても、r%modの答えは変わらない。

for i in l:
    ans += i*(i - 1)//2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
mod = 2019
l = [0]*mod
ans = 0

for i in range(len(s)):
    a = int(s[i:])%mod
    l[a] += 1
l[0] += 1

for i in range(2019):
    ans += l[i]*(l[i] - 1)//2

print(ans)

Fixed submission:
s = input()
mod = 2019
l = [0]*mod
l[0] = 1 #余りが0の場合が1足りないので補う
ans = 0
r = 0
t = 1

for i in s[::-1]:
    r += int(i)*t
    r %= mod # 余りをrに代入してしまっても、後の計算に支障が無い。
    l[r] += 1
    t *= 10
    t %= mod # t *= 10を使用しても、ここの余りを使用しても、r%modの答えは変わらない。

for i in l:
    ans += i*(i - 1)//2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
l = len(s)
cnt = 0

for i in range(l):
    if len(s[i:]) > 4:
        m = int(s[i:])%2019
        for j in range(i + 2, l):
            if j == l - 1:
                if m == 0:
                    cnt += 1
            elif m == int(s[j + 1:])%2019:
                cnt += 1

print(cnt)

Fixed submission:
s = input()
mod = 2019
l = [0]*mod
l[0] = 1 #余りが0の場合が1足りないので補う
ans = 0
r = 0
t = 1

for i in s[::-1]:
    r += int(i)*t
    r %= mod # 余りをrに代入してしまっても、後の計算に支障が無い。
    l[r] += 1
    t *= 10
    t %= mod # t *= 10を使用しても、ここの余りを使用しても、r%modの答えは変わらない。

for i in l:
    ans += i*(i - 1)//2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
l = len(s)
cnt = 0

for i in range(l):
    for j in range(i, l):
        if int(s[i:j + 1])%2019 == 0 and int(s[i:j + 1]) != 0:
            cnt +=1

print(cnt)

Fixed submission:
s = input()
mod = 2019
l = [0]*mod
l[0] = 1 #余りが0の場合が1足りないので補う
ans = 0
r = 0
t = 1

for i in s[::-1]:
    r += int(i)*t
    r %= mod # 余りをrに代入してしまっても、後の計算に支障が無い。
    l[r] += 1
    t *= 10
    t %= mod # t *= 10を使用しても、ここの余りを使用しても、r%modの答えは変わらない。

for i in l:
    ans += i*(i - 1)//2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
l = len(s)
cnt = 0

for i in range(l):
    for j in range(i, l):
        if int(s[i:j + 1])%2019 == 0 and int(s[i:j + 1]) != 0:
            cnt +=1

print(cnt)

Fixed submission:
s = input()
mod = 2019
l = [0]*mod
l[0] = 1 #余りが0の場合が1足りないので補う
ans = 0
r = 0
t = 1

for i in s[::-1]:
    r += int(i)*t
    r %= mod # 余りをrに代入してしまっても、後の計算に支障が無い。
    l[r] += 1
    t *= 10
    t %= mod # t *= 10を使用しても、ここの余りを使用しても、r%modの答えは変わらない。

for i in l:
    ans += i*(i - 1)//2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
ans = 0

for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
           ans += gcd(a, b, c)

print(ans)

Fixed submission:
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
ans = 0

for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
           ans += gcd(a, b, c)

print(ans)
Buggy python submission (verdict: Runtime Error):
s = list(input())
n = len(s)
ans = "No"

for i in range(1 - -(n//2)//2):
    if s[i] == s[n//2 - i - 1] == s[n//2 + i + 1] == s[n - i - 1]:
        ans = "Yes"
    else:
        print("No")
        exit()

print(ans)

Fixed submission:
s = list(input())
n = len(s)
ans = "No"

if n == 3:
    if s[0] == s[2]:
        print("Yes")
        exit()
    else:
        print("No")
        exit()


for i in range(1 - -(n//2)//2):
    if s[i] == s[n//2 - i - 1] == s[n//2 + i + 1] == s[n - i - 1]:
        ans = "Yes"
    else:
        print("No")
        exit()

print(ans)
Buggy python submission (verdict: Runtime Error):
while True:
    Lists = [1, 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
    x = int(input())
    print(Lists[x])

Fixed submission:
Lists = [1, 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
x = int(input())
print(Lists[x])
Buggy python submission (verdict: Runtime Error):
n, m, k = map(int, input().split())
F = [[] for i in range(n)]
B = [set() for i in range(n)]
l = [0]*n

for i in range(m):
    a, b = map(int, input().split())
    F[a - 1].append(b - 1)
    F[b - 1].append(a - 1)

for i in range(k):
    c, d = map(int, input().split())
    B[c - 1].add(d - 1)
    B[d - 1].add(c - 1)

seen = [0]*n
cnt = 0
r = []

def dfs(x):
    if seen[x] == 0:
        r[cnt].add(x)
        seen[x] = 1
        for i in F[x]:
            dfs(i)

for i in range(n):
    if seen[i] == 0:
        r.append(set())
        dfs(i)
        cnt += 1

ans = [0]*n

for i in r:
    lr = len(i)
    for j in i:
        ans[j] = lr - len(F[j]) - len(i & B[j]) - 1

print(*ans)

Fixed submission:
import sys
sys.setrecursionlimit(10**9)

n, m, k = map(int, input().split())
F = [[] for i in range(n)]
B = [set() for i in range(n)]
l = [0]*n

for i in range(m):
    a, b = map(int, input().split())
    F[a - 1].append(b - 1)
    F[b - 1].append(a - 1)

for i in range(k):
    c, d = map(int, input().split())
    B[c - 1].add(d - 1)
    B[d - 1].add(c - 1)

seen = [0]*n
cnt = 0
r = []

def dfs(x):
    if seen[x] == 0:
        r[cnt].add(x)
        seen[x] = 1
        for i in F[x]:
            dfs(i)

for i in range(n):
    if seen[i] == 0:
        r.append(set())
        dfs(i)
        cnt += 1

ans = [0]*n

for i in r:
    lr = len(i)
    for j in i:
        ans[j] = lr - len(F[j]) - len(i & B[j]) - 1

print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

for i in range(n -1):
    for j in range(i + 1, n):
        if a[i] == a[j]:
            print("NO")
            exit()

print("YES")

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

if len(a) == len(set(a)):
    print("YES")
else:
    print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    ans = 0

    for i in range(n - k + 1):
        ref = sum(p[i: i + k])
        if ref > ans:
            ans = ref

    print(ans/2 + k*0.5)

main()

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    ref = sum(p[:k])
    ans = ref

    for i in range(1, n - k + 1):
        ref = ref - p[i - 1] + p[i + k - 1]
        if ref > ans:
            ans = ref

    print(ans/2 + k*0.5)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    ans = 0

    for i in range(n - k + 1):
        ref = sum(p[i: i + k])/2 + k*0.5
        if ref > ans:
            ans = ref

    print(ans)

main()

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    ref = sum(p[:k])
    ans = ref

    for i in range(1, n - k + 1):
        ref = ref - p[i - 1] + p[i + k - 1]
        if ref > ans:
            ans = ref

    print(ans/2 + k*0.5)

main()

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0

for i in range(n - k + 1):
    ref = sum(p[i: i + k])/2 + k*0.5
    if ref > ans:
        ans = ref

print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    ref = sum(p[:k])
    ans = ref

    for i in range(1, n - k + 1):
        ref = ref - p[i - 1] + p[i + k - 1]
        if ref > ans:
            ans = ref

    print(ans/2 + k*0.5)

main()
Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
dp = [0]*20001

for i in range(1, h + 1):
    ref = 10**10
    for a, b in l:
        temp = dp[i - a] + b
        ref = min(ref, temp)
    dp[i] = ref

print(dp[h])

Fixed submission:
h, n = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
dp = [0]*20001

for i in range(1, h + 1):
    ref = 10**10
    for a, b in l:
        temp = dp[i - a] + b
        ref = min(ref, temp)
    dp[i] = ref

print(dp[h])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = list(map(int, input().split()))
ans = 0

for i in range(n):
    minp = min(p[:i + 1])
    if p[i] <= minp:
        ans += 1

print(ans)

Fixed submission:
n = int(input())
p = list(map(int, input().split()))
ans = 0
minp = p[0]


for i in range(n):
    if p[i] <= minp:
        ans += 1
        minp = p[i]

print(ans)
Buggy python submission (verdict: Runtime Error):
import fractions

a, b = map(int, input().split())

ans = a*b/math.gcd(a, b)
print(int(ans))

Fixed submission:
import fractions

a, b = map(int, input().split())

ans = a*b/fractions.gcd(a, b)
print(int(ans))

Buggy python submission (verdict: Runtime Error):
import math

a, b = map(int, input().split())

ans = a*b/math.gcd(a, b)
print(int(ans))

Fixed submission:
import fractions

a, b = map(int, input().split())

ans = a*b/fractions.gcd(a, b)
print(int(ans))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
ans = {}

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            ref = s[i] + s[j] + s[k]
            ans[ref] = 1

print(len(ans))

Fixed submission:
from itertools import product

n = int(input())
s = input()
ans = 0

for i in product(range(10), repeat = 3):
    a = s.find(str(i[0]))
    if a != -1 and a != n - 1:
        b = s[a + 1:].find(str(i[1]))
        if b != -1:
            b += a + 1
            if b != n - 1:
                c = s[b + 1:].find(str(i[2]))
                if c != -1:
                    ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    l = sorted(list(map(int, input().split())))
    ans = 0

    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            L = j
            R = n
            ij = l[i] + l[j]
            while R - L != 1:
                if ij <= l[j + 1]:
                    break
                now = (L + R)//2
                if ij > l[now]: #三角形になる
                    L = now
                else:
                    R = now
            ans += L - j

    print(ans)

main()

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    l = sorted(list(map(int, input().split())))
    ans = 0

    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            L = j
            R = n
            ij = l[i] + l[j]
            while R - L != 1:
                if ij <= l[j + 1]:
                    break
                now = (L + R)//2
                if ij > l[now]: #三角形になる
                    L = now
                else:
                    R = now
            ans += L - j

    print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        L = j
        R = n
        ij = l[i] + l[j]
        while R - L != 1:
            if ij <= l[j + 1]:
                break
            now = (L + R)//2
            if ij > l[now]: #三角形になる
                L = now
            else:
                R = now
        ans += L - j

print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    l = sorted(list(map(int, input().split())))
    ans = 0

    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            L = j
            R = n
            ij = l[i] + l[j]
            while R - L != 1:
                if ij <= l[j + 1]:
                    break
                now = (L + R)//2
                if ij > l[now]: #三角形になる
                    L = now
                else:
                    R = now
            ans += L - j

    print(ans)

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

for i in range(m):
    a = sorted(a)[::-1]
    a[0] //= 2

print(sum(a))

Fixed submission:
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))

for i in range(n):
    a[i] *= -1

heapq.heapify(a)

for i in range(m):
    ref = heapq.heappop(a)*-1
    ref //= 2
    heapq.heappush(a, -ref)

print(sum(a)*-1)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
s = input()
pre = s[0]
rsans = s[0]
first = s[0]

if s[0] == "R":
    second = "L"
else:
    second = "R"

for i in s[1:]:
    if i == second and k > 0:
        ans = ans + first
        pre = i
    elif i == first and pre == second:
        k -= 1
        ans = ans + i
        pre = i
    elif k == 0:
        ans = ans + i
    elif i == first and pre == first:
        ans = ans + i

pre = "0"
cnt = 0

for i in ans:
    if i == pre:
        cnt += 1
    pre = i

print(cnt)

Fixed submission:
n, k = map(int, input().split())
s = input()
pre = s[0]
ans = s[0]
first = s[0]

if s[0] == "R":
    second = "L"
else:
    second = "R"

for i in s[1:]:
    if i == second and k > 0:
        ans = ans + first
        pre = i
    elif i == first and pre == second:
        k -= 1
        ans = ans + i
        pre = i
    elif k == 0:
        ans = ans + i
    elif i == first and pre == first:
        ans = ans + i

pre = "0"
cnt = 0

for i in ans:
    if i == pre:
        cnt += 1
    pre = i

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = []
ans = 0

for i in range(n):
    a = sorted(input())
    l.append("".join(a))

sl = set(l)


for i in sl:
    com = l.count(i)
    ans += com*(com - 1)//2

print(ans)

Fixed submission:
n = int(input())
d = {}
ans = 0

for i in range(n):
    s = "".join(sorted(input()))
    if s in d:
        d[s] += 1
    else:
        d[s] = 1

for i in d.values():
    ans += i*(i - 1)//2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s)
l = [0]*n

for i in range(n):
    for j in range(1, n):
        if s[i] == "R":
            if s[i + j] == "L":
                if j%2 == 1:
                    l[i + j - 1] += 1
                else:
                    l[i + j] += 1
                break
        elif s[i] == "L":
            if s[i - j] == "R":
                if j%2 == 1:
                    l[i - j + 1] += 1
                else:
                    l[i - j] += 1
                break
print(*l)

Fixed submission:
s = input()
n = len(s)
l = [1]*n

for i in range(n - 1):
    if s[i] == s[i + 1] == "R":
        l[i + 2] += l[i]
        l[i] = 0
    if s[-i - 1] == s[-i - 2] == "L":
        l[-i - 3] += l[-i - 1]
        l[-i - 1] = 0

print(*l)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s)
l = [0]*n

for i in range(n):
    for j in range(1, n):
        if s[i] == "R":
            if s[i + j] == "L":
                if j%2 == 1:
                    l[i + j - 1] += 1
                else:
                    l[i + j] += 1
                break
        elif s[i] == "L":
            if s[i - j] == "R":
                if j%2 == 1:
                    l[i - j + 1] += 1
                else:
                    l[i - j] += 1
                break
print(*l)

Fixed submission:
s = input()
n = len(s)
l = [1]*n

for i in range(n - 1):
    if s[i] == s[i + 1] == "R":
        l[i + 2] += l[i]
        l[i] = 0
    if s[-i - 1] == s[-i - 2] == "L":
        l[-i - 3] += l[-i - 1]
        l[-i - 1] = 0

print(*l)
Buggy python submission (verdict: Runtime Error):
import math

def comb(n, r, mod):
    return math.factorial(n + r - 1)//(math.factorial(n - 1)*math.factorial(r))%mod

n, k = map(int, input().split())
mod = 10**9 + 7
red = n - k

for i in range(k):
    ans = 0
    redmod = red - i
    redplace = 2 + i
    bluemod = k - (i + 1)
    if i == 0:
        bluemod = 0
    blueplace = i + 1
    ans += comb(redplace, redmod, mod)*comb(blueplace, bluemod, mod)
    print(ans%mod)

Fixed submission:
import math

def comb(n, r, mod):
    return math.factorial(n + r - 1)//(math.factorial(n - 1)*math.factorial(r))%mod

n, k = map(int, input().split())
mod = 10**9 + 7
red = n - k

for i in range(k):
    ans = 0
    redmod = red - i
    if redmod < 0:
        print(0)
        continue
    redplace = 2 + i
    bluemod = k - (i + 1)
    if i == 0:
        bluemod = 0
    blueplace = i + 1
    ans += comb(redplace, redmod, mod)*comb(blueplace, bluemod, mod)
    print(ans%mod)
Buggy python submission (verdict: Runtime Error):
import math

a, b, c, d = map(int, input().split())
g = math.gcd(c, d)


t = b//c + b//d - b//(c*d//g)
l = (a - 1)//c + (a - 1)//d - (a - 1)//(c*d//g)
ans = b - (a - 1) - t + l

print(ans)

Fixed submission:
import fractions

a, b, c, d = map(int, input().split())
g = fractions.gcd(c, d)


t = b//c + b//d - b//(c*d//g)
l = (a - 1)//c + (a - 1)//d - (a - 1)//(c*d//g)
ans = b - (a - 1) - t + l

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
r, c = map(int, input().split())
ans = 0

map = []
for i in range(r):
    map.append(input())

L = [[0]*c for i in range(r)]
R = [[0]*c for i in range(r)]
D = [[0]*c for i in range(r)]
U = [[0]*c for i in range(r)]

for i in range(r):
    for j in range(c):
        if map[i][j] == ".":
            L[i][j] = L[i][j - 1] + 1
        else:
            L[i][j] = 0
for i in range(r):
    for j in range(c - 1, -1, -1):
        if j == c - 1:
            if map[i][j] == ".":
                R[i][j] = 1
            continue
        if map[i][j] == ".":
            R[i][j] = R[i][j + 1] + 1
        else:
            R[i][j] = 0
for i in range(r):
    for j in range(c):
        if map[i][j] == ".":
            D[i][j] = D[i - 1][j] + 1
        else:
            D[i][j] = 0
for i in range(r - 1, -1, -1):
    for j in range(c):
        if i == r - 1:
            if map[i][j] == ".":
                U[i][j] = 1
            continue
        if map[i][j] == ".":
            U[i][j] = U[i + 1][j] + 1
        else:
            U[i][j] = 0

for i in range(r):
    for j in range(c):
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

print(ans)

Fixed submission:
r, c = map(int, input().split())
ans = 0

map = []
for i in range(r):
    map.append(input())

L = [[0]*c for i in range(r)]
R = [[0]*c for i in range(r)]
D = [[0]*c for i in range(r)]
U = [[0]*c for i in range(r)]

for i in range(r):
    for j in range(c):
        if map[i][j] == ".":
            L[i][j] = L[i][j - 1] + 1
        else:
            L[i][j] = 0
for i in range(r):
    for j in range(c - 1, -1, -1):
        if j == c - 1:
            if map[i][j] == ".":
                R[i][j] = 1
            continue
        if map[i][j] == ".":
            R[i][j] = R[i][j + 1] + 1
        else:
            R[i][j] = 0
for i in range(r):
    for j in range(c):
        if map[i][j] == ".":
            D[i][j] = D[i - 1][j] + 1
        else:
            D[i][j] = 0
for i in range(r - 1, -1, -1):
    for j in range(c):
        if i == r - 1:
            if map[i][j] == ".":
                U[i][j] = 1
            continue
        if map[i][j] == ".":
            U[i][j] = U[i + 1][j] + 1
        else:
            U[i][j] = 0

for i in range(r):
    for j in range(c):
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    n, q = map(int, input().split())
    s = input()
    ll = [0]*n
    rl = [0]*n
    lr = []

    for i in range(n):
        ll[i] = s[:i + 1].count("AC")
        rl[i] = s[i:].count("AC")

    for i in range(q):
        l, r = map(int, input().split())
        l = max(l - 1, 0)
        lr.append([l , r - 1])

    for i, j in lr:
        ans = rl[0] - ll[i] - rl[j]
        print(ans)

main()

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    n, q = map(int, input().split())
    s = input()
    t = [0]*(n + 1)

    for i in range(n):
        if s[i: i + 2] == "AC":
            t[i + 1] = t[i] + 1
        else:
            t[i + 1] = t[i]
    
    for i in range(q):
        l, r = map(int, input().split())
        print(t[r - 1] - t[l - 1])

main()

Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
ll = [0]*n
rl = [0]*n
lr = []

for i in range(n):
    ll[i] = s[:i + 1].count("AC")
    rl[i] = s[i:].count("AC")

for i in range(q):
    l, r = map(int, input().split())
    l = max(l - 1, 0)
    lr.append([l , r - 1]) 



for i in range(q):
    ans = rl[0] - ll[lr[i][0]] - rl[lr[i][1]]
    print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    n, q = map(int, input().split())
    s = input()
    t = [0]*(n + 1)

    for i in range(n):
        if s[i: i + 2] == "AC":
            t[i + 1] = t[i] + 1
        else:
            t[i + 1] = t[i]
    
    for i in range(q):
        l, r = map(int, input().split())
        print(t[r - 1] - t[l - 1])

main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(set(map(int, input().split())))

    while max(a) - min(a) > 0:
        a.sort()
        a[-1] = a[-1]%a[0]
        if a[-1] == 0:
            del a[-1]

    print(min(a))

main()

Fixed submission:
import sys
import fractions
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int, input().split()))
    g = a[0]

    for i in range(1, n):
        g = fractions.gcd(g, a[i])
    
    print(g)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int, input().split()))

    while max(a) - min(a) > 0:
        a.sort()
        a[-1] = a[-1]%a[0]
        if a[-1] == 0:
            del a[-1]

    print(min(a))

main()

Fixed submission:
import sys
import fractions
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int, input().split()))
    g = a[0]

    for i in range(1, n):
        g = fractions.gcd(g, a[i])
    
    print(g)

main()

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

while max(a) - min(a) > 0:
    a.sort()
    a[-1] = a[-1]%a[0]
    if a[-1] == 0:
        del a[-1]

print(min(a))

Fixed submission:
import sys
import fractions
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int, input().split()))
    g = a[0]

    for i in range(1, n):
        g = fractions.gcd(g, a[i])
    
    print(g)

main()
Buggy python submission (verdict: Runtime Error):
 = int(input())
h = list(map(int, input().split()))

ans = 0
cnt = 0

for i in range(1, max(h) + 1)[::-1]:
    cnt = 0
    for j in range(n):
        if h[j] == i:
            h[j] -= 1
            cnt += 1
            if j + 1 < n:
                if h[j + 1] == i:
                    cnt -= 1
    ans += cnt

print(ans)

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

ans = 0
cnt = 0

for i in range(1, max(h) + 1)[::-1]:
    cnt = 0
    for j in range(n):
        if h[j] == i:
            h[j] -= 1
            cnt += 1
            if j + 1 < n:
                if h[j + 1] == i:
                    cnt -= 1
    ans += cnt

print(ans)