Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
	A[i], B[i], C[i] = map(int, input().split())

d = [[float("inf") for _ in range(N)] for _ in range(N)]

for i in range(M):
	d[A[i] - 1][B[i] - 1] = C[i]
	d[B[i] - 1][A[i] - 1] = C[i]

for k in range(N):
	for i in range(N):
		for j in range(N):
			if d[i][j] > d[i][k] + d[k][j]:
				d[i][j] = d[i][k] + d[k][j]

p = permutations(r)
ans = float("inf")
for route in p:
	l = 0
	for i in range(R - 1):
		l += d[route[i] - 1][route[i + 1] - 1]

	if l < ans:
		ans = l

print(ans)

Fixed submission:
from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
	A[i], B[i], C[i] = map(int, input().split())

d = [[float("inf") for _ in range(N)] for _ in range(N)]

for i in range(M):
	d[A[i] - 1][B[i] - 1] = C[i]
	d[B[i] - 1][A[i] - 1] = C[i]

for k in range(N):
	for i in range(N):
		for j in range(N):
			if d[i][j] > d[i][k] + d[k][j]:
				d[i][j] = d[i][k] + d[k][j]
				d[j][i] = d[i][k] + d[k][j]

p = permutations(r)
ans = float("inf")
for route in p:
	l = 0
	for i in range(R - 1):
		l += d[route[i] - 1][route[i + 1] - 1]

	if l < ans:
		ans = l

print(ans)

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

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
	A[i], B[i], C[i] = map(int, input().split())

d = [[float("inf") for _ in range(N)] for _ in range(N)]

for i in range(M):
	d[A[i] - 1][B[i] - 1] = C[i]
	d[B[i] - 1][A[i] - 1] = C[i]

for k in range(N):
	for i in range(N):
		for j in range(N):
			if d[i][j] > d[i][k] + d[k][j]:
				d[i][j] = d[i][k] + d[k][j]
				d[j][i] = d[i][k] + d[k][j]

p = permutations(r)
ans = float("inf")
for route in p:
	l = 0
	for i in range(R - 1):
		l += d[route[i] - 1][route[i + 1] - 1]

	if l < ans:
		ans = l

print(ans)

Fixed submission:
from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
	A[i], B[i], C[i] = map(int, input().split())

d = [[float("inf") for _ in range(N)] for _ in range(N)]

for i in range(M):
	d[A[i] - 1][B[i] - 1] = C[i]
	d[B[i] - 1][A[i] - 1] = C[i]

for k in range(N):
	for i in range(N):
		for j in range(N):
			if d[i][j] > d[i][k] + d[k][j]:
				d[i][j] = d[i][k] + d[k][j]
				d[j][i] = d[i][k] + d[k][j]

p = permutations(r)
ans = float("inf")
for route in p:
	l = 0
	for i in range(R - 1):
		l += d[route[i] - 1][route[i + 1] - 1]

	if l < ans:
		ans = l

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

n = int(input())
ans = 1

for _ in range(n):
	i = int(input())
	ans = int((ans / gcd(ans, i)) * i)

print(ans)

Fixed submission:
from fractions import gcd

n = int(input())
ans = 1

for _ in range(n):
	i = int(input())
	ans = ans // gcd(ans, i) * i

print(ans)

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

n = int(input())
ans = 1

for _ in range(n):
	i = int(input())
	ans = int(ans / gcd(ans, i) * i)

print(ans)

Fixed submission:
from fractions import gcd

n = int(input())
ans = 1

for _ in range(n):
	i = int(input())
	ans = ans // gcd(ans, i) * i

print(ans)

Buggy python submission (verdict: Runtime Error):
from fratcions import gcd

n = int(input())
ans = 1

for _ in range(n):
	i = int(input())
	ans = int(ans / gcd(ans, i) * i)

print(ans)

Fixed submission:
from fractions import gcd

n = int(input())
ans = 1

for _ in range(n):
	i = int(input())
	ans = ans // gcd(ans, i) * i

print(ans)

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

n = int(input())
ans = 1

for _ in range(n):
	i = int(input())
	ans = int(ans * i / gcd(ans, i))

print(ans)

Fixed submission:
from fractions import gcd

n = int(input())
ans = 1

for _ in range(n):
	i = int(input())
	ans = ans // gcd(ans, i) * i

print(ans)

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

n = int(input())
ans = 1

for _ in range(n):
	i = int(input())
	ans = int(ans * i / gcd(ans, i))

print(ans)

Fixed submission:
from fractions import gcd

n = int(input())
ans = 1

for _ in range(n):
	i = int(input())
	ans = ans // gcd(ans, i) * i

print(ans)
Buggy python submission (verdict: Runtime Error):
from math import gcd

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

if n == 1:
	if n == k:
		print("POSSIBLE")
	else:
		print("IMPOSSIBLE")
else:
	if k in a:
		print("POSSIBLE")
	elif k > max(a):
		print("IMPOSSIBLE")
	else:
		g = gcd(a[0], a[1])
		for i in range(2, n):
			g = gcd(g, a[i])

		if k % g == 0:
			print("POSSIBLE")
		else:
			print("IMPOSSIBLE")

Fixed submission:
from fractions import gcd

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

if n == 1:
	if a[0] == k:
		print("POSSIBLE")
	else:
		print("IMPOSSIBLE")
else:
	if k in a:
		print("POSSIBLE")
	elif k > max(a):
		print("IMPOSSIBLE")
	else:
		g = gcd(a[0], a[1])
		for i in range(2, n):
			g = gcd(g, a[i])

		if k % g == 0:
			print("POSSIBLE")
		else:
			print("IMPOSSIBLE")
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [b-1 for b in a]
imos = [0 for _ in range(m+1)]
base = 0
for i in range(n-1):
	x, y = a[i], a[i+1]
	z, w = (x+2)%m, (y+1)%m
	if w == 0:
		w = m
	if z < w:
		imos[z] += 1
		imos[w] -= w-z+1
		if w < m:
			imos[w+1] += w-z
	else:
		imos[z] += 1
		imos[m] -= m-z+1
		imos[0] += 1
		base += m-z
		imos[w] -= m+w-z+1
		if w < m:
			imos[w+1] += m+w-z
#print(imos)
#print(base)
for i in range(n):
	imos[i+1] += imos[i]
imos[0] += base
for i in range(n):
	imos[i+1] += imos[i]
res = max(imos[:m])
ans = 0
for i in range(n-1):
	if a[i+1] > a[i]:
		ans += a[i+1] - a[i]
	else:
		ans += a[i+1] + m - a[i]
#print(ans)
ans -= res
print(ans)

Fixed submission:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [b-1 for b in a]
imos = [0 for _ in range(m+1)]
base = 0
for i in range(n-1):
	x, y = a[i], a[i+1]
	if y-x == 1 or x+1-m == y:
		continue
	z, w = (x+2)%m, (y+1)%m
	if w == 0:
		w = m
	if z < w:
		imos[z] += 1
		imos[w] -= w-z+1
		if w < m:
			imos[w+1] += w-z
	else:
		imos[z] += 1
		imos[m] -= m-z+1
		imos[0] += 1
		base += m-z
		imos[w] -= m+w-z+1
		if w < m:
			imos[w+1] += m+w-z
#print(imos)
#print(base)
for i in range(m):
	imos[i+1] += imos[i]
imos[0] += base
for i in range(m):
	imos[i+1] += imos[i]
res = max(imos[:m])
ans = 0
for i in range(n-1):
	if a[i+1] > a[i]:
		ans += a[i+1] - a[i]
	else:
		ans += a[i+1] + m - a[i]
#print(ans)
ans -= res
print(ans)

Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [b-1 for b in a]
imos = [0 for _ in range(m+1)]
base = 0
for i in range(n-1):
	x, y = a[i], a[i+1]
	z, w = (x+2)%m, (y+1)%m
	if w == 0:
		w = m
	if z < w:
		imos[z] += 1
		imos[w] -= w-z+1
		if w < m:
			imos[w+1] += w-z
	else:
		imos[z] += 1
		imos[m] -= m-z+1
		imos[0] += 1
		base += m-z
		imos[w] -= m+w-z+1
		imos[w+1] += m+w-z
#print(imos)
#print(base)
for i in range(n):
	imos[i+1] += imos[i]
imos[0] += base
for i in range(n):
	imos[i+1] += imos[i]
res = max(imos[:m])
ans = 0
for i in range(n-1):
	if a[i+1] > a[i]:
		ans += a[i+1] - a[i]
	else:
		ans += a[i+1] + m - a[i]
#print(ans)
ans -= res
print(ans)

Fixed submission:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [b-1 for b in a]
imos = [0 for _ in range(m+1)]
base = 0
for i in range(n-1):
	x, y = a[i], a[i+1]
	if y-x == 1 or x+1-m == y:
		continue
	z, w = (x+2)%m, (y+1)%m
	if w == 0:
		w = m
	if z < w:
		imos[z] += 1
		imos[w] -= w-z+1
		if w < m:
			imos[w+1] += w-z
	else:
		imos[z] += 1
		imos[m] -= m-z+1
		imos[0] += 1
		base += m-z
		imos[w] -= m+w-z+1
		if w < m:
			imos[w+1] += m+w-z
#print(imos)
#print(base)
for i in range(m):
	imos[i+1] += imos[i]
imos[0] += base
for i in range(m):
	imos[i+1] += imos[i]
res = max(imos[:m])
ans = 0
for i in range(n-1):
	if a[i+1] > a[i]:
		ans += a[i+1] - a[i]
	else:
		ans += a[i+1] + m - a[i]
#print(ans)
ans -= res
print(ans)
Buggy python submission (verdict: Runtime Error):
from operator import itemgetter

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return x

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
		return

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xy_x = {i: xy[i][0] for i in range(n)}
xy_y = {i: xy[i][1] for i in range(n)}

v_x = sorted(xy_x.items(), key=itemgetter(1))
v_y = sorted(xy_y.items(), key=itemgetter(1))

edges = dict()

for i in range(n - 1):
	edges[(v_x[i][0], v_x[i+1][0])] = v_x[i+1][1] - v_x[i][1]
	edges[(v_y[i][0], v_y[i+1][0])] = v_y[i+1][1] - v_y[i][1]

uf = UnionFind(n)

edges = sorted(edges.items(), key=itemgetter(1))

ans = 0

while edges != list():
	e = edges.pop(0)
	if uf.find(e[0][0]) != uf.find(e[0][1]):
		uf.union(e[0][0], e[0][1])
		ans += e[1]

print(ans)

Fixed submission:
MOD = 10 ** 9 + 7
n, m = map(int, input().split())

if abs(n - m) >= 2:
	print(0)

else:
	n, m = (max(n, m), min(n, m))
	ans = 1
	for i in range(1, m + 1):
		ans = (ans * i) % MOD

	if n == m:
		print((ans ** 2 * 2) % MOD)
	else:
		print((ans ** 2 * n) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
n, a, b = map(int, input().split())
pre_h = [int(input()) for _ in range(n)]

minimum = (min(pre_h) - 1) // a + 1

h = [0] * n
while True:
	for i in range(n):
		if pre_h[i] - b * minimum > 0:
			h[i] = pre_h[i] - b * minimum
		else:
			h[i] = 0

	if sum([(i - 1) // (a - b) + 1 for i in h]) <= minimum:
		break

	#print(h)
	minimum += 1

print(minimum)

Fixed submission:
n, a, b = map(int, input().split())
pre_h = [int(input()) for _ in range(n)]

def check(cnt):
	h = [0] * n
	for i in range(n):
		if pre_h[i] - b * cnt > 0:
			h[i] = pre_h[i] - b * cnt
		else:
			h[i] = 0

	if sum([(i - 1) // (a - b) + 1 for i in h]) <= cnt:
		return True
	else:
		return False

minimum = 1
maximum = (max(pre_h) - 1) // b + 1

while maximum - minimum > 1:
	if check(minimum + (maximum - minimum) // 2):
		maximum = minimum + (maximum - minimum) // 2
	else:
		minimum = minimum + (maximum - minimum) // 2

print(maximum)

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

minimum = (min(pre_h) - 1) // a + 1

h = [0] * n
while True:
	for i in range(n):
		if pre_h[i] - b * minimum > 0:
			h[i] = pre_h[i] - b * minimum
		else:
			h[i] = 0

	if sum([(i - 1) // (a - b) + 1 for i in h]) <= minimum:
		break

	#print(h)
	minimum += 1

print(minimum)

Fixed submission:
n, a, b = map(int, input().split())
pre_h = [int(input()) for _ in range(n)]

def check(cnt):
	h = [0] * n
	for i in range(n):
		if pre_h[i] - b * cnt > 0:
			h[i] = pre_h[i] - b * cnt
		else:
			h[i] = 0

	if sum([(i - 1) // (a - b) + 1 for i in h]) <= cnt:
		return True
	else:
		return False

minimum = 1
maximum = (max(pre_h) - 1) // b + 1

while maximum - minimum > 1:
	if check(minimum + (maximum - minimum) // 2):
		maximum = minimum + (maximum - minimum) // 2
	else:
		minimum = minimum + (maximum - minimum) // 2

print(maximum)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input():
	return sys.stdin.readline()[:-1]

n, m, q = map(int, input().split())
s = ["0"*(m+1)] + ["0" + input() for _ in range(n)]

block = [[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(1, n+1):
	for j in range(1, m+1):
		block[i][j] = block[i][j-1] + block[i-1][j] - block[i-1][j-1] + int(s[i][j])

def block_num(x1, y1, x2, y2):
	return block[x2][y2] - block[x1-1][y2] - block[x2][y1-1] + block[x1-1][y1-1]

edge_h = [[0 for _ in range(m)] for _ in range(n+1)]
edge_v = [[0 for _ in range(m+1)] for _ in range(n)]

for i in range(1, n+1):
	for j in range(1, m):
		edge_h[i][j] = edge_h[i][j-1] + edge_h[i-1][j] - edge_h[i-1][j-1] + (int(s[i][j]) + int(s[i][j+1]) == 2)

for i in range(1, n):
	for j in range(1, m+1):
		edge_v[i][j] = edge_v[i][j-1] + edge_v[i-1][j] - edge_v[i-1][j-1] + (int(s[i][j]) + int(s[i+1][j]) == 2)

def edge_num(x1, y1, x2, y2):
	h = edge_h[x2][y2-1] - edge_h[x1-1][y2-1] - edge_h[x2][y1-1] + edge_h[x1-1][y1-1]
	v = edge_v[x2-1][y2] - edge_v[x1-1][y2] - edge_v[x2-1][y1-1] + edge_v[x1-1][y1-1]
	return h+v

for _ in range(q):
	x1, y1, x2, y2 = map(int, input().split())
	b = block_num(x1, y1, x2, y2)
	e = edge_num(x1, y1, x2, y2)
	print(b-e)

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

n, m, q = map(int, input().split())
s = ["0"*(m+1)] + ["0" + input() for _ in range(n)]

block = [[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(1, n+1):
	for j in range(1, m+1):
		block[i][j] = block[i][j-1] + block[i-1][j] - block[i-1][j-1] + int(s[i][j])

def block_num(x1, y1, x2, y2):
	return block[x2][y2] - block[x1-1][y2] - block[x2][y1-1] + block[x1-1][y1-1]

edge_h = [[0 for _ in range(m)] for _ in range(n+1)]
edge_v = [[0 for _ in range(m+1)] for _ in range(n)]

for i in range(1, n+1):
	for j in range(1, m):
		edge_h[i][j] = edge_h[i][j-1] + edge_h[i-1][j] - edge_h[i-1][j-1] + (int(s[i][j]) + int(s[i][j+1]) == 2)

for i in range(1, n):
	for j in range(1, m+1):
		edge_v[i][j] = edge_v[i][j-1] + edge_v[i-1][j] - edge_v[i-1][j-1] + (int(s[i][j]) + int(s[i+1][j]) == 2)

def edge_num(x1, y1, x2, y2):
	h = edge_h[x2][y2-1] - edge_h[x1-1][y2-1] - edge_h[x2][y1-1] + edge_h[x1-1][y1-1]
	v = edge_v[x2-1][y2] - edge_v[x1-1][y2] - edge_v[x2-1][y1-1] + edge_v[x1-1][y1-1]
	return h+v

for _ in range(q):
	x1, y1, x2, y2 = map(int, input().split())
	b = block_num(x1, y1, x2, y2)
	e = edge_num(x1, y1, x2, y2)
	print(b-e)
Buggy python submission (verdict: Runtime Error):
h, w = map(int, input().split())
l = max(h, w)
s = min(h, w)
if h % 3 == 0 or w % 3 == 0:
	print(0)
else:
	if abs((l // 3) - l / 3) <= abs((l // 3 + 1) - l / 3):
		block1 = s * (l // 3)
		block3 = (l - (l // 3)) * ((s + 1) // 2)
		block2 = H * W - block1 - block3
		print(max(block1, block2, block3) - min(block1, block2, block3))
	else:
		block1 = s * (l // 3 + 1)
		block3 = (l - 1 - (l // 3)) * (s // 2)
		block2 = H * W - block1 - block3
		print(max(block1, block2, block3) - min(block1, block2, block3))

Fixed submission:
H, W = map(int, input().split())

def check(h, w):
	if h % 3 == 0 or w % 3 == 0:
		return 0

	else:
		block1 = w * (h // 3)
		block2 = (h - (h // 3)) * (w // 2)
		block3 = h * w - block1 - block2
		gap1 = max(block1, block2, block3) - min(block1, block2, block3)

		block4 = w * (h // 3 + 1)
		block5 = (h - 1 - (h // 3)) * (w // 2)
		block6 = h * w - block4 - block5
		gap2 = max(block4, block5, block6) - min(block4, block5, block6)

		return(min(gap1, gap2, min(w, h)))

print(min(check(H, W), check(W, H)))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from math import ceil
import sys
def input():
	return sys.stdin.readline()[:-1]

H, W, k = map(int, input().split())
m = [input() for _ in range(H)]
q = deque()
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

step = [[10**10 for _ in range(W)] for _ in range(H)]

for h in range(1, H-1):
	for w in range(1, W-1):
		if m[h][w] == "S":
			q.appendleft([h, w])
			sx, sy = h, w

step[sx][sy] = 0
while q:
	label = q.pop()
	if step[label[0]][label[1]] == k:
		continue
	for i in range(4):
		h, w = label[0] + dx[i], label[1] + dy[i]
		if 0 <= h < H and 0 <= w < W:
			if m[h][w] == "." and step[h][w] > step[label[0]][label[1]] + 1:
				q.appendleft([h, w])
				step[h][w] = step[label[0]][label[1]] + 1

min_dis = max(H, W)
for h in range(H):
	for w in range(W):
		if step[h][w] <= k:
			min_dis = min(min_dis, h, w, H-h-1, W-w-1)

print(1+ceil(min_dis/k))

Fixed submission:
from collections import deque
from math import ceil
import sys
def input():
	return sys.stdin.readline()[:-1]

H, W, k = map(int, input().split())
m = [input() for _ in range(H)]
q = deque()
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

step = [[10**10 for _ in range(W)] for _ in range(H)]

for h in range(1, H-1):
	for w in range(1, W-1):
		if m[h][w] == "S":
			q.appendleft([h, w])
			sx, sy = h, w

step[sx][sy] = 0
while q:
	label = q.pop()
	if step[label[0]][label[1]] == k:
		continue
	for i in range(4):
		h, w = label[0] + dx[i], label[1] + dy[i]
		if 0 <= h < H and 0 <= w < W:
			if m[h][w] == "." and step[h][w] > step[label[0]][label[1]] + 1:
				q.appendleft([h, w])
				step[h][w] = step[label[0]][label[1]] + 1

min_dis = max(H, W)
for h in range(H):
	for w in range(W):
		if step[h][w] <= k:
			min_dis = min(min_dis, h, w, H-h-1, W-w-1)

print(1+ceil(min_dis/k))
Buggy python submission (verdict: Runtime Error):
INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1 << (size.bit_length())
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)>>1
			self.node[x] = min(self.node[(x<<1)+1], self.node[(x<<1)+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b = map(int, input().split())
qs = [a] + list(map(int, input().split()))
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
for i in range(q):
	x, y = qs[i], qs[i+1]
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	#print(res)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff

N = dp_l.n
print(total_diff + min(dp_l.node[i+N-1] + i for i in range(1, n+1)))

Fixed submission:
n, T = map(int, input().split())
t = list(map(int, input().split()))
ans = 0

for i in range(n - 1):
	if t[i + 1] - t[i] < T:
		ans += t[i + 1] - t[i]
	else:
		ans += T

ans += T

print(ans)
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left
n, l, t = map(int, input().split())
ants = [list(map(int, input().split())) for _ in range(n)]
bnts = []
diff = []

for i in range(n):
	x, w = ants[i][0], 3 - 2*ants[i][1]
	bnts.append((x + t*w) % l)
	if i == 0:
		zero = bnts[-1]
	if ants[i][1] != ants[0][1]:
		if ants[0][1] == 1:
			diff.append(x - ants[0][0])
		else:
			diff.append(l - (x - ants[0][0]))

bnts.sort()
num = 0
quo, mod = t//l, t%l
num += quo * len(diff) * 2
diff.sort()
diff += [d+l for d in diff]
num += bisect_left(diff, mod*2)
num %= n
for i in range(n):
	if bnts[i] == zero:
		if ants[0][1] == 1:
			true_zero = (i-num) % n
		else:
			if bnts[i+1] == zero:
				num += 1
			true_zero = (i+num) % n

ans = bnts[true_zero:] + bnts[:true_zero]
print(*ans, sep="\n")

Fixed submission:
from bisect import bisect_left, bisect
n, l, t = map(int, input().split())
ants = [list(map(int, input().split())) for _ in range(n)]
bnts = []
diff = []

for i in range(n):
	x, w = ants[i][0], 3 - 2*ants[i][1]
	bnts.append((x + t*w) % l)
	if i == 0:
		zero = bnts[-1]
	if ants[i][1] != ants[0][1]:
		if ants[0][1] == 1:
			diff.append(x - ants[0][0])
		else:
			diff.append(l - (x - ants[0][0]))

bnts.sort()
num = 0
quo, mod = t//l, t%l
num += quo * len(diff) * 2
diff.sort()
diff += [d+l for d in diff]
#num += bisect_left(diff, mod*2)
num += bisect(diff, mod*2)
num %= n
for i in range(n):
	if bnts[i] == zero:
		if ants[0][1] == 1:
			true_zero = (i-num) % n
		else:
			if i < n-1:
				if bnts[i+1] == zero:
					#pass
					num -= 1
			true_zero = (i+num) % n

ans = bnts[true_zero:] + bnts[:true_zero]
print(*ans, sep="\n")
Buggy python submission (verdict: Runtime Error):
MOD = 10**9 + 7
n = int(input())
dp = [0 for _ in range(n+1)]
dp[0], dp[1], dp[2] = 1, 1, 1
cum = [0 for _ in range(n+1)]
cum[0], cum[1], cum[2] = 1, 2, 3
for i in range(3, n+1):
	dp[i] = (dp[i-1] + cum[i-3]) % MOD
	cum[i] = (cum[i-1] + dp[i]) % MOD
ans = cum[n-2] * (n-1) * (n-1) + dp[n-1] * (n-1) + cum[n-2] * (n-1) + 1
print(ans%MOD)

Fixed submission:
MOD = 10**9 + 7
n = int(input())
if n == 1:
	print(1)
else:
	dp = [0 for _ in range(n+1)]
	dp[0], dp[1], dp[2] = 1, 1, 1
	cum = [0 for _ in range(n+1)]
	cum[0], cum[1], cum[2] = 1, 2, 3
	for i in range(3, n+1):
		dp[i] = (dp[i-1] + cum[i-3]) % MOD
		cum[i] = (cum[i-1] + dp[i]) % MOD
	ans = cum[n-2] * (n-1) * (n-1) + dp[n-1] * (n-1) + cum[n-2] * (n-1) + 1
	print(ans%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input():
	return sys.stdin.readline()[:-1]

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

dp = [[0 for _ in range(11)] for _ in range(n)]
qs = [0]

q = int(input())
for i in range(q):
	v, d, c = map(int, input().split())
	qs.append(c)
	dp[v-1][d] = i+1

for j in range(10, 0, -1):
	for i in range(n):
		for v in adj[i]:
			dp[v][j-1] = max(dp[v][j-1], dp[i][j])

for i in range(n):
	print(qs[dp[i][0]])

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

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

dp = [[0 for _ in range(11)] for _ in range(n)]
qs = [0]

q = int(input())
for i in range(q):
	v, d, c = map(int, input().split())
	qs.append(c)
	dp[v-1][d] = i+1

for j in range(10, 0, -1):
	for i in range(n):
		for v in adj[i]:
			dp[v][j-1] = max(dp[v][j-1], dp[i][j])

for i in range(n):
	print(qs[dp[i][0]])
Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split())
if a == b:
  print("H")
else:
  print("D")


Fixed submission:
a, b = map(str, input().split())
if a == b:
	print("H")
else:
	print("D")

Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split())
if a == b:
	print("H")
else:
	print("D")

Fixed submission:
a, b = map(str, input().split())
if a == b:
	print("H")
else:
	print("D")
Buggy python submission (verdict: Time Limit Exceeded):
x = int(input())
s = {0}
ans = 0
i = 1
while x not in s:
	t = set()
	for u in s:
		t |= {u + i, u, u - i}
	s = t
	i += 1

print(i - 1)

Fixed submission:
x = int(input())
i = 1
while i * (i + 1) / 2 < x:
	i += 1
print(i)
Buggy python submission (verdict: Time Limit Exceeded):
n, ma, mb = map(int, input().split())
dp = [[[float('inf') for _ in range(401)] for _ in range(401)] for _ in range(n)]
dp[0][0][0] = 0
a0, b0, c0 = map(int, input().split())
dp[0][a0][b0] = c0

for i in range(1, n):
	dp[i][0][0] = 0
	a, b, c = map(int, input().split())
	for j in range(401):
		for k in range(401):
			if j >= a and k >= b:
				dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][j-a][k-b] + c)
			else:
				dp[i][j][k] = dp[i-1][j][k]

ans = float("inf")
cnt = 400 // max(ma, mb)
for i in range(1, cnt + 1):
	ans = min(ans, dp[-1][ma * i][mb * i])

if ans <= 4000:
	print(ans)
else:
	print(-1)

Fixed submission:
n, ma, mb = map(int, input().split())
dp = [[[float('inf') for _ in range(401)] for _ in range(401)] for _ in range(n)]
dp[0][0][0] = 0
a0, b0, c0 = map(int, input().split())
dp[0][a0][b0] = c0

for i in range(1, n):
	dp[i][0][0] = 0
	a, b, c = map(int, input().split())
	for j in range(401):
		for k in range(401):
			if j >= a and k >= b:
				dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][j-a][k-b] + c)
			else:
				dp[i][j][k] = dp[i-1][j][k]

ans = float("inf")
cnt = 400 // max(ma, mb)
for i in range(1, cnt + 1):
	ans = min(ans, dp[-1][ma * i][mb * i])

if ans <= 4000:
	print(ans)
else:
	print(-1)