Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
slist = []
for i in range(N):
    slist.append(sorted(list(input())))
count = [0 for i in range(N)]
c = []
answer = 0
for i in range(N):
    d = 0
    for j in range(len(c)):
        if slist[i] == c[j]:
            count[j] += 1
            answer += count[j]
            d = 1
    if d == 0:
        c.append(slist[i])
print(answer)

Fixed submission:
N = int(input())
ssorted = []
for i in range(N):
    ssorted.append("".join(sorted(list(input()))))
sdict = {}
for i in ssorted:
    if i in sdict:
        sdict[i] += 1
    else:
        sdict[i] = 1
count = 0
for i in sdict:
    s = sdict[i]
    if s >= 2:
        count += s*(s-1)//2
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
slist = []
for i in range(N):
    slist.append(sorted(list(input())))
count = [0 for i in range(N)]
c = []
c.append(slist[0])
for i in range(N):
    d = 0
    for j in range(len(c)):
        if slist[i] == c[j]:
            count[j] += 1
            d = 1
    if d == 0:
        c.append(slist[i])
count[0] -= 1
def counting(n):
    if n == 0:
        return 0
    else:
        return n*(n+1)//2
sum = 0
for i in range(N):
    sum += counting(count[i])
print(sum)

Fixed submission:
N = int(input())
ssorted = []
for i in range(N):
    ssorted.append("".join(sorted(list(input()))))
sdict = {}
for i in ssorted:
    if i in sdict:
        sdict[i] += 1
    else:
        sdict[i] = 1
count = 0
for i in sdict:
    s = sdict[i]
    if s >= 2:
        count += s*(s-1)//2
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N, M = map(int,input().split())
A = [0 for i in range(N)]
B = [0 for i in range(N)]
for i in range(N):
    A[i], B[i] = map(int,input().split())
ptj = {}
for i in range(N):
    if A[i] in ptj:
        ptj[A[i]].append(-B[i])
    else:
        ptj[A[i]] = [-B[i]]
count = 0
s = []
for i in range(1,M+1):
    if i in ptj:
        s.extend(ptj[i])
        heapq.heapify(s)
    if s != []:
        count -= heapq.heappop(s)
print(count)

Fixed submission:
import heapq
N, M = map(int,input().split())
A = [0 for i in range(N)]
B = [0 for i in range(N)]
for i in range(N):
    A[i], B[i] = map(int,input().split())
ptj = {}
for i in range(N):
    if A[i] in ptj:
        ptj[A[i]].append(-B[i])
    else:
        ptj[A[i]] = [-B[i]]
count = 0
s = []
for i in range(1,M+1):
    if i in ptj:
        for j in ptj[i]:
            heapq.heappush(s,j)
    if s != []:
        count -= heapq.heappop(s)
print(count)
Buggy python submission (verdict: Runtime Error):
import math
a, b, c, d = map(int, input().split())
div_c = b//c + (-a//c) + 1
div_d = b//d + (-a//d) + 1
div_cd = b//(c*d//math.gcd(c, d)) + (-a//(c*d//math.gcd(c,d))) + 1
print(b-a+1 - div_c - div_d + div_cd)


Fixed submission:
import fractions
a, b, c, d = map(int, input().split())
div_c = b//c + (-a//c) + 1
div_d = b//d + (-a//d) + 1
div_cd = b//(c*d//fractions.gcd(c, d)) + (-a//(c*d//fractions.gcd(c,d))) + 1
print(b-a+1 - div_c - div_d + div_cd)
Buggy python submission (verdict: Runtime Error):
n, x = map(int, input().split())
l = list(map(int,input().split()))
pos = 0
count = 0
i=0
while pos <= x and i <= n:
    pos += l[i]
    count += 1
    i += 1
print(count)

Fixed submission:
n, x = map(int, input().split())
l = list(map(int,input().split()))
pos = 0
count = 0
i=0
while pos <= x and i < n:
    pos += l[i]
    count += 1
    i += 1
if i == n and pos <= x:
    count += 1
print(count)
Buggy python submission (verdict: Runtime Error):
import sys
n,m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
fib = [1,1]
for i in range(n):
    fib.append((fib[i]+fib[i+1])%1000000007)
if m == 0:
	print(fib[n])
    sys.exit()
answer = fib[a[0]-1]
for i in range(m-1):
    if a[i] + 1 == a[i+1]:
        answer = 0
    else:
        answer = answer * fib[a[i+1]-a[i]-2] % 1000000007
answer = answer * fib[n-a[m-1]-1] % 1000000007
print(answer)

Fixed submission:
p,q,r = map(int, input().split())
print(min(p+q,q+r,r+p))
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int,input().split())
s = {}
for i in range(m):
    l, r = map(int,input().split())
    if i == 0:
        s = set(range(l,r+1))
    else:
        s = set(range(l, r+1)) & s
print(len(s))

Fixed submission:
import heapq
n, m = map(int,input().split())
l = []
r = []
for i in range(m):
    line = list(map(int,input().split()))
    l.append(-line[0])
    r.append(line[1])
heapq.heapify(l)
heapq.heapify(r)
l_max = - heapq.heappop(l)
r_min = heapq.heappop(r)
if l_max > r_min:
    print(0)
else:
    print(r_min-l_max+1)
Buggy python submission (verdict: Runtime Error):
n, m = map(int,input().split())
a = list(map(int,input().split()))
rewrite = []
for i in range(m):
    rewrite.append(list(map(int,input().split())))
rewrite.sort(key= lambda x : x[1], reverse=True)
a.sort()
k = 0
flag = 0
for i in range(min(n,sum(rewrite[0]))):
    for j in range(rewrite[i][0]):
        if rewrite[i][1] > a[k]:
            a[k] = rewrite[i][1]
            k += 1
        else:
            flag = 1
            break
    if flag == 1:
        break
print(sum(a))


Fixed submission:
n, m = map(int,input().split())
a = list(map(int,input().split()))
rewrite = []
for i in range(m):
    rewrite.append(list(map(int,input().split())))
rewrite.sort(key= lambda x : x[1], reverse=True)
a.sort()
k = 0
flag = 0
for i in range(m):
    for j in range(rewrite[i][0]):
        if rewrite[i][1] > a[k]:
            a[k] = rewrite[i][1]
            k += 1
            if k == n:
                flag = 1
                break
        else:
            flag = 1
            break
    if flag == 1:
        break
print(sum(a))
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = list(input())
l = []
r = []
for _ in range(q):
    line = list(map(int, input().split()))
    l.append(line[0])
    r.append(line[1])
acgt = []
for i in range(1, n):
    if s[i-1] == "A" and s[i] == "C":
        acgt.append(1)
    else:
        acgt.append(0)
for i in range(q):
    print(sum(acgt[l[i]-1:r[i]-1]))

Fixed submission:
n, q = map(int, input().split())
s = list(input())
l = []
r = []
for _ in range(q):
    line = list(map(int, input().split()))
    l.append(line[0])
    r.append(line[1])
ac = []
count = 0
for i in range(1, n):
    if s[i-1] == "A" and s[i] == "C":
        count += 1
    ac.append(count)
for i in range(q):
    right = ac[r[i]-2]
    if l[i] < 2:
        left = 0
    else:
        left = ac[l[i]-2]
    print(right-left)
Buggy python submission (verdict: Runtime Error):
import math

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

x = c * d // math.gcd(c, d)

t1 = b // c
t2 = (a - 1) // c
u1 = b // d
u2 = (a - 1) // d
v1 = b // x
v2 = (a - 1) // x

ans = (b - a + 1) - (t1 - t2) - (u1 - u2) + (v1 - v2)
print(ans)

Fixed submission:
def gcd(x, y):
  if y == 0:
    return x
  else:
    x %= y
    x, y = y, x
    return gcd(x, y)

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

x = c * d // gcd(c, d)

t1 = b // c
t2 = (a - 1) // c
u1 = b // d
u2 = (a - 1) // d
v1 = b // x
v2 = (a - 1) // x

ans = (b - a + 1) - (t1 - t2) - (u1 - u2) + (v1 - v2)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import fractions


k = int(input())

def gcd(p, q):
    if p % q == 0: return q
    return gcd(q, p % q)

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



Fixed submission:
import fractions


k = int(input())

def gcd(p, q):
    if p % q == 0: return q
    return gcd(q, p % q)

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

Buggy python submission (verdict: Time Limit Exceeded):
import fractions


k = int(input())
cache = dict()

def gcd(l):
    if tuple(sorted(l)) in cache:
        return cache[tuple(sorted(l))]
    ans = l[0]
    for i in range(1, len(l)):
        ans = fractions.gcd(ans, l[i])
    cache[tuple(sorted(l))] = ans
    return ans

res = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            res += gcd([a, b, c])
print(res)



Fixed submission:
import fractions


k = int(input())

def gcd(p, q):
    if p % q == 0: return q
    return gcd(q, p % q)

res = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            res += gcd(gcd(a, b), c)
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
w_l = [input() for _ in range(n)]

d = {}

max_v = 0
for w in w_l:
    if d.get(w, 0) == 0:
        d[w] = 1
    else:
        d[w] += 1

max_k_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]

max_k_list.sort()

for k in max_k_list:
    print(k)




Fixed submission:
import collections


n = int(input())
w_l = [input() for _ in range(n)]

counter = collections.Counter(w_l)

c_l = counter.most_common()
max_v = c_l[0][1]
ans_l = []
for i in range(len(c_l)):
    word, num = c_l[i]
    if max_v != num:
        break
    ans_l.append(word)

ans_l.sort()
for ans in ans_l:
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
w_l = [input() for _ in range(n)]

d = {}

for w in w_l:
    if d.get(w, 0) == 0:
        d[w] = 1
    else:
        d[w] += 1

max_k_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]

max_k_list.sort()
for k in max_k_list:
    print(k)




Fixed submission:
import collections


n = int(input())
w_l = [input() for _ in range(n)]

counter = collections.Counter(w_l)

c_l = counter.most_common()
max_v = c_l[0][1]
ans_l = []
for i in range(len(c_l)):
    word, num = c_l[i]
    if max_v != num:
        break
    ans_l.append(word)

ans_l.sort()
for ans in ans_l:
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))

ans = 0

def expect(n):
    res = 0
    for i in range(1, n+1):
        res += i
    res /= n
    return res

p = list(map(expect, p))

for i in range(n-k+1):
    target = p[i:i+k]
    ans = max(ans, sum(target))

print(ans)






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


def expect(n):
    res = (n + 1) / 2
    return res

p = list(map(expect, p))
ans_sum = sum(p[:k])
tmp_sum = ans_sum
idx = 0

for i in range(k, n):
    tmp_sum = tmp_sum + p[i] - p[i-k]
    if tmp_sum > ans_sum:
        ans_sum = tmp_sum

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

for i in range(1, n+1):
    print(A.index(i) + 1, end=" ")



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

ans = [0] * n

for i in range(n):
    s = A[i]
    ans[s-1] = i+1
print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

ans = 0
for i in range(n):
    ans += i
print(ans)



Fixed submission:
n = int(input())

print(n * (n - 1) // 2)

Buggy python submission (verdict: Runtime Error):
n = int(input())

ans = 0
for i in range(len(n)):
  ans += i
  
print(ans)

Fixed submission:
n = int(input())

print(n * (n - 1) // 2)
Buggy python submission (verdict: Runtime Error):
# グラフ木累積和
n, q = map(int, input().split())
tree = [[] for _ in range(n)]
ans = [0] * n

for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

for _ in range(q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x

def dfs(v, p=-1):
    for u in tree[v]:
        # 親には戻らないようにする
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)

dfs(0)
print(*ans)



Fixed submission:
import collections

n, q = map(int, input().split())
cnt = [0] * (n + 1)

# adjacency list for tree graph
g = [[] for _ in range(n + 1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

# calc cnt
for _ in range(q):
    v, val = map(int, input().split())
    cnt[v] += val

q = collections.deque()
q.append(1)
checked = [0] * (n + 1)

while q:
    v = q.pop()
    checked[v] = 1
    for u in g[v]:
        if checked[u] == 1:
            continue
        cnt[u] += cnt[v]
        q.append(u)
print(*cnt[1:])
Buggy python submission (verdict: Runtime Error):
from scipy.special import comb

n = int(input())
S = [input() for _ in range(n)]
S_sorted = ["".join(sorted(s)) for s in S]
S_sorted = sorted(S_sorted)

ans = 0
cnt = 1
for i in range(1, len(S_sorted)):
    if S_sorted[i] == S_sorted[i-1]:
        cnt += 1
    else:
        ans += comb(cnt, 2, exact=True)
        cnt = 1

if cnt > 1:
    ans += comb(cnt, 2, exact=True)

print(ans)






Fixed submission:
def cmb(n, r):
    if n == 1: return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n = int(input())
S = [input() for _ in range(n)]
S_sorted = ["".join(sorted(s)) for s in S]
S_sorted = sorted(S_sorted)

ans = 0
cnt = 1
for i in range(1, len(S_sorted)):
    if S_sorted[i] == S_sorted[i-1]:
        cnt += 1
    else:
        ans += cmb(cnt, 2)
        cnt = 1

if cnt > 1:
    ans += cmb(cnt, 2)

print(int(ans))

Buggy python submission (verdict: Runtime Error):
from scipy.special import comb

n = int(input())
S = [input() for _ in range(n)]
S_sorted = ["".join(sorted(s)) for s in S]
S_sorted = sorted(S_sorted)

ans = 0
cnt = 1
for i in range(1, len(S_sorted)):
    if S_sorted[i] == S_sorted[i-1]:
        cnt += 1
    else:
        ans += comb(cnt, 2, exact=True)
        cnt = 1

if cnt > 1:
    ans += comb(cnt, 2, exact=True)

print(ans)






Fixed submission:
def cmb(n, r):
    if n == 1: return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n = int(input())
S = [input() for _ in range(n)]
S_sorted = ["".join(sorted(s)) for s in S]
S_sorted = sorted(S_sorted)

ans = 0
cnt = 1
for i in range(1, len(S_sorted)):
    if S_sorted[i] == S_sorted[i-1]:
        cnt += 1
    else:
        ans += cmb(cnt, 2)
        cnt = 1

if cnt > 1:
    ans += cmb(cnt, 2)

print(int(ans))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(input()) for _ in range(n)]
max_a = max(a)
tmp_a = a.copy()
count = 0
for i in range(n):
    if tmp_a[i] == max_a:
        count += 1

if count == 1:
    for i in range(len(a)):
        tmp_a = a.copy()
        if tmp_a[i] == max_a:
            del tmp_a[i]
            print(max(tmp_a))
        else:
            print(max_a)
else:
    for i in range(len(a)):
        print(max_a)



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

sorted_a = sorted(a)
first_a = sorted_a[-1]
second_a = sorted_a[-2]

for i in range(len(a)):
    if a[i] == first_a:
        print(second_a)
    else:
        print(first_a)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(input()) for _ in range(n)]
max_a = max(a)
for i in range(len(a)):
    tmp_a = a.copy()
    if tmp_a[i] == max_a:
        del tmp_a[i]
        print(max(tmp_a))
    else:
        print(max_a)



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

sorted_a = sorted(a)
first_a = sorted_a[-1]
second_a = sorted_a[-2]

for i in range(len(a)):
    if a[i] == first_a:
        print(second_a)
    else:
        print(first_a)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(input()) for _ in range(n)]

for i in range(len(a)):
    tmp_a = a.copy()
    del tmp_a[i]
    print(max(tmp_a))



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

sorted_a = sorted(a)
first_a = sorted_a[-1]
second_a = sorted_a[-2]

for i in range(len(a)):
    if a[i] == first_a:
        print(second_a)
    else:
        print(first_a)
Buggy python submission (verdict: Runtime Error):
n = int(input())
l = list(map(int, input().split()))
 
ans = 0
for i in range(1, n - 1):
  if l[i - 1] < l[i] and l[i] < l[i + 1]:
    ans += 1
  elif l[i + 1] < l[i] and l[i] < l[i - 1]:
 	ans += 1
print(ans)

Fixed submission:
n = int(input())
l = list(map(int, input().split()))
 
ans = 0
for i in range(1, n - 1):
  if l[i - 1] < l[i] and l[i] < l[i + 1]:
    ans += 1
  elif l[i + 1] < l[i] and l[i] < l[i - 1]:
    ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
l = list(map(int, input().split()))

c_idx = n / 2 - 1
l.sort()
print(l[c_idx + 1] - l[c_idx])

Fixed submission:
n = int(input())
l = list(map(int, input().split()))
 
c_idx = n // 2 - 1
l.sort()
print(l[c_idx + 1] - l[c_idx])
Buggy python submission (verdict: Runtime Error):
n, k = list(map(int, input().split()))


from functools import reduce
from operator import mul

def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    # なんでn + 1じゃないのか？
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

TEISU = 10 ** 9 + 7

for i in range(k):
    print(int(cmb(n - k + 1, i + 1) * cmb(k - 1, i)) % TEISU)



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


from functools import reduce
from operator import mul

def cmb(n, r):
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    # なんでn + 1じゃないのか？
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

TEISU = 10 ** 9 + 7

for i in range(k):
    print(int(cmb(n - k + 1, i + 1) * cmb(k - 1, i)) % TEISU)

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


from functools import reduce
from operator import mul

def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    # なんでn + 1じゃないのか？
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

TEISU = 10 ** 9 + 7

for i in range(k):
    print(int(cmb(n - k + 1, i + 1) * cmb(k - 1, i)) % TEISU)



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


from functools import reduce
from operator import mul

def cmb(n, r):
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    # なんでn + 1じゃないのか？
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

TEISU = 10 ** 9 + 7

for i in range(k):
    print(int(cmb(n - k + 1, i + 1) * cmb(k - 1, i)) % TEISU)

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

def kaijou(a):
    ret = 1
    for i in range(a):
        ret *= i + 1
    return ret


def comb(n, k):
    if k == 0:
        return 1

    return kaijou(n) / (kaijou(k) * kaijou(n - k))

TEISU = 10 ** 9 + 7

for i in range(k):
    print(int(comb(n - k + 1, i + 1) * comb(k - 1, i)) % TEISU)


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


from functools import reduce
from operator import mul

def cmb(n, r):
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    # なんでn + 1じゃないのか？
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

TEISU = 10 ** 9 + 7

for i in range(k):
    print(int(cmb(n - k + 1, i + 1) * cmb(k - 1, i)) % TEISU)
Buggy python submission (verdict: Runtime Error):
import math


a, b, c, d = list(map(int, input().split()))

def lcm(x, y):
    return x * y // math.gcd(x, y)

def get_num(x):
    ans = x - x // c - x // d + x // lcm(c, d)
    return ans


print(get_num(b) - get_num(a -1))


Fixed submission:
import fractions


a, b, c, d = list(map(int, input().split()))

def lcm(x, y):
    return x * y // fractions.gcd(x, y)

def get_num(x):
    ans = x - x // c - x // d + x // lcm(c, d)
    return ans


print(get_num(b) - get_num(a -1))
Buggy python submission (verdict: Time Limit Exceeded):
n, m = list(map(int, input().split()))
a = [int(input()) for _ in range(m)]


f = []

for i in range(n + 1):
    if i == 0:
        f.append(1)
        continue
    if i in a:
        f.append(0)
        continue
    if i == 1:
        f.append(1)
        continue
    f.append(f[i - 1] + f[i - 2])
    
print(f[n] % 1000000007)


Fixed submission:
n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
NUM = 10 ** 9 + 7

dp = [0] * (n+1)
dp[0] = 1
if not 1 in a:
    dp[1] = 1

for i in range(2, n+1):
    if not i in a:
        dp[i] = (dp[i-2] + dp[i-1]) % NUM
    else:
        dp[i] = 0

print(dp[n])
Buggy python submission (verdict: Time Limit Exceeded):
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
cnt = [[0] * w for _ in range(h)]

def rotate(l_2d):
    l_2d = np.array(l_2d)
    return (l_2d.T).tolist()


# check horizontal direction(done)
done = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if done[i][j] == 1 or s[i][j] == "#":
            continue
        l = 0
        k = j
        while k < w:
            if s[i][k] == ".":
                l += 1
            else:
                break
            k += 1
        for o in range(l):
            cnt[i][j+o] += l
            done[i][j+o] = 1


# check vertical direction
done = [[0] * w for _ in range(h)]
for j in range(w):
    for i in range(h):
        if done[i][j] == 1 or s[i][j] == "#":
            continue
        l = 0
        k = i
        while k < h:
            if s[k][j] == ".":
                l += 1
            else:
                break
            k += 1
        for o in range(l):
            cnt[i+o][j] += l
            done[i+o][j] = 1

print(max(list(map(max, cnt))) - 1)



Fixed submission:
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
cnt = [[0] * w for _ in range(h)]

def rotate(l_2d):
    l_2d = np.array(l_2d)
    return (l_2d.T).tolist()


# check horizontal direction(done)
done = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if done[i][j] == 1 or s[i][j] == "#":
            continue
        l = 0
        k = j
        while k < w:
            if s[i][k] == ".":
                l += 1
            else:
                break
            k += 1
        for o in range(l):
            cnt[i][j+o] += l
            done[i][j+o] = 1


# check vertical direction
done = [[0] * w for _ in range(h)]
for j in range(w):
    for i in range(h):
        if done[i][j] == 1 or s[i][j] == "#":
            continue
        l = 0
        k = i
        while k < h:
            if s[k][j] == ".":
                l += 1
            else:
                break
            k += 1
        for o in range(l):
            cnt[i+o][j] += l
            done[i+o][j] = 1

print(max(list(map(max, cnt))) - 1)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
ls = []
rs = []

for _ in range(m):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)

l_max = max(l)
r_min = min(r)
master_card_num = r_min - l_max

if master_card_num < 0:
    print(0)
else:
    print(master_card_num + 1)

Fixed submission:
n, m = map(int, input().split())
ls = []
rs = []

for _ in range(m):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)

l_max = max(ls)
r_min = min(rs)
master_card_num = r_min - l_max

if master_card_num < 0:
    print(0)
else:
    print(master_card_num + 1)