Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())
wl = [0]*(N+1)
vl = [0]*(N+1)
for i in range(1, N+1):
    wl[i], vl[i] = map(int, input().split())

MAX = W
dp = [0]*(MAX+1)

for i in range(1, N+1):
    w, v = wl[i], vl[i]
    for k in reversed(range(MAX+1-w)):
        if k + w > MAX:
            break
        else:
            dp[k+w] = max(dp[k+w], dp[k] + v)
print(max(dp))



Fixed submission:
N, W = map(int, input().split())
wl = [0]*(N+1)
vl = [0]*(N+1)
for i in range(1, N+1):
    wl[i], vl[i] = map(int, input().split())

NIL = int(1e18)
MAX = int(1e5)

dp = [NIL]*(MAX+1)
dp[0]= 0

for i in range(1, N+1):
    w, v = wl[i], vl[i]
    for k in reversed(range(MAX+1)):
        if k + v <= MAX and dp[k] != NIL:
            dp[k+v] = min(dp[k+v], dp[k] + w)

ans = 0
for i in reversed(range(MAX+1)):
    if dp[i] <= W:
        ans = i
        break
print(ans)
Buggy python submission (verdict: Runtime Error):
# 誤読

N, X = map(int, input().split())

layer = 1
for _ in range(N):
    layer = layer * 2 + 3

def calc(n, i, layer):
    if n == 1:
        return "BPPPB"[i-1]
    else:
        if i == layer // 2 + 1:
            return "P"
        
        if i > layer // 2:
            i = layer - i + 1
        
        return calc(n-1, i, (layer-3) // 2)

ans = calc(N, X, layer)
print(ans)


Fixed submission:
N, X = map(int, input().split())

cntP = [0]*(N+1)
cntP[0] = 1
for i in range(1, N+1):
    cntP[i] = cntP[i-1] * 2 + 1

layer = 1
for _ in range(N):
    layer = layer * 2 + 3

def calc(n, i, layer):
    if i == 0:
        return 0
    
    if n == 1:
        return "BPPPB"[:i].count("P")
    else:
        if i == layer // 2 + 1:
            return cntP[n-1] + 1
        elif i > layer // 2 + 1:
            return cntP[n-1] + 1 + calc(n-1, i - (layer // 2 + 1), (layer-3) // 2)
        elif i < layer // 2 + 1:
            return calc(n-1, i-1, (layer-3) // 2)

ans = calc(N, X, layer)
print(ans)
Buggy python submission (verdict: Runtime Error):
# 最小公倍数
# ユークリッドの互除法
def lcm(a, b): 
    def gcd(a, b):  # a >= b
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    return a * b // gcd(a, b)

N, M = map(int, input().split())
S = input()
T = input()

l = lcm(N, M)

ans = ['.']*(l+1)
flag = True

for i in range(N):
    now = (l // N) * i + 1
    if ans[now] == '.':
        ans[now] = S[i]

for i in range(M):
    now = (l // M) * i + 1
    if ans[now] == '.':
        ans[now] = T[i]
    else:
        if ans[now] != T[i]:
            flag = False
            break

if flag:
    print(l)
else:
    print(-1)



Fixed submission:
# 最小公倍数
# ユークリッドの互除法
def lcm(a, b): 
    def gcd(a, b):  # a >= b
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    return a * b // gcd(a, b)

N, M = map(int, input().split())
S = input()
T = input()

l = lcm(N, M)

ans = {}
flag = True

for i in range(N):
    now = (l // N) * i + 1
    ans[now] = S[i]

for i in range(M):
    now = (l // M) * i + 1
    if now in ans:
        if ans[now] != T[i]:
            flag = False
            break

if flag:
    print(l)
else:
    print(-1)

Buggy python submission (verdict: Runtime Error):
# 最小公倍数
# ユークリッドの互除法
def lcm(a, b): 
    def gcd(a, b):  # a >= b
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    return a * b // gcd(a, b)

N, M = map(int, input().split())
S = input()
T = input()

l = lcm(N, M)

ans = ['.']*(l+1)
flag = True

for i in range(N):
    now = (l // N) * i + 1
    if ans[now] == '.':
        ans[now] = S[i]

for i in range(M):
    now = (l // M) * i + 1
    if ans[now] == '.':
        ans[now] = T[i]
    else:
        if ans[now] != T[i]:
            flag = False
            break

for i in range(1, l+1):
    if ans[i] == '.':
        ans[i] = 'a'

if flag:
    print(len("".join(ans[1:])))
else:
    print(-1)


Fixed submission:
# 最小公倍数
# ユークリッドの互除法
def lcm(a, b): 
    def gcd(a, b):  # a >= b
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    return a * b // gcd(a, b)

N, M = map(int, input().split())
S = input()
T = input()

l = lcm(N, M)

ans = {}
flag = True

for i in range(N):
    now = (l // N) * i + 1
    ans[now] = S[i]

for i in range(M):
    now = (l // M) * i + 1
    if now in ans:
        if ans[now] != T[i]:
            flag = False
            break

if flag:
    print(l)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
# def makelist(n, m):
#     return [[0 for i in range(m)] for j in range(n)]

N, X = map(int, input().split())
x = list(map(int, input().split()))

# ユークリッドの互除法
def gcd(a, b):  # a >= b
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

    
x.sort()
sa = [0]*(N-1)
for i in range(N-1):
    sa[i] = x[i+1] - x[i]
    
for i in range(1, N-1):
    sa[i] = gcd(sa[i-1], sa[i])

print(sa[-1])


Fixed submission:
# def makelist(n, m):
#     return [[0 for i in range(m)] for j in range(n)]

N, X = map(int, input().split())
x = [X] + list(map(int, input().split()))

# ユークリッドの互除法
def gcd(a, b):  # a >= b
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

    
x.sort()
sa = [0]*(N)
for i in range(N):
    sa[i] = x[i+1] - x[i]
    
for i in range(1, N):
    sa[i] = gcd(sa[i-1], sa[i])

print(sa[-1])
Buggy python submission (verdict: Runtime Error):
X = int(input())
if X == 1:
    print(1)
else:
    ans = 1
    for i in range(2, X+1):
        for k in range(2, 10):
            now = i ** k
            if now <= X:
                ans = max(ans, now)
print(ans)


Fixed submission:
X = int(input())
if X == 1:
    print(1)
else:
    ans = 1
    for i in range(2, X+1):
        for k in range(2, 10):
            now = i ** k
            if now <= X:
                ans = max(ans, now)
    print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
ans = "Four" if 'Y' in list(map(int, input().split())) else "Three"
print(ans)


Fixed submission:
N = int(input())
ans = "Four" if 'Y' in list(input().split()) else "Three"
print(ans)
Buggy python submission (verdict: Runtime Error):
N, Z, W = map(int, input().split())
a = list(map(int, input().split()))

if N == 1:
    print(a[0] - W)
else:
    x = abs(a[-2] - a[-1])
    y = abs(a[-1] - W)
    z = min(abs(max(A) - A[-1]), abs(a[-2]-a[-1]))
    w = min(abs(min(A) - A[-1]), abs(a[-2]-a[-1]))
    
    ans = max(x, y)
    print(ans)


Fixed submission:
N, Z, W = map(int, input().split())
a = list(map(int, input().split()))

if N == 1:
    print(abs(a[0] - W))
else:
    x = abs(a[-2] - a[-1])
    y = abs(a[-1] - W)
    
    ans = max(x, y)
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# def makelist(n, m):
#     return [[0 for i in range(m)] for j in range(n)]

# n = int(input())
# a, b = map(int, input().split())
# s = input()


N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))

D.sort()
T.sort()

i = 0
ans = "YES"
for e in T:
    while True:
        if i >= N:
            ans = "NO"
            break
        else:
            if D[i] != e:
                i += 1

    if ans == "NO":
        break
print(ans)


Fixed submission:
N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))

D.sort()
T.sort()

i = 0
ans = "YES"
for e in T:
    flag = True
    while flag:
        if i >= N:
            ans = "NO"
            break
        else:
            if D[i] == e:
                flag = False
            i += 1

    if ans == "NO":
        break
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())

maxm = 0
num = -1

for i in range():
    a, b = map(int, input().split())
    if a > maxm:
        maxm = a
        num = b

print(maxm + num)

Fixed submission:
n = int(input())

maxm = 0
num = -1

for i in range(n):
    a, b = map(int, input().split())
    if a > maxm:
        maxm = a
        num = b

print(maxm + num)
Buggy python submission (verdict: Runtime Error):
N = int(input())

if N == 1:
    print(0)
else:
    ans = 2
    while ans * 2 <= N:
        ans *= 2
print(ans)


Fixed submission:
N = int(input())
 
if N == 1:
    print(1)
else:
    ans = 2
    while ans * 2 <= N:
        ans *= 2
    print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(reversed(map(int, input().split())))

dp = [0]*n
for i in range(n):
    now = a[i]
    if i%2 == 0:
        dp[i//2] = now
    else:
        dp[-(i//2 + 1)] = now
print(" ".join(map(str, a)))


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

dp = [0]*n
for i in range(n):
    now = a[i]
    if i%2 == 0:
        dp[i//2] = now
    else:
        dp[-(i//2 + 1)] = now
print(" ".join(map(str, dp)))
Buggy python submission (verdict: Runtime Error):
a, b, c = map(int, input().split())
ans = (a[0]+b[0]+c[0]).upper()
print(ans)

Fixed submission:
a, b, c = input().split()
ans = (a[0]+b[0]+c[0]).upper()
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

num = int(1e5)

dp = [0]*(num+1)

for e in A:
  dp[e] += 1

cnt = 0
maxm = 0
for i in range(1, num+1):
  if dp[i] > 1:
    cnt += dp[i] - 1
    maxm = max(maxm, dp[i] - 1)

if maxm * 2 > N // 2:
  print(ans)
if maxm > cnt // 2:
  ans = N - (maxm-(cnt-maxm)) * 2
  if ans <= 0:
    ans = 1
else:
  ans = N - (cnt + (cnt%2)*2)
print(ans)


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

num = int(1e5)

dp = [0]*(num+1)

for e in A:
  dp[e] += 1

cnt = 0
for i in range(1, num+1):
  if dp[i] > 1:
    cnt += dp[i] - 1

ans = N - (cnt + (cnt%2))
print(ans)

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

num = int(1e5)

dp = [0]*(num+1)

for e in A:
  dp[e] += 1

cnt = 0
maxm = 0
for i in range(1, num+1):
  if dp[i] > 1:
    cnt += dp[i] - 1
    maxm = max(maxm, dp[i] - 1)

if maxm * 2 > N // 2:
  print(ans)
if maxm > cnt // 2:
  ans = N - (maxm-(cnt-maxm)) * 2
  print(cnt, maxm)
  if ans <= 0:
    ans = 1
else:
  ans = N - (cnt + (cnt%2)*2)
print(ans)


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

num = int(1e5)

dp = [0]*(num+1)

for e in A:
  dp[e] += 1

cnt = 0
for i in range(1, num+1):
  if dp[i] > 1:
    cnt += dp[i] - 1

ans = N - (cnt + (cnt%2))
print(ans)
Buggy python submission (verdict: Runtime Error):
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

# n = int(input())
# a, b = map(int, input().split())
# s = input()


K, T = map(int, input().split())
hoge = list(map(int, input().split()))

a = [0]*T
for i in range(T):
	a[i] = (hoge[i], i)

if T == 1:
	print(K-1)
else:
	a.sort()
	a[-1] = (a[-1][0] - 1, a[-1][1])
	pre = a[-1][1]

	while True:
		a.sort()
		if a[-1][0] == 0:
			print(0)
			raise NameError('error')
			break
		elif a[-1][1] != pre:
			a[-1] = (a[-1][0] - 1, a[-1][1])
			pre = a[-1][1]
		else:
			if a[-2][0] == 0:
				print(a[-1][1])
				break
			else:
				a[-2] = (a[-2][0] - 1, a[-2][1])
				pre = a[-2][1]


Fixed submission:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

# n = int(input())
# a, b = map(int, input().split())
# s = input()

MOD = int(1e9) + 7
n = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))

Tsa = [0]*n
Asa = [0]*n

if n == 1:
	if T[0] != A[0]:
		print(0)
	else:
		print(1)
elif T[-1] != A[0]:
	print(0)
else:
	##
	dai = T[0]
	shou = T[0]
	Tsa[0] = (shou, dai)

	for i in range(1, n):
		if T[i] == dai:
			Tsa[i] = (1, dai)
		else:
			dai = T[i]
			Tsa[i] = (dai, dai)

	##
	dai = A[-1]
	shou = A[-1]
	Asa[-1] = (shou, dai)

	for i in reversed(range(-n, -1)):
		if A[i] == dai:
			Asa[i] = (1, dai)
		else:
			dai = A[i]
			Asa[i] = (dai, dai)

	##
	ans = 1
	for i in range(n):
		d = max(Tsa[i][0], Asa[i][0])
		u = min(Tsa[i][1], Asa[i][1])

		if d > u:
			ans = 0
			break
		else:
			ans *= u - d + 1
			ans %= MOD
	print(ans)
Buggy python submission (verdict: Runtime Error):
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

# n = int(input())
# a, b = map(int, input().split())
# s = input()


rei = "CODEFESTIVAL2016"
s = input()

ans = 0
for i in range(s):
	if rei[i] != s[i]:
		ans += 1

print(ans)


Fixed submission:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

# n = int(input())
# a, b = map(int, input().split())
# s = input()


rei = "CODEFESTIVAL2016"
s = input()

ans = 0
for i in range(len(s)):
	if rei[i] != s[i]:
		ans += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

n = int(input())
A = [0]*N
for i in range(N):
	A[i] = int(input())

ans = A[0] - 1
A[0] = 1

cnt = 1
# yobi = 1

for i in range(1, N):
	now = A[i]

	if now > cnt:
		if now == cnt + 1: ## 0 ni nattyau
			cnt += 1
		else: ## now >= cnt + 2
			ans += now // (cnt + 1)
			if now % (cnt + 1) == 0:
				ans -= 1

print(ans)


Fixed submission:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

N = int(input())
A = [0]*N
for i in range(N):
	A[i] = int(input())

ans = A[0] - 1
A[0] = 1

cnt = 1
# yobi = 1

for i in range(1, N):
	now = A[i]

	if now > cnt:
		if now == cnt + 1: ## 0 ni nattyau
			cnt += 1
		else: ## now >= cnt + 2
			ans += now // (cnt + 1)
			if now % (cnt + 1) == 0:
				ans -= 1

print(ans)
Buggy python submission (verdict: Runtime Error):
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

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


par = [0]*202020
size = [0]*202020

def find(x):
	if par[x] == x:
		return x
	else:
		par[x] = find(par[x])
		return par[x]

def unite(x, y):
	x = find(x)
	y = find(y)
	res = size[x] * size[y]
	size[x] += size[y]
	par[y] = x
	return res

# main
n = int(input())
for i in range(202020):
	par[i] = i
	size[i] = 1

a = [0] + list(map(int, input().split()))
b = [0]*(n+1)
for i in range(1, n+1):
	b[a[i]] = i

ans = 0
for j in reversed(1, n+1):
	i = b[j]
	ans += a[i]
	if i - 1 >= 1 and a[i-1] > a[i]:
		ans += unite(i-1, i) * a[i]
	if i + 1 <= n and a[i+1] > a[i]:
		ans += unite(i+1, i) * a[i]
print(ans)


Fixed submission:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

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


par = [0]*202020
size = [0]*202020

def find(x):
	if par[x] == x:
		return x
	else:
		par[x] = find(par[x])
		return par[x]

def unite(x, y):
	x = find(x)
	y = find(y)
	res = size[x] * size[y]
	size[x] += size[y]
	par[y] = x
	return res

# main
n = int(input())
for i in range(202020):
	par[i] = i
	size[i] = 1

a = [0] + list(map(int, input().split()))
b = [0]*(n+1)
for i in range(1, n+1):
	b[a[i]] = i

ans = 0
for j in reversed(range(1, n+1)):
	i = b[j]
	ans += a[i]
	if i - 1 >= 1 and a[i-1] > a[i]:
		ans += unite(i-1, i) * a[i]
	if i + 1 <= n and a[i+1] > a[i]:
		ans += unite(i+1, i) * a[i]
print(ans)
Buggy python submission (verdict: Runtime Error):
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

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


s = input()
l = len(s)

ans = 0

m = int('1'*(l-1), 2)
for i in range(m+1):
	now = format(i, 'b').zfill(l-1)
	tmp = s[0]
	for k in range(l-1):
		if now[k] == '0':
			tmp += s[k+1]
		else:
			ans += int(tmp)
			tmp = s[k+1]
	ans += int(tmp)
print(ans)


Fixed submission:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

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


s = input()
l = len(s)

if l == 1:
	print(int(s))
else:
	ans = 0

	m = int('1'*(l-1), 2)
	for i in range(m+1):
		now = format(i, 'b').zfill(l-1)
		tmp = s[0]
		for k in range(l-1):
			if now[k] == '0':
				tmp += s[k+1]
			else:
				ans += int(tmp)
				tmp = s[k+1]
		ans += int(tmp)
	print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, x = map(int, input().split())
a = list(map(int, input().split()))

ans = sum(a)
b = a[:]
c = [0]*n

for k in range(1, n):
	now = k * x
	for i in range(n):
		tmp = min(b[i-1], a[i])
		now += tmp
		c[i] = tmp
	ans = min(ans, now)
	b = c[:]
	
print(ans)

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

ans = sum(a)
b = a[:]
c = [0]*n

for k in range(1, n):
	now = k * x
	for i in range(n):
		tmp = min(b[i-1], a[i])
		now += tmp
		c[i] = tmp
	ans = min(ans, now)
	b = c[:]
	
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def makelist(n, m, p):
	return [[[0 for k in range(p)] for i in range(m)] for j in range(n)]

N, A = map(int, input().split())
x = list(map(int, input().split()))

dp = makelist(N+1, N+1, N*A+1)
dp[0][0][0] = 1
for i in range(N):
	for j in range(i+1):
		for k in range(N*A):
			if k + x[i] <= N * A:
				dp[i+1][j+1][k+x[i]] += dp[i][j][k]
			dp[i+1][j][k] += dp[i][j][k]

ans = 0
for i in range(1, N+1):
	ans += dp[N][i][i*A]

print(ans)


Fixed submission:
def makelist(n, m, p):
	return [[[0 for k in range(p)] for i in range(m)] for j in range(n)]

N, A = map(int, input().split())
x = list(map(int, input().split()))

dp = makelist(N+1, N+1, N*A+1)
dp[0][0][0] = 1
for i in range(N):
	for j in range(i+1):
		for k in range(N*A):
			if k + x[i] <= N * A:
				dp[i+1][j+1][k+x[i]] += dp[i][j][k]
			dp[i+1][j][k] += dp[i][j][k]

ans = 0
for i in range(1, N+1):
	ans += dp[N][i][i*A]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
b, c = map(int, input().split())
ans = 1
while b <= c:
	ans *= b
	b += 1

if ans > 0:
	print("Positive")
elif ans < 0:
	print("Negative")
else:
	print("Zero")


Fixed submission:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

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


b, c = map(int, input().split())
ans = 1

if b == 0 or c == 0 or (b < 0 and c > 0):
	ans = 0
elif b > 0 and c > 0:
	ans = 1
else:
	tmp = abs(b) - abs(c)
	if tmp % 2 == 0:
		ans = -1
	else:
		ans = 1

if ans > 0:
	print("Positive")
elif ans < 0:
	print("Negative")
else:
	print("Zero")
Buggy python submission (verdict: Runtime Error):
def down_score(d, c, last_d, score):
    sum = 0
    for i in range(26):
        sum += c[i]*(d-last_d[i])
        
    return (score - sum)


def main():
    D = int(input())

    c = list(map(int, input().split()))

    s = [list(map(int, input().split())) for i in range(D)]

    sche = []
    for i in range(D):
        x = int(input())
        sche.append(x)
    
    last_d = [0 for i in range(26)]
    score = 0
    
    for i in range(D):
        score += s[i][sche[i]]
        last_d[sche[i]] = i+1
        score = down_score(i+1, c, last_d, score)
        print(score)
        
if __name__ == "__main__":
    main()


Fixed submission:
import random

def down_score(d, c, last_d, score):
    sum = 0
    for i in range(26):
        sum = sum + c[i]*(d-last_d[i])
        
    return int(score - sum)


def main():
    D = int(input())

    c = list(map(int, input().split()))

    s = [list(map(int, input().split())) for i in range(D)]

    sche = []
    for i in range(D):
        x = int(input())
        sche.append(x)
    
    last_d = [0 for i in range(26)]
    score = 0
    
    for i in range(D):
        score += s[i][sche[i]-1]
        last_d[sche[i]-1] = i+1
        score = down_score(i+1, c, last_d, score)
        print(score)
        
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import math
def comb(n,r):
	if n < r:
		return 0
	return int(math.factorial(n) / (math.factorial(r) * math.factorial(n-r)))


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

a = sorted(a)

r = 0
maxV = 0
for i in range(max(0,n//2-2),min(n-1,n//2+2)):
	curr = comb(a[-1],a[i])
	if maxV < curr:
		r = a[i]
		maxV = curr

print(a[-1], r)

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

a = sorted(a)

r = 0
minV = 10**10
for i in range(n-1):
	curr = abs(a[-1] / 2 - a[i])
#	print(a[-1],a[i],curr)
	if minV > curr:
		r = a[i]
		minV = curr

print(a[-1], r)
Buggy python submission (verdict: Runtime Error):
def dfs(s):
	global x, G
	for t, d in G[s]:
		if x[t] is None:
			x[t] = x[s] + d
			if not dfs(t):
				return False
		else:
			if x[t] != x[s] + d:
				return False
	return True

N,M = map(int,input().split())
x = [None] * N
G = [[] for _ in range(N)]
for i in range(M):
	L, R, D = map(int,input().split())
	G[L-1].append([R-1,D])
	G[R-1].append([L-1,-D])

res = True
for i in range(N):
	if x[i] is None:
		x[i] = 0
		res &= dfs(i)

print("Yes" if res == True else "No")

Fixed submission:
NOT_VISIT = 10**20
N, M = map(int,input().split())
graph = [[] for i in range(N)]

for i in range(M):
	L, R, D = map(int,input().split())
	graph[L-1].append((R-1,D))
	graph[R-1].append((L-1,-D))

visited = [NOT_VISIT for i in range(N)]

def dfs(start):
	global graph, visited

	if visited[start] != NOT_VISIT:
		return True

	stack = [start]
	visited[start] = 0
	while stack:
		label = stack.pop()
		for nextnode, distance in graph[label]:
			if visited[nextnode] == NOT_VISIT:
				stack.append(nextnode)
				visited[nextnode] = visited[label] + distance
			elif visited[nextnode] != visited[label] + distance:
				return False
	return True

res = True
for i in range(N):
	res &= dfs(i)

print("Yes" if res == True else "No")

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int,input().split())
L = [0] * M
R = [0] * M
D = [0] * M
for i in range(M):
	L[i],R[i],D[i] = map(int,input().split())
#	print(L[i],R[i],D[i])
leftside = 0
cand = set()
for i in range(M):
	cand.add(L[i])
for i in range(M):
	if R[i] in cand:
		cand.remove(R[i])

res = True
if M == 0:
	res = True
else:
	if len(cand) == 0:
		res = False
	else:
		leftside = list(cand)
#		print("leftside:",leftside)
		ok = True
		for c in leftside:
			point = [-1] * (N+1)
			point[c] = 0
			ok = True
			while True:
				update = False
				for i in range(M):
					if point[L[i]] != -1:
						if point[R[i]] == -1:
							update = True
							point[R[i]] = point[L[i]] + D[i]
						else:
							if point[R[i]] != point[L[i]] + D[i]:
								ok = False
								break
				if update == False:
					break
				res &= ok
					
print("Yes" if res == True else "No")

Fixed submission:
NOT_VISIT = 10**20
N, M = map(int,input().split())
graph = [[] for i in range(N)]

for i in range(M):
	L, R, D = map(int,input().split())
	graph[L-1].append((R-1,D))
	graph[R-1].append((L-1,-D))

visited = [NOT_VISIT for i in range(N)]

def dfs(start):
	global graph, visited

	if visited[start] != NOT_VISIT:
		return True

	stack = [start]
	visited[start] = 0
	while stack:
		label = stack.pop()
		for nextnode, distance in graph[label]:
			if visited[nextnode] == NOT_VISIT:
				stack.append(nextnode)
				visited[nextnode] = visited[label] + distance
			elif visited[nextnode] != visited[label] + distance:
				return False
	return True

res = True
for i in range(N):
	res &= dfs(i)

print("Yes" if res == True else "No")
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

res = 0
for i in range(N):
	indB = bisect.bisect_right(B,A[i])
	for j in range(indB,N):
		indC = bisect.bisect_right(C,B[j])
		ansC = N - indC
		res += ansC

print(res)

Fixed submission:
import bisect
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

res = 0
for j in range(N):
	indA = bisect.bisect_left(A,B[j])
	ansA = indA
	indC = bisect.bisect_right(C,B[j])
	ansC = N - indC
	res += ansA * ansC

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
a=[0]*N
s=set()
for i in range(N):
	a[i] = int(input())
	s.add(a[i])
res=0
for j in s:
	res += (1 if not a.count(j) % 2 == 0 else 0)

print(res)

Fixed submission:
N=int(input())
a=[0]*N
s={}
for i in range(N):
	a[i] = int(input())
	if a[i] not in s:
		s[a[i]] = 1
	else:
		s[a[i]] += 1

res=0
for key,value in s.items():
#	print(key,value)
	res += (1 if not value % 2 == 0 else 0)

print(res)