Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
h, w = list(map(int, input().split() ))

s = []
s.append("." * (w+2)) 
for _ in range(h):
	s.append("." + input() + ".")
s.append("." * (w+2)) 

ans = "Yes"
dx = [-1, 0, 1, 0]
dy = [ 0, 1, 0,-1]

for i in range(1, h+1):
	for j in range(1, h+1):
		if s[i][j] == "#":
			CanPaint = False
			for k in range(4):
				if s[i+dx[k]][j+dy[k]] == "#":
					CanPaint = True
			if not CanPaint:
				ans = "No"

print(ans)


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

s = []
s.append("." * (w+2)) 
for _ in range(h):
	s.append("." + input() + ".")
s.append("." * (w+2)) 

ans = "Yes"
dx = [-1, 0, 1, 0]
dy = [ 0, 1, 0,-1]

for i in range(1, h+1):
	for j in range(1, w+1):
		if s[i][j] == "#":
			CanPaint = False
			for k in range(4):
				if s[i+dx[k]][j+dy[k]] == "#":
					CanPaint = True
			if not CanPaint:
				ans = "No"

print(ans)

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

s = []
s.append("." * (w+2)) 
for _ in range(h):
	s.append("." + input() + ".")
s.append("." * (w+2)) 

ans = "Yes"
dx = [-1, 0, 1, 0]
dy = [ 0, 1, 0,-1]

for i in range(1, h+1):
	for j in range(1, h+1):
		if s[i][j] == "#":
			CanPaint = False
			for k in range(4):
				if s[i+dx[k]][j+dy5 5
#.#.#
.#.#.
#.#.#
.#.#.
#.#.#[k]] == "#":
					CanPaint = True
			if not CanPaint:
				ans = "No"

print(ans)


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

s = []
s.append("." * (w+2)) 
for _ in range(h):
	s.append("." + input() + ".")
s.append("." * (w+2)) 

ans = "Yes"
dx = [-1, 0, 1, 0]
dy = [ 0, 1, 0,-1]

for i in range(1, h+1):
	for j in range(1, w+1):
		if s[i][j] == "#":
			CanPaint = False
			for k in range(4):
				if s[i+dx[k]][j+dy[k]] == "#":
					CanPaint = True
			if not CanPaint:
				ans = "No"

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# 最も単純にやると
# 盤面の移動のしかたはN^2通り
# それぞれに対して、対称行列かの判定はO(N^2)個の条件を確認する必要がある
# したがってO(N^4)である。間に合わない。
# しかし、対称行列であれば、1行1列を右下に移動しても対称行列である。
# これより、行またはだけを移動した場合について確認すれば良い。O(N^3)。

n = int(input())
masume = [input() for i in range(n)]

count = 0
for diff in range(n):
    flag = True
    for i in range(n):
        for j in range(i+1, n):
            if masume[(i+diff)%n][j] != masume[(j+diff)%n][i]:
                flag = False
                break
        if not flag:
            break
    count += flag

print(count * n)


Fixed submission:
# 最も単純にやると
# 盤面の移動のしかたはN^2通り
# それぞれに対して、対称行列かの判定はO(N^2)個の条件を確認する必要がある
# したがってO(N^4)である。間に合わない。
# しかし、対称行列であれば、1行1列を右下に移動しても対称行列である。
# これより、行またはだけを移動した場合について確認すれば良い。O(N^3)。

n = int(input())
masume = [input() for i in range(n)]

count = 0
for diff in range(n):
    flag = True
    for i in range(n):
        for j in range(i+1, n):
            if masume[(i+diff)%n][j] != masume[(j+diff)%n][i]:
                flag = False
                break
        if not flag:
            break
    count += flag

print(count * n)
Buggy python submission (verdict: Runtime Error):
n, a, b = list(map(int(), input().split()))
print("Borys" if (b - a) % 2 == 1 else "Alice")

Fixed submission:
n, a, b = list(map(int, input().split()))
print("Borys" if (b - a) % 2 == 1 else "Alice")
Buggy python submission (verdict: Time Limit Exceeded):
n, c = list(map(int, input().split()))

s = [0] * n
t = [0] * n
chan = [0] * n
for i in range(n):
    s[i], t[i], chan[i] = list(map(int, input().split()))

length_double = 2 * (max(t)+1)

recording_num = [0] * length_double
# tt = [0] * length_double
for i in range(1, c+1):
    tt = [0] * length_double

    for j in range(n):
        if chan[j] == i:
            tt[s[j]*2-1] += 1
            tt[t[j]*2] -= 1
    
    for j in range(1, length_double):
        tt[j] += tt[j-1]
    for j in range(length_double):
        if tt[j] > 0:
            recording_num[j] += 1
    # print(tt)

ans = max(recording_num)
print(ans)
# print(recording_num)



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

s = [0] * n
t = [0] * n
chan = [0] * n
for i in range(n):
    s[i], t[i], chan[i] = list(map(int, input().split()))

length_double = 2 * (max(t)+1)

recording_num = [0] * length_double
# tt = [0] * length_double
for i in range(1, c+1):
    tt = [0] * length_double

    for j in range(n):
        if chan[j] == i:
            tt[s[j]*2-1] += 1
            tt[t[j]*2] -= 1
    
    for j in range(1, length_double):
        tt[j] += tt[j-1]
    for j in range(length_double):
        if tt[j] > 0:
            recording_num[j] += 1
    # print(tt)

ans = max(recording_num)
print(ans)
# print(recording_num)
Buggy python submission (verdict: Time Limit Exceeded):
n, x0, y0 = list(map(int, input().split()))

cards = [y0] + list(map(int, input().split()))
# yの手持ちはゲームに関与するため、リストに加えてしまう

xs = [[-1] * (n+1) for i in range(n+1)]
ys = [[-1] * (n+1) for i in range(n+1)] 
#xs[i][j] = xの手番で、xがcards[i]を持ちyがcards[j]を持っているとき(i<j)の最善スコア
#ys[i][j] = yの手番で、xがcards[j]を持ちyがcards[i]を持っているとき(i<j)の最善スコア

for i in range(n+1):
	xs[i][-1] = abs(cards[-1] - cards[i])
	ys[i][-1] = abs(cards[-1] - cards[i])

for j in range(n-1, -1, -1):

	# x[i][j] = max (y[j][j+1] , y[j][j+2] , ……, y[j][n] )
	for i in range(0, j):
		xs[i][j] = max(ys[j][j+1:n+1])

	for i in range(0, j):
		ys[i][j] = min(xs[j][j+1:n+1])

# print(max(xs[0][0], abs(cards[-1] - x0)) )

# print(xs)
# print(ys)
print(max(ys[0][1:]))	


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

cards = [y0] + list(map(int, input().split()))
# yの手持ちはゲームに関与するため、リストに加えてしまう

xs = [[-1] * (n+1) for i in range(n+1)]
ys = [[-1] * (n+1) for i in range(n+1)] 
#xs[i][j] = xの手番で、xがcards[i]を持ちyがcards[j]を持っているとき(i<j)の最善スコア
#ys[i][j] = yの手番で、xがcards[j]を持ちyがcards[i]を持っているとき(i<j)の最善スコア

for i in range(n+1):
	xs[i][-1] = abs(cards[-1] - cards[i])
	ys[i][-1] = abs(cards[-1] - cards[i])

for j in range(n-1, -1, -1):

	# x[i][j] = max (y[j][j+1] , y[j][j+2] , ……, y[j][n] )
	xs_temp = max(ys[j][j+1:n+1])
	ys_temp = min(xs[j][j+1:n+1])
	for i in range(0, j):
		xs[i][j] = xs_temp
		ys[i][j] = ys_temp

# print(xs)
# print(ys)
print(max(ys[0][1:]))

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

cards = [y0] + list(map(int, input().split()))

xs = [[-1] * (n+1) for i in range(n+1)]
ys = [[-1] * (n+1) for i in range(n+1)] 
#xs[i][j] = xの手番で、xがcards[i]を持ちyがcards[j]を持っているとき(i<j)の最善スコア
#ys[i][j] = yの手番で、xがcards[j]を持ちyがcards[i]を持っているとき(i<j)の最善スコア

########ys[i][j] = yの手番で、xがcards[i]を持ちyがcards[j]を持っているとき(i>j)の最善スコア

for i in range(n+1):
	xs[i][-1] = abs(cards[-1] - cards[i])
	ys[i][-1] = abs(cards[-1] - cards[i])

for i in range(n-1, -1, -1):

	# x[i][j] = max (y[j][j+1] , y[j][j+2] , ……, y[j][n-1] )
	for j in range(n-1, i, -1):
		# temp_max = max(ys[j][j+1:n-1])
		# xs[i][j] = max(temp_max, ys[j][n-1])
		xs[i][j] = max(ys[j][j+1:n+1])

	for j in range(n-1, i, -1):
		# temp_min = min(xs[j][j+1:n-1])
		# ys[i][j] = min(temp_min, xs[j][n-1])
		ys[i][j] = min(xs[j][j+1:n+1])

# print(max(xs[0][0], abs(cards[-1] - x0)) )

# print(xs)
# print(ys)
print(max(ys[0][1:]))	


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

cards = [y0] + list(map(int, input().split()))
# yの手持ちはゲームに関与するため、リストに加えてしまう

xs = [[-1] * (n+1) for i in range(n+1)]
ys = [[-1] * (n+1) for i in range(n+1)] 
#xs[i][j] = xの手番で、xがcards[i]を持ちyがcards[j]を持っているとき(i<j)の最善スコア
#ys[i][j] = yの手番で、xがcards[j]を持ちyがcards[i]を持っているとき(i<j)の最善スコア

for i in range(n+1):
	xs[i][-1] = abs(cards[-1] - cards[i])
	ys[i][-1] = abs(cards[-1] - cards[i])

for j in range(n-1, -1, -1):

	# x[i][j] = max (y[j][j+1] , y[j][j+2] , ……, y[j][n] )
	xs_temp = max(ys[j][j+1:n+1])
	ys_temp = min(xs[j][j+1:n+1])
	for i in range(0, j):
		xs[i][j] = xs_temp
		ys[i][j] = ys_temp

# print(xs)
# print(ys)
print(max(ys[0][1:]))
Buggy python submission (verdict: Time Limit Exceeded):
# 全縦線と全横線を全探索するとO(N^5)
# 50 ** 5 = 312500000
# 縦線の選び方は50 C 2だから2分の1になるのを考慮しても、78125000
# いや無理だろ……と思ったら公式がこの解法だった。衝撃。
# 二次元累積和を使うと各回の計算がO(1)になるので、O(N^4)となる。

# まず O(N^5)解法を作ってみよう。通るのかこれ?


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

ans = (3 * 10 ** 9) ** 2
for ix1, x1 in enumerate(coords):
    for ix2, x2 in enumerate(coords[ix1+1:]):
        for iy1, y1 in enumerate(coords):
            for iy2, y2 in enumerate(coords[iy1+1:]):
                point_in_rect = 0
                for c in coords:
                    # ソートしてない。
                    if (c[0] - x1[0]) * (c[0] - x2[0]) <= 0 and (c[1] - y1[1]) * (c[1] - y2[1]) <= 0:
                        point_in_rect += 1
                if point_in_rect >= k:
                    ans = min(ans, abs((x1[0] - x2[0]) * (y1[1] - y2[1])))

print(ans)


Fixed submission:
# 全縦線と全横線を全探索するとO(N^5)
# 50 ** 5 = 312500000
# 縦線の選び方は50 C 2だから2分の1になるのを考慮しても、78125000
# いや無理だろ……と思ったら公式がこの解法だった。衝撃。
# 二次元累積和を使うと各回の計算がO(1)になるので、O(N^4)となる。

# まず O(N^5)解法を作ってみよう。通るのかこれ?


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

ans = (3 * 10 ** 9) ** 2
for ix1, x1 in enumerate(coords):
    for ix2, x2 in enumerate(coords[ix1+1:]):
        for iy1, y1 in enumerate(coords):
            for iy2, y2 in enumerate(coords[iy1+1:]):
                point_in_rect = 0
                for c in coords:
                    # ソートしてない。
                    if (c[0] - x1[0]) * (c[0] - x2[0]) <= 0 and (c[1] - y1[1]) * (c[1] - y2[1]) <= 0:
                        point_in_rect += 1
                if point_in_rect >= k:
                    ans = min(ans, abs((x1[0] - x2[0]) * (y1[1] - y2[1])))

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

num_free = 0
num_color = [False] * 8
for rate in nums:
    if rate < 3200:
        num_color(rate // 400) = True
    else:
        num_free += 1

ans = sum(num_color)
print('{} {}'.format(ans, ans + num_free))


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

num_free = 0
num_color = [False] * 8
for rate in nums:
    if rate < 3200:
        num_color[rate // 400] = True
    else:
        num_free += 1

ans = sum(num_color)
print('{} {}'.format(max(ans, 1), ans + num_free))
Buggy python submission (verdict: Time Limit Exceeded):
# dp[i][j] := Aをiグラム、Bをjグラムちょうど買うための最小予算。
# i <= N * a_i <= 40*10=400
# j <= N * b_i <= 40*10=400
# ……だとダメだわ。マスの遷移が許されるかどうかの情報が入ってない。
# （ある薬品を2回使うことはできないから、薬品を買ったか否かの情報を入れなきゃいけない）
# dp[k][i][j] := k番目までの薬品を使って、Aをiグラム、Bをjグラムちょうど買うための最小予算。
# 40*400*400で、各マスの計算は2個のマスを参照すれば求まるから、
# 40*400*400*2 = 12800000 = 1280万 間に合う。

n, a_ratio, b_ratio = list(map(int, input().split()))
chemicals = [list(map(int, input().split())) for _ in range(n)]

inf = 10 ** 10
ab_max = 10
dp = [[[inf for j in range(n * ab_max + 1)] for i in range(n * ab_max + 1)] for k in range(n)]

dp[0][0][0] = 0
dp[0][chemicals[0][0]][chemicals[0][1]] = chemicals[0][2]

for k in range(1, n):
    for i in range(n * ab_max + 1):
        for j in range(n * ab_max + 1):
            if i-chemicals[k][0] >= 0 and j-chemicals[k][1] >= 0:
                dp[k][i][j] = min(dp[k-1][i][j],  dp[k-1][i-chemicals[k][0]][j-chemicals[k][1]] + chemicals[k][2])
            else:
                dp[k][i][j] = dp[k-1][i][j]

ans = inf
bai = 1
while(a_ratio * bai <= n * ab_max and b_ratio * bai <= n * ab_max):
    ans = min(ans, dp[n-1][a_ratio * bai][b_ratio * bai])
    bai += 1

if ans < inf:
    print(ans)
else:
    print(-1)


Fixed submission:
# dp[i][j] := Aをiグラム、Bをjグラムちょうど買うための最小予算。
# i <= N * a_i <= 40*10=400
# j <= N * b_i <= 40*10=400
# ……だとダメだわ。マスの遷移が許されるかどうかの情報が入ってない。
# （ある薬品を2回使うことはできないから、薬品を買ったか否かの情報を入れなきゃいけない）
# dp[k][i][j] := k番目までの薬品を使って、Aをiグラム、Bをjグラムちょうど買うための最小予算。
# 40*400*400で、各マスの計算は2個のマスを参照すれば求まるから、
# 40*400*400*2 = 12800000 = 1280万 間に合う。

n, a_ratio, b_ratio = list(map(int, input().split()))
chemicals = [list(map(int, input().split())) for _ in range(n)]

inf = 10 ** 10
ab_max = 10
dp = [[[inf for j in range(n * ab_max + 1)] for i in range(n * ab_max + 1)] for k in range(n)]

dp[0][0][0] = 0
dp[0][chemicals[0][0]][chemicals[0][1]] = chemicals[0][2]

for k in range(1, n):
    for i in range(n * ab_max + 1):
        for j in range(n * ab_max + 1):
            if i-chemicals[k][0] >= 0 and j-chemicals[k][1] >= 0:
                dp[k][i][j] = min(dp[k-1][i][j],  dp[k-1][i-chemicals[k][0]][j-chemicals[k][1]] + chemicals[k][2])
            else:
                dp[k][i][j] = dp[k-1][i][j]

ans = inf
bai = 1
while(a_ratio * bai <= n * ab_max and b_ratio * bai <= n * ab_max):
    ans = min(ans, dp[n-1][a_ratio * bai][b_ratio * bai])
    bai += 1

if ans < inf:
    print(ans)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
# 6, 5, 6, 5, ...

x = int(input())
q = x // 11
r = x % 11
if r == 0:
    ans = q * 2
elif 1 <= r <= 5:
    ans = q * 2 + 1
elif 6 <= ans <= 10:
    ans = q * 2 + 2
print(ans)


Fixed submission:
# 6, 5, 6, 5, ...

x = int(input())
q = x // 11
r = x % 11
if r == 0:
    ans = q * 2
elif 1 <= r <= 6:
    ans = q * 2 + 1
elif 7 <= r <= 10:
    ans = q * 2 + 2
print(ans)
Buggy python submission (verdict: Runtime Error):
k, t = list(map(int, input().split()))
nums = list(map(int, input().split()))

m = max(nums)
rest = k - m
if max - rest - 1 > 0:
    print(max - rest - 1)
else:
    print(0)


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

m = max(nums)
rest = k - m
if m - rest - 1 > 0:
    print(m - rest - 1)
else:
    print(0)
Buggy python submission (verdict: Runtime Error):
lst =map(int, input().split())

max_value = 0
for i in range(len(lst)):
  for j in range(i):
    max_value = max(max_value, lst[i]*lst[j])

print(max_value)

Fixed submission:
# -*- coding: utf-8 -*-
# map(int, input().split())
a,b,c,d = list(map(int, input().split()))
 
max_value = max([a*c,a*d,b*c,b*d])

print(max_value)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


sum_A = [0]
sum_B = [0]
for n in range(N):
    sum_A.append(sum_A[n]+A[n])
for m in range(M):
    sum_B.append(sum_B[m]+B[m])

max_j = M
max_book = 0
for i in range(N+1):
    # Aの机でi冊読んだときのBの机で読む最大値
    if sum_A > K:
        break
    for j in range(max_j,-1,-1):
        if sum_A[i]+sum_B[j] <= K:
            max_j = j
            break
    else:
        max_j = 0
    
    max_book = max(max_book, i+max_j)

print(max_book)


Fixed submission:
# -*- coding: utf-8 -*-
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


sum_A = [0]
sum_B = [0]
for n in range(N):
    sum_A.append(sum_A[n]+A[n])
for m in range(M):
    sum_B.append(sum_B[m]+B[m])

max_j = M
max_book = 0
for i in range(N+1):
    # Aの机でi冊読んだときのBの机で読む最大値
    if sum_A[i] > K:
        break
    for j in range(max_j,-1,-1):
        if sum_A[i]+sum_B[j] <= K:
            max_j = j
            break
    else:
        max_j = 0
    
    max_book = max(max_book, i+max_j)

print(max_book)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

if sum(A)+sum(B) <= K:
    print(N+M)
    exit(0)

sum_A = [0 for i in range(N+1)]
sum_B = [0 for i in range(M+1)]
for i in range(N):
    sum_A[i+1] = sum_A[i]+A[i]
for i in range(M):
    sum_B[i+1] = sum_B[i]+B[i]    

for l in range(N+M+1):
    min_time_l = min(
        [sum_A[i]+sum_B[l-i] 
        for i in range(max(l-M,0), N+1)])
    if min_time_l > K:
        print(l-1)
        exit(0)

print(N+M)

Fixed submission:
# -*- coding: utf-8 -*-
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


sum_A = [0]
sum_B = [0]
for n in range(N):
    sum_A.append(sum_A[n]+A[n])
for m in range(M):
    sum_B.append(sum_B[m]+B[m])

max_j = M
max_book = 0
for i in range(N+1):
    # Aの机でi冊読んだときのBの机で読む最大値
    if sum_A[i] > K:
        break
    for j in range(max_j,-1,-1):
        if sum_A[i]+sum_B[j] <= K:
            max_j = j
            break
    else:
        max_j = 0
    
    max_book = max(max_book, i+max_j)

print(max_book)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

N = int(input())

result = 0
for n in range(1,N+1):
    result += sum([n*i for i in range(1, int(N/n)+1)])

print(result)

Fixed submission:
# -*- coding: utf-8 -*-

N = int(input())

def sum_inc(n):
    return int(n*(n+1)/2)

half = int(N/2)+1

each_result = [n*sum_inc(int(N/n)) for n in range(1,half)]

print(sum(each_result)+sum_inc(N) - sum_inc(half-1))
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
s = input()

return s[0:3]

Fixed submission:
# -*- coding: utf-8 -*-
s = input()
print(s[0:3])
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
A, B = map(int, input().split())

return(A*B)

Fixed submission:
# -*- coding: utf-8 -*-
A, B = map(int, input().split())

print(A*B)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
X, Y, A, B, C = map(int, input().split())
red_oishisa = list(map(int, input().split()))
green_oishisa = list(map(int, input().split()))
no_oishisa = list(map(int, input().split()))

red_oishisa = list(sorted(red_oishisa))[::-1]
green_oishisa = list(sorted(green_oishisa))[::-1]
no_oishisa = list(sorted(no_oishisa))[::-1]

oishisa_s = []

i=1
j=1
k=1
while(True):
    if len(oishisa_s) == X+Y:
        break
    
    hikaku_dict = dict()
    if i <= X:
        hikaku_dict['red'] = red_oishisa[i-1]
    if j <= Y:
        hikaku_dict['green'] = green_oishisa[j-1]
    if k <= C:
        hikaku_dict['no'] = no_oishisa[k-1]
    
    max_key, max_value = max(hikaku_dict.items(), key=lambda x:x[1])
    oishisa_s.append(max_value)
    if max_key == 'red':
        i += 1
    elif max_key == 'green':
        j += 1
    elif max_key == 'no':
        k += 1

print(sum(oishisa_s))

Fixed submission:
# -*- coding: utf-8 -*-
string = input()

if string[2] == string[3] and string[4] == string[5]:
  print('Yes')
else:
  print('No')

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
X = int(input())

num_500 = int(X / 500)
num_5 = int((X - (num_500*500)) / 5)

print((num_500*1000) + (num_5)*5)

Fixed submission:
# -*- coding: utf-8 -*-
string = input()

if string[2] == string[3] and string[4] == string[5]:
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int,input().split())
LR = [tuple(map(int,input().split())) for _ in range(K)]
d = [0]*N
ans = [0]*N
ans[0] = 1
MOD = 998244353
for i in range(N):
    x = ans[i]
    for k in range(K):
        L, R = LR[k]
        if i+L < len(d):
            d[i+L] += x
            d[i+L] %= MOD
        if i+R+1 < len(d):
            d[i+R+1] -= x
            d[i+R+1] %= MOD
    for j in range(i+2, len(d)):
        d[j] += d[j-1]
        d[j] %= MOD
    for j in range(len(d)):
        ans[j] = (ans[j]+d[j]) % MOD
        d[j] = 0
print(ans[-1] % MOD)

Fixed submission:
N, K = map(int,input().split())
LR = [tuple(map(int,input().split())) for _ in range(K)]
d = [0]*N
d[0] = 1
MOD = 998244353
for i in range(N-1):
    x = d[i]
    d[0] = 0
    for k in range(K):
        L, R = LR[k]
        if i+L < len(d):
            d[i+L] += x
            d[i+L] %= MOD
        if i+R+1 < len(d):
            d[i+R+1] -= x
            d[i+R+1] %= MOD
    d[i+1] += d[i]
    d[i+1] %= MOD
print(d[-1] % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int,input().split())
LR = [tuple(map(int,input().split())) for _ in range(K)]
d = [0]*N
ans = [0]*N
ans[0] = 1
for i in range(N):
    x = ans[i]
    for k in range(K):
        L, R = LR[k]
        if i+L < len(d):
            d[i+L] += x
        if i+R+1 < len(d):
            d[i+R+1] -= x
    for j in range(i+2, len(d)):
        d[j] += d[j-1]
    for j in range(len(d)):
        ans[j] += d[j]
        d[j] = 0
print(ans[-1] % 998244353)

Fixed submission:
N, K = map(int,input().split())
LR = [tuple(map(int,input().split())) for _ in range(K)]
d = [0]*N
d[0] = 1
MOD = 998244353
for i in range(N-1):
    x = d[i]
    d[0] = 0
    for k in range(K):
        L, R = LR[k]
        if i+L < len(d):
            d[i+L] += x
            d[i+L] %= MOD
        if i+R+1 < len(d):
            d[i+R+1] -= x
            d[i+R+1] %= MOD
    d[i+1] += d[i]
    d[i+1] %= MOD
print(d[-1] % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
N, X, M = map(int,input().split())
visited = [(-1,-1)]*M
ans = 0
for i in range(N):
    if visited[X][0] > 0:
        d = ans - visited[X][0]
        left = N-i
        length = i-visited[X][1]
        ans += (left//length)*d
        left %= length
        for j in range(left):
            ans += X
            X = X*X % M
        break
    visited[X] = (ans, i)
    ans += X
    X = X*X % M
print(ans)

Fixed submission:
N, X, M = map(int,input().split())
visited = [(-1,-1)]*M
ans = 0
for i in range(N):
    if visited[X][0] >= 0:
        d = ans - visited[X][0]
        left = N-i
        length = i-visited[X][1]
        ans += (left//length)*d
        left %= length
        for j in range(left):
            ans += X
            X = X*X % M
        break
    visited[X] = (ans, i)
    ans += X
    X = X*X % M
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, X, M = map(int,input().split())
visited = [(-1,-1)]*M
ans = 0
for i in range(N):
    if visited[X][0] > 0:
        d = ans - visited[X][0]
        left = N-i
        length = i-visited[X][1]
        ans += (left//length)*d
        left %= length
        for j in range(left):
            ans += X
            X = X*X % M
        break
    visited[X] = (ans, i)
    ans += X
    X = X*X % M
print(ans)

Fixed submission:
N, X, M = map(int,input().split())
visited = [(-1,-1)]*M
ans = 0
for i in range(N):
    if visited[X][0] >= 0:
        d = ans - visited[X][0]
        left = N-i
        length = i-visited[X][1]
        ans += (left//length)*d
        left %= length
        for j in range(left):
            ans += X
            X = X*X % M
        break
    visited[X] = (ans, i)
    ans += X
    X = X*X % M
print(ans)