Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

s = input()

a = np.zeros(len(s)+1, dtype='i8')
res = 0
for i in range(len(s)):
    for k in range(i+4, len(s)+1):
        if int(s[i:k]) % 2019 == 0:
            res += a[i] + 1
            a[k] += 1
            break

print(res)


Fixed submission:
s = input()[::-1]

res = 0
cnt = {0: 1}
now = 0
p = 1
for i in range(len(s)):
    now = (now + (10 * p) * int(s[i])) % 2019
    cnt[now] = cnt.get(now, 0) + 1
    p = (p * 10) % 2019

print(sum(cnt[k] * (cnt[k] - 1) // 2 for k in cnt))

Buggy python submission (verdict: Time Limit Exceeded):
s = input()

res = 0
for i in range(len(s)):
    for k in range(i+4, len(s)+1):
        if int(s[i:k]) % 2019 == 0:
            res += 1

print(res)


Fixed submission:
s = input()[::-1]

res = 0
cnt = {0: 1}
now = 0
p = 1
for i in range(len(s)):
    now = (now + (10 * p) * int(s[i])) % 2019
    cnt[now] = cnt.get(now, 0) + 1
    p = (p * 10) % 2019

print(sum(cnt[k] * (cnt[k] - 1) // 2 for k in cnt))
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd

k = int(input())

res = 0
mul = [0, 1, 3, 6]
for a in range(1, k+1):
    for b in range(a, k+1):
        for c in range(b, k+1):
            res += gcd(gcd(a, b), c) * mul[len({a, b, c})]

print(res)

Fixed submission:
from math import gcd

k = int(input())

res = 0
mul = [0, 1, 3, 6]
for a in range(1, k+1):
    for b in range(a, k+1):
        for c in range(b, k+1):
            res += gcd(gcd(a, b), c) * mul[len({a, b, c})]

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
from math import gcd

k = int(input())

res = 0
for a, b, c in product(range(1, k+1), repeat=3):
    res += gcd(gcd(a, b), c)

print(res)


Fixed submission:
from math import gcd

k = int(input())

res = 0
mul = [0, 1, 3, 6]
for a in range(1, k+1):
    for b in range(a, k+1):
        for c in range(b, k+1):
            res += gcd(gcd(a, b), c) * mul[len({a, b, c})]

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

s = deque(input())
q = int(input())
for _ in range(q):
    query = input().split()
    if query[0] == '1':
        s.reverse()
    else:
        if query[1] == '1':
            s.appendleft(query[2])
        else:
            s.append(query[2])
print(''.join(s))


Fixed submission:
from collections import deque

is_reverse = False
s = deque(input())
q = int(input())
for _ in range(q):
    query = input().split()
    if query[0] == '1':
        is_reverse = not is_reverse
    else:
        if (not is_reverse and query[1] == '1') or (is_reverse and query[1] == '2'):
            s.appendleft(query[2])
        else:
            s.append(query[2])
print(''.join(s)[::-1]) if is_reverse else print(''.join(s))

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())
for _ in range(q):
    query = input().split()
    if query[0] == '1':
        s = s[::-1]
    else:
        if query[1] == '1':
            s = query[2] + s
        else:
            s = s + query[2]
print(s)


Fixed submission:
from collections import deque

is_reverse = False
s = deque(input())
q = int(input())
for _ in range(q):
    query = input().split()
    if query[0] == '1':
        is_reverse = not is_reverse
    else:
        if (not is_reverse and query[1] == '1') or (is_reverse and query[1] == '2'):
            s.appendleft(query[2])
        else:
            s.append(query[2])
print(''.join(s)[::-1]) if is_reverse else print(''.join(s))

Buggy python submission (verdict: Runtime Error):
s = input()
q = int(input())
for _ in range(q):
    query = input().split()
    if query[0] == '1':
        s = s[::-1]
    else:
        if query[1] == '1':
            s = query[2] + s
        else:
            s = s + query[2]
    print(s)


Fixed submission:
from collections import deque

is_reverse = False
s = deque(input())
q = int(input())
for _ in range(q):
    query = input().split()
    if query[0] == '1':
        is_reverse = not is_reverse
    else:
        if (not is_reverse and query[1] == '1') or (is_reverse and query[1] == '2'):
            s.appendleft(query[2])
        else:
            s.append(query[2])
print(''.join(s)[::-1]) if is_reverse else print(''.join(s))
Buggy python submission (verdict: Time Limit Exceeded):
n, p = [int(i) for i in input().split()]
s = input()

cnt = 0
for i in range(n):
    for k in range(i+1, n+1):
        if int(s[i:k]) % p == 0:
            cnt += 1

print(cnt)


Fixed submission:
n, p = map(int, input().split())
s = input()

res = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            res += i + 1
else:
    s = s[::-1]
    cnt = {0: 1}
    now = 0
    d = 1
    for i in range(n):
        now = (now + int(s[i]) * d) % p
        res += cnt.get(now, 0)
        d = (d * 10) % p
        cnt[now] = cnt.get(now, 0) + 1

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

cum = [0]
for i in range(1, n+1):
    cum.append(cum[i-1] + (p[i-1]+1)/2)

max = sum(p[:k])
idx = 0
for i in range(1, n-k+1):
    if max < sum(p[i:i+k]):
        max = sum(p[i:i+k])
        idx = i

print(cum[idx+k]-cum[idx])


Fixed submission:
n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

cum = [0]
for i in range(1, n+1):
    cum.append(cum[i-1] + (p[i-1]+1)/2)

res = 0
for i in range(0, n-k+1):
    val = cum[i+k] - cum[i]
    if res < val:
        res = val

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

mean = [0]
for i in range(1, 1001):
    mean.append(sum(range(1,i+1))/i)

cum = [0]
for i in range(1, n+1):
    cum.append(cum[i-1] + mean[p[i-1]])

max = sum(p[:k])
idx = 0
for i in range(1, n-k+1):
    if max < sum(p[i:i+k]):
        max = sum(p[i:i+k])
        idx = i

print(cum[idx+k]-cum[idx])


Fixed submission:
n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

cum = [0]
for i in range(1, n+1):
    cum.append(cum[i-1] + (p[i-1]+1)/2)

res = 0
for i in range(0, n-k+1):
    val = cum[i+k] - cum[i]
    if res < val:
        res = val

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

max = sum(p[:k])
idx = 0
for i in range(1, n-k+1):
    if max < sum(p[i:i+k]):
        max = sum(p[i:i+k])
        idx = i

result = 0
for i in range(k):
    result += sum(range(1,p[idx+i]+1))/p[idx+i]

print(result)


Fixed submission:
n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

cum = [0]
for i in range(1, n+1):
    cum.append(cum[i-1] + (p[i-1]+1)/2)

res = 0
for i in range(0, n-k+1):
    val = cum[i+k] - cum[i]
    if res < val:
        res = val

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
from sys import maxsize

h, n = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]

dp = [0] + [maxsize]*h
for a, b in m:
    for i in range(h+1):
        dp[min(i+a, h)] = min(dp[min(i+a, h)], dp[i]+b)
print(dp[h])


Fixed submission:
from sys import maxsize

h, n = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]

dp = [0] + [maxsize]*h
for a, b in m:
    for i in range(h+1):
        dp[min(i+a, h)] = min(dp[min(i+a, h)], dp[i]+b)
print(dp[h])
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from itertools import product

h, w = map(int, input().split())
s = np.full((h, w), 'x', dtype='U1')
for i in range(h):
    s[i] = list(input())

d = np.full((h*w, w*h), float('inf'))
for i in range(h * w):
    d[i, i] = 0

for i, k in product(range(h), range(w)):
    if s[i, k] == '#':
        continue
    for dy, dx in ((-1, 0), (0, -1), (0, 1), (1, 0)):
        y, x = i + dy, k + dx
        if y < 0 or h <= y or x < 0 or w <= x or s[y, x] == '#':
            continue
        d[i*w+k, y*w+x] = 1
        d[y*w+x, i*w+k] = 1

# warshall-floyd
for k, i, j in product(range(h * w), repeat=3):
    d[i, j] = min(d[i, j], d[i, k] + d[k, j])

print(d.astype('i8').max())


Fixed submission:
import numpy as np
from collections import deque
from itertools import product

H, W = map(int, input().split())
S = np.full((H, W), 'x', dtype='U1')
for i in range(H):
    S[i] = list(input())

def bfs(x, y):
    dist = np.full((H, W), -1, dtype='i8')
    que = deque()

    dist[x, y] = 0
    que.append((x, y))

    while que:
        h, w = que.popleft()
        d = dist[h, w]
        for dx, dy in ((0, -1), (-1, 0), (1, 0), (0, 1)):
            hh, ww = h + dx, w + dy
            if hh < 0 or H <= hh or ww < 0 or W <= ww or S[hh, ww] == '#' or dist[hh, ww] != -1:
                continue
            dist[hh, ww] = d + 1
            que.append((hh, ww))

    return d

res = 0
for i, k in product(range(H), range(W)):
    if S[i, k] == '#':
        continue
    d = bfs(i, k)
    if d > res:
        res = d
print(res)
Buggy python submission (verdict: Runtime Error):
import numpy as np

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

d_cumsum = np.zeros(60, dtype='i8')
for v in a:
    d_cumsum += np.array(list(map(int, list(format(v, '060b')))))

res = 0
mod = 10**9 + 7
for i, d in enumerate(reversed(d_cumsum)):
    res += (2**i * d * (n-d)) % mod
    res %= mod

print(res)

Fixed submission:
from itertools import count

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

d_cumsum = [0] * 60
for v in a:
    for i in count():
        d_cumsum[i] += v % 2
        v //= 2
        if v == 0:
            break

res = 0
mod = 10**9 + 7
for i, d in enumerate(d_cumsum):
    res += (2**i * d * (n-d)) % mod
    res %= mod

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import count

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

d_cumsum = [0] * 60
for v in a:
    for i in count():
        d_cumsum[i] += v % 2
        v //= 2
        if v == 0:
            break

res = 0
mod = 10**9 + 7
for i, d in enumerate(d_cumsum):
    res += (2**i * d * (n-d)) % mod
    res %= mod

print(res)


Fixed submission:
from itertools import count

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

d_cumsum = [0] * 60
for v in a:
    for i in count():
        d_cumsum[i] += v % 2
        v //= 2
        if v == 0:
            break

res = 0
mod = 10**9 + 7
for i, d in enumerate(d_cumsum):
    res += (2**i * d * (n-d)) % mod
    res %= mod

print(res)
Buggy python submission (verdict: Runtime Error):
days = ['SUN','MON','TUE','WED','THU','FRI','SAT']
S = input()
if days.get(S) == 0:
  print(7)
else:
  print(days.get(S))
    

Fixed submission:
days = ['SUN','MON','TUE','WED','THU','FRI','SAT']
S = input()
print(7-days.index(S))
Buggy python submission (verdict: Runtime Error):
from itertools import groupby

s = input()
k = int(input())

t = s * k
cont = [sum(1 for _ in it) for k, it in groupby(t)]

res = 0
for c in cont:
    if c != 1:
        res += c // 2

print(res)

Fixed submission:
from itertools import groupby

s = input()
k = int(input())

cont = [sum(1 for _ in it) for k, it in groupby(s)]

if len(cont) == 1:
    res = len(s) * k // 2
else:
    res = k-1 if s[0] == s[-1] and cont[0] % 2 == 1 and cont[-1] % 2 == 1 else 0
    for c in cont:
        if c != 1:
            res += c // 2 * k

print(res)
Buggy python submission (verdict: Runtime Error):
from fractions import gcd

def divisors(n, reverse=False):
    table = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            table.append(i)
            if i != n // i:
                table.append(n // i)
    table.sort(reverse=reverse)
    return table

def common_divisors(x, y, reverse=False):
    return divisors(gcd(x, y), reverse=reverse)

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

d = common_divisors(a, b)
MAX_VAL = d[-1]
prime = [1] * (MAX_VAL+1)
prime[0] = prime[1] = 0
for i in range(2, int(MAX_VAL**0.5)+1):
    if prime[i]:
        for k in range(2*i, MAX_VAL+1, i):
            prime[k] = 0

print(len([i for i in d if i == 1 or prime[i]]))


Fixed submission:
from fractions import gcd

def divisors(n, reverse=False):
    table = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            table.append(i)
            if i != n // i:
                table.append(n // i)
    table.sort(reverse=reverse)
    return table

def common_divisors(x, y, reverse=False):
    return divisors(gcd(x, y), reverse=reverse)


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

res = 0
for i in common_divisors(a, b):
    for k in range(2, int(i**0.5)+1):
        if i % k == 0:
            break
    else:
        res += 1
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
n, k, q = [int(i) for i in input().split()]
point = [k] * n
for _ in range(q):
    a = int(input())
    point = [p-1 if i != a-1 else p for i,p in enumerate(point)]
[print('Yes') if i > 0 else print('No') for i in point]


Fixed submission:
from collections import Counter

n, k, q = [int(i) for i in input().split()]
a = []
for i in range(q):
    a.append(int(input()))

c = Counter(a)
for i in range(1, n+1):
    print('Yes') if k-q+c[i] > 0 else print('No')
Buggy python submission (verdict: Time Limit Exceeded):
print(sum(range(1, int(input()))))

Fixed submission:
n = int(input())
print(n*(n-1)//2)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
from itertools import combinations

n = int(input())
s = []
for _ in range(n):
    s.append(input())

cnt = 0
for t, u in combinations(s, 2):
    if Counter(t) == Counter(u):
        cnt += 1

print(cnt)


Fixed submission:
from collections import Counter
from math import factorial

def count_combinations(n, r):
    return factorial(n) // (factorial(r) * factorial(n-r))

n = int(input())
s = []
for _ in range(n):
    s.append(input())

t = [''.join(sorted(str)) for str in s]
c = Counter(t)
ll = [i for _, i in c.items() if i > 1]
cnt = 0
for i in ll:
    cnt += count_combinations(i, 2)

print(cnt)
Buggy python submission (verdict: Runtime Error):
n = int(input())
h = [int(i) for i in input().split()]

h2 = [0] + h[:]
can = True
for i in range(1, n-1):
    if h2[i] <= h2[i+1]:
        continue
    elif h2[i]-1 > 0 and h2[i]-1 <= h2[i+i] and h2[i-1] <= h2[i]:
        h2[i] -= 1
    else:
        can = False
        break

print('Yes') if can else print('No')


Fixed submission:
n = int(input())
h = [int(i) for i in input().split()]

h2 = h[:]
can = True
for i in range(n-2, -1, -1):
    if h2[i] <= h2[i+1]:
        continue
    elif h2[i] > 1:
        h2[i] -= 1
    if not h2[i] <= h2[i+1]:
        can = False
        break

print('Yes') if can else print('No')
Buggy python submission (verdict: Time Limit Exceeded):
s = input()

mod = 10**9+7
n = len(s)
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    if s[i] == '?':
        for j in range(10):
            for k in range(13):
                dp[i+1][(k*10+j)%13] += dp[i][k]
    else:
        for k in range(13):
            dp[i+1][(k*10+int(s[i]))%13] += dp[i][k]
    for k in range(13):
        dp[i+1][k] %= mod
print(dp[n][5])


Fixed submission:
s = input()

mod = 10**9+7
n = len(s)
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    if s[i] == '?':
        for j in range(10):
            for k in range(13):
                dp[i+1][(k*10+j)%13] += dp[i][k]
    else:
        for k in range(13):
            dp[i+1][(k*10+int(s[i]))%13] += dp[i][k]
    for k in range(13):
        dp[i+1][k] %= mod
print(dp[n][5])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))

for _ in range(n):
    val = a.pop(0)
    print(max(a))
    a.append(val)


Fixed submission:
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))

desc = sorted(list(set(a)), reverse=True)
max = desc[0]
large_2 = desc[1] if len(desc) > 1 else 0

if a.count(max) == 1:
    for val in a:
        if val == max:
            print(large_2)
        else:
            print(max)
else:
    for _ in range(n):
        print(max)
Buggy python submission (verdict: Runtime Error):
from sys import maxsize
from itertools import combinations

l, r = [int(i) for i in input().split()]

min = maxsize
for i, k in combinations(range(l, r+1), 2):
    mod = i * k % 2019
    if mod < min:
        min = mod
    if mod == 0:
        break

print(min)


Fixed submission:
from sys import maxsize

l, r = [int(i) for i in input().split()]

min = maxsize
m = l
while m <= r:
    n = m + 1
    while n <= r:
        mod = m * n % 2019
        if mod < min:
            min = mod
        if mod == 0:
            break
        n += 1
    else:
        m += 1
        continue
    break

print(min)
Buggy python submission (verdict: Runtime Error):
n, m = [int(i) for i in input().split()]
a = []
broken = [False] * (n+1)
for _ in range(m):
    i = int(input())
    a.append(i)
    broken[i] = True

ways = [0] * 3
ways[1] = 0 if broken[1] else 1
ways[2] = 0 if broken[2] else ways[1] + 1
for i in range(3, n+1):
    if broken[i]:
        ways.append(0)
    else:
        ways.append((ways[-2]+ways[-1])%(10**9+7))

print(ways[n])


Fixed submission:
n, m = [int(i) for i in input().split()]
a = []
broken = [False] * max(n+1, 3)
for _ in range(m):
    i = int(input())
    a.append(i)
    broken[i] = True

ways = [0] * 3
ways[1] = 0 if broken[1] else 1
ways[2] = 0 if broken[2] else ways[1] + 1
for i in range(3, n+1):
    if broken[i]:
        ways.append(0)
    else:
        ways.append((ways[-2]+ways[-1])%(10**9+7))

print(ways[n])

Buggy python submission (verdict: Time Limit Exceeded):
n, m = [int(i) for i in input().split()]
a = []
for _ in range(m):
    a.append(int(input()))

ways = [0] * 3
ways[1] = 0 if 1 in a else 1
ways[2] = 0 if 2 in a else ways[1] + 1
for i in range(3, n+1):
    if i in a:
        ways.append(0)
    else:
        ways.append((ways[-2]+ways[-1])%(10**9+7))

print(ways[n])


Fixed submission:
n, m = [int(i) for i in input().split()]
a = []
broken = [False] * max(n+1, 3)
for _ in range(m):
    i = int(input())
    a.append(i)
    broken[i] = True

ways = [0] * 3
ways[1] = 0 if broken[1] else 1
ways[2] = 0 if broken[2] else ways[1] + 1
for i in range(3, n+1):
    if broken[i]:
        ways.append(0)
    else:
        ways.append((ways[-2]+ways[-1])%(10**9+7))

print(ways[n])

Buggy python submission (verdict: Runtime Error):
n, m = [int(i) for i in input().split()]
a = []
for _ in range(m):
    a.append(int(input()))

ways = [0] * 3
ways[1] = 0 if 1 in a else 1
ways[2] = 0 if 2 in a else ways[1] + 1
for i in range(3, n+1):
    if i in a:
        ways.append(0)
    else:
        ways.append((ways[-2]+ways[-1])%(10**9+7))
    print(ways)

print(ways[n])


Fixed submission:
n, m = [int(i) for i in input().split()]
a = []
broken = [False] * max(n+1, 3)
for _ in range(m):
    i = int(input())
    a.append(i)
    broken[i] = True

ways = [0] * 3
ways[1] = 0 if broken[1] else 1
ways[2] = 0 if broken[2] else ways[1] + 1
for i in range(3, n+1):
    if broken[i]:
        ways.append(0)
    else:
        ways.append((ways[-2]+ways[-1])%(10**9+7))

print(ways[n])
Buggy python submission (verdict: Time Limit Exceeded):
n, m = [int(i) for i in input().split()]
l = []
r = []
for _ in range(m):
    i, k = [int(i) for i in input().split()]
    l.append(i)
    r.append(k)

card = [0] * (n+1)
for i, j in zip(l, r):
    for k in range(i, j+1):
        card[k] += 1

print(card.count(m))


Fixed submission:
n, m = [int(i) for i in input().split()]
l = []
r = []
for _ in range(m):
    i, k = [int(i) for i in input().split()]
    l.append(i)
    r.append(k)

res = min(r) - max(l) + 1 if min(r) >= max(l) else 0
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import groupby
from math import ceil

n, k = map(int, input().split())
s = input()

block = [sum(1 for _ in it) for k, it in groupby(s)]
if s[0] != '1':
    block.insert(0, 0)

res = 0
for i in range(0, len(block), 2):
    res = max(sum(block[i:i+2*k+1]), res)
    if i+2*k+1 > n:
        break
print(res)


Fixed submission:
from itertools import groupby
from math import ceil

n, k = map(int, input().split())
s = input()

block = [sum(1 for _ in it) for k, it in groupby(s)]
if s[0] != '1':
    block.insert(0, 0)

m = len(block)
left, right = 0, 2*k
res = val = sum(block[left:right-1])
while right <= m:
    val += block[right-1] if right == m else block[right-1] + block[right]
    res = max(res, val)
    val -= block[left] + block[left+1]
    left += 2
    right += 2
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

p = [i + k for i, k in product(a, b)]
p.sort(reverse=True)
q = [i + k for i, k in product(p[:k], c)]
q.sort(reverse=True)

print('\n'.join(map(str, q[:k])))


Fixed submission:
from itertools import product

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

p = [i + k for i, k in product(a, b)]
p.sort(reverse=True)
q = [i + k for i, k in product(p[:k], c)]
q.sort(reverse=True)
print('\n'.join(map(str, q[:k])))
Buggy python submission (verdict: Time Limit Exceeded):
n, q = [int(i) for i in input().split()]
s = input()
l = []
r = []
for _ in range(q):
    i, k = [int(i) for i in input().split()]
    l.append(i)
    r.append(k)

for i, k in zip(l, r):
    print(s[i-1:k].count('AC'))


Fixed submission:
n, q = [int(i) for i in input().split()]
s = input()
l = []
r = []
for _ in range(q):
    i, k = [int(i) for i in input().split()]
    l.append(i)
    r.append(k)

cum_sum = [0]
for i in range(n-1):
    if s[i:i+2] == 'AC':
        cum_sum.append(cum_sum[-1]+1)
    else:
        cum_sum.append(cum_sum[-1])
else:
    cum_sum.append(cum_sum[-1])

for i, k in zip(l, r):
    print(cum_sum[k-1] - cum_sum[i-1])
Buggy python submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        if self.parents[x] > self.parents[y]:
            rx, ry = ry, rx
        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx

    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    def size(self, x):
        return -self.parents[self.root(x)]


n, m = map(int, input().split())
bridges = [tuple((int(i)-1 for i in input().split())) for _ in range(m)]
islands = UnionFind(n)
res = [n*(n-1)//2]
for a, b in bridges[:0:-1]:
    if islands.same(a, b):
        res.append(res[-1])
    else:
        res.append(res[-1] - islands.size(a) * islands.size(b))
        islands.unite(a, b)
print('\n'.join(map(str, res[::-1])))


Fixed submission:
import sys

sys.setrecursionlimit(10**5)


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        if self.parents[x] > self.parents[y]:
            rx, ry = ry, rx
        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx

    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    def size(self, x):
        return -self.parents[self.root(x)]


n, m = map(int, input().split())
bridges = [tuple((int(i)-1 for i in input().split())) for _ in range(m)]
islands = UnionFind(n)
res = [n*(n-1)//2]
for a, b in bridges[:0:-1]:
    if islands.same(a, b):
        res.append(res[-1])
    else:
        res.append(res[-1] - islands.size(a) * islands.size(b))
        islands.unite(a, b)
print('\n'.join(map(str, res[::-1])))