Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import math
import sys
sys.setrecursionlimit(100000000)

n, k = list(map(int, input().split()))
ls = [list(map(int, input().split())) for _ in range(n - 1)]
qs = [list(map(int, input().split())) for _ in range(k)]

ws = [0 for _ in range(n)]
for q in qs:
	ws[q[0] - 1] += q[1]

ds = [[] for _ in range(n)]
for l in ls:
	ds[l[0] - 1].append(l[1] - 1)

ans = [0 for _ in range(n)]

def dfs(x, v):
	ans[x] = ws[x] + v
	if len(ds[x]) > 0:
		for nxt in ds[x]:
			dfs(nxt, ans[x])

dfs(0, 0)

print(*ans)


Fixed submission:
n, k = list(map(int, input().split()))
ls = [list(map(int, input().split())) for _ in range(n - 1)]
qs = [list(map(int, input().split())) for _ in range(k)]

ws = [0 for _ in range(n)]
for q in qs:
	ws[q[0] - 1] += q[1]

ds = [[] for _ in range(n)]
for l in ls:
	ds[l[0] - 1].append(l[1] - 1)

for i in range(0, n):
	for x in ds[i]:
		ws[x] += ws[i]

for i in range(n):
	print(ws[i])

Buggy python submission (verdict: Time Limit Exceeded):
import math
import sys
sys.setrecursionlimit(100000000)

n, k = list(map(int, input().split()))
ls = [list(map(int, input().split())) for _ in range(n - 1)]
qs = [list(map(int, input().split())) for _ in range(k)]

# n = 2 * 10 ** 5
# k = 2 * 10 ** 5
# ls = [[i + 1, i + 2] for i in range(n - 1)]
# qs = [[i + 1, 10] for i in range(k)]

ws = [0 for _ in range(n)]
for q in qs:
	ws[q[0] - 1] += q[1]

ds = [[] for _ in range(n)]
for l in ls:
	ds[l[0] - 1].append(l[1] - 1)

ans = [0 for _ in range(n)]

def dfs(x, v):
	global ans
	ans[x] = ws[x] + v
	if len(ds[x]) > 0:
		for nxt in ds[x]:
			dfs(nxt, ans[x])

dfs(0, 0)

#print(ws)
#print(ds)

for i in range(n):
	print(ans[i])


Fixed submission:
n, k = list(map(int, input().split()))
ls = [list(map(int, input().split())) for _ in range(n - 1)]
qs = [list(map(int, input().split())) for _ in range(k)]

ws = [0 for _ in range(n)]
for q in qs:
	ws[q[0] - 1] += q[1]

ds = [[] for _ in range(n)]
for l in ls:
	ds[l[0] - 1].append(l[1] - 1)

for i in range(0, n):
	for x in ds[i]:
		ws[x] += ws[i]

for i in range(n):
	print(ws[i])

Buggy python submission (verdict: Time Limit Exceeded):
import math
import sys
sys.setrecursionlimit(100000)

n, k = list(map(int, input().split()))
ls = [list(map(int, input().split())) for _ in range(n - 1)]
qs = [list(map(int, input().split())) for _ in range(k)]

ws = [0 for _ in range(n)]
for q in qs:
	ws[q[0] - 1] += q[1]

ds = [[] for _ in range(n)]
for l in ls:
	ds[l[0] - 1].append(l[1] - 1)

ans = [0 for _ in range(n)]

def dfs(x, v, ans):
	ans[x] = ws[x] + v
	if len(ds[x]) > 0:
		for nxt in ds[x]:
			ans = dfs(nxt, ans[x], ans)
	return ans

ans = dfs(0, 0, ans)

#print(ws)
#print(ds)

for i in range(n):
	print(ans[i])


Fixed submission:
n, k = list(map(int, input().split()))
ls = [list(map(int, input().split())) for _ in range(n - 1)]
qs = [list(map(int, input().split())) for _ in range(k)]

ws = [0 for _ in range(n)]
for q in qs:
	ws[q[0] - 1] += q[1]

ds = [[] for _ in range(n)]
for l in ls:
	ds[l[0] - 1].append(l[1] - 1)

for i in range(0, n):
	for x in ds[i]:
		ws[x] += ws[i]

for i in range(n):
	print(ws[i])
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

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

colors = []
min_val = 10 ** 10
for num in nums:
	if num <= min_val:
		colors.insert(0, num)
		min_val = num
	else:
		idx_r = bisect.bisect_right(colors, num - 0.5) - 1
		colors[idx_r] = num
		min_val = max(colors[0], min_val)

print(len(colors))


Fixed submission:
import bisect

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

colors = []
max_val = -1 * (10 ** 10)
for num in nums:
	if num >= max_val:
		colors.append(num)
		max_val = num
	else:
		idx_r = bisect.bisect_right(colors, num)
		colors[idx_r] = num
		max_val = min(colors[-1], max_val)

print(len(colors))
Buggy python submission (verdict: Runtime Error):
n,a,b=map(int,input().split())
print min(n*a,b)

Fixed submission:
n,a,b=list(map(int,input().split()))
print(min(n*a,b))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = list(map(int, input().split()))
mod = 10 ** 9 + 7

m = n ** 0.5
cnt = [n // i - n // (i + 1) for i in range(1, int(m) + 1)] 
cnt = (cnt + [1 for _ in range(n - sum(cnt))])[::-1]
nxt = cnt[:]

for _ in range(k - 1):
	cnt = [sum([x * nxt[i] % mod for x in cnt[:(len(cnt) - i)]])  for i in range(len(cnt))]
print(sum(cnt) % mod)


Fixed submission:
import numpy as np
n, k = list(map(int, input().split()))
mod = 10 ** 9 + 7

m = n ** 0.5
cnt = [n // i - n // (i + 1) for i in range(1, int(m) + 1)] 
cnt = np.array((cnt + [1 for _ in range(n - sum(cnt))])[::-1])
nxt = cnt[:]
for _ in range(k - 1):
	cnt = nxt * np.cumsum(cnt)[::-1] % mod

print(sum(cnt) % mod)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = list(map(int, input().split()))
mod = 10 ** 9 + 7

m = n ** 0.5
cnt = [n // i - n // (i + 1) for i in range(1, int(m) + 1)] 
cnt = (cnt + [1 for _ in range(n - sum(cnt))])[::-1]
nxt = cnt[:]

for _ in range(k - 1):
	cnt = [sum([x * nxt[i] % mod for x in cnt[:(len(cnt) - i)]])  for i in range(len(cnt))]
print(sum(cnt) % mod)


Fixed submission:
import numpy as np
n, k = list(map(int, input().split()))
mod = 10 ** 9 + 7

m = n ** 0.5
cnt = [n // i - n // (i + 1) for i in range(1, int(m) + 1)] 
cnt = np.array((cnt + [1 for _ in range(n - sum(cnt))])[::-1])
nxt = cnt[:]
for _ in range(k - 1):
	cnt = nxt * np.cumsum(cnt)[::-1] % mod

print(sum(cnt) % mod)
Buggy python submission (verdict: Runtime Error):
n, l = list(map(int, input().split()))
ts = [l + i - 1 for i in range(1, n + 1)]
print(sum(ts) + min([abs(x) for x in ts]))

Fixed submission:
from fractions import gcd
from decimal import *

a, b, c, d = list(map(Decimal, input().split()))
e = c * d / gcd(c, d)
print(int(b - a + 1 - ((b // c + b // d - b // e) - ((a - 1) // c + (a - 1) // d - (a - 1) // e))))
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

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

d = defaultdict(lambda: 0)
for x in range(n):
	for y in range(n):
		d[(balls[x][0] - balls[y][0], balls[x][1] - balls[y][1])] += 1

del d[(0, 0)]
print(n - max(d.values()))

Fixed submission:
from collections import defaultdict

n = int(input())
if n == 1:
	print(1)
else:
	balls = [list(map(int, input().split())) for _ in range(n)]

	d = defaultdict(lambda: 0)
	for x in range(n):
		for y in range(n):
			d[(balls[x][0] - balls[y][0], balls[x][1] - balls[y][1])] += 1

	del d[(0, 0)]
	print(n - max(d.values()))
Buggy python submission (verdict: Runtime Error):
mod = 1000000007

n, m = list(map(int, input().split()))
nums = [int(input()) for _ in range(m)]
 
dp = [1] + [0 for _ in range(n)]

if nums[0] == 1:
	del nums[0]
else:
	dp[1] = 1
	

for i in range(2, n + 1):
	#print(i, dp, nums)
	if len(nums) ==  0:
		dp[i] = (dp[i - 1] + dp[i - 2]) % mod
	else:
		for j in range(len(nums)):
			if nums[j] > i:
				dp[i] = (dp[i - 1] + dp[i - 2]) % mod
				break
			elif nums[j] == i:
				del nums[:(j + 1)]
				break
#print(nums)
#print(dp)
print(dp[-1])


Fixed submission:
mod = 1000000007

n, m = list(map(int, input().split()))
nums = [int(input()) for _ in range(m)]
 
dp = [1] + [0 for _ in range(n)]

if len(nums) > 0 and nums[0] == 1:
	del nums[0]
else:
	dp[1] = 1
	

for i in range(2, n + 1):
	#print(i, dp, nums)
	if len(nums) ==  0:
		dp[i] = (dp[i - 1] + dp[i - 2]) % mod
	else:
		for j in range(len(nums)):
			if nums[j] > i:
				dp[i] = (dp[i - 1] + dp[i - 2]) % mod
				break
			elif nums[j] == i:
				del nums[:(j + 1)]
				break
#print(nums)
#print(dp)
print(dp[-1])

Buggy python submission (verdict: Runtime Error):
mod = 1000000007

n, m = list(map(int, input().split()))
nums = [int(input()) for _ in range(m)]
 
dp = [1] + [0 for _ in range(n)]

if nums[0] == 1:
	del nums[0]
else:
	dp[1] = 1
	

for i in range(2, n + 1):
	#print(i, dp, nums)
	if len(nums) ==  0:
		dp[i] = (dp[i - 1] + dp[i - 2]) % mod
	else:
		for j in range(len(nums)):
			if nums[j] > i:
				dp[i] = (dp[i - 1] + dp[i - 2]) % mod
				break
			elif nums[j] == i:
				del nums[:(j + 1)]
				break
#print(nums)
#print(dp)
print(dp[-1])

Fixed submission:
mod = 1000000007

n, m = list(map(int, input().split()))
nums = [int(input()) for _ in range(m)]
 
dp = [1] + [0 for _ in range(n)]

if len(nums) > 0 and nums[0] == 1:
	del nums[0]
else:
	dp[1] = 1
	

for i in range(2, n + 1):
	#print(i, dp, nums)
	if len(nums) ==  0:
		dp[i] = (dp[i - 1] + dp[i - 2]) % mod
	else:
		for j in range(len(nums)):
			if nums[j] > i:
				dp[i] = (dp[i - 1] + dp[i - 2]) % mod
				break
			elif nums[j] == i:
				del nums[:(j + 1)]
				break
#print(nums)
#print(dp)
print(dp[-1])

Buggy python submission (verdict: Runtime Error):
import bisect
mod = 1000000007

n, m = list(map(int, input().split()))
nums = [int(input()) for _ in range(m)]
 
dp = [1] + [0 for _ in range(n)]

if nums[0] != 1:
	dp[1] = 1
	idx = bisect.bisect_right(nums, 1)
	nums = nums[idx:]

for i in range(2, n + 1):
	if i in nums:
		dp[i] = 0
		idx = bisect.bisect_right(nums, 1)
		nums = nums[idx:]
	else:
		dp[i] = (dp[i - 1] + dp[i - 2])  % mod

print(dp[-1])



Fixed submission:
mod = 1000000007

n, m = list(map(int, input().split()))
nums = [int(input()) for _ in range(m)]
 
dp = [1] + [0 for _ in range(n)]

if len(nums) > 0 and nums[0] == 1:
	del nums[0]
else:
	dp[1] = 1
	

for i in range(2, n + 1):
	#print(i, dp, nums)
	if len(nums) ==  0:
		dp[i] = (dp[i - 1] + dp[i - 2]) % mod
	else:
		for j in range(len(nums)):
			if nums[j] > i:
				dp[i] = (dp[i - 1] + dp[i - 2]) % mod
				break
			elif nums[j] == i:
				del nums[:(j + 1)]
				break
#print(nums)
#print(dp)
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n, q = list(map(int, input().split()))
rws = [list(map(int, input().split())) for _ in range(n)]
ds = [int(input()) for _ in range(q)]

rws.sort(key = lambda x: x[2])
ans = [-1 for _ in range(q)]
for rw in rws:
	st = bisect.bisect_left(ds, rw[0] - rw[2])
	en = bisect.bisect_left(ds, rw[1] - rw[2])
	while st < en:
		if ans[st] == -1:
			ans[st] = rw[2]
		st += 1

for a in ans:
	print(a)

Fixed submission:
import bisect

n, q = list(map(int, input().split()))
rws = [list(map(int, input().split())) for _ in range(n)]
ds = [int(input()) for _ in range(q)]

rws.sort(key = lambda x: x[2])

ans = [-1 for _ in range(q)]
nxt = [-1 for _ in range(q)]
for rw in rws:
	st = bisect.bisect_left(ds, rw[0] - rw[2])
	en = bisect.bisect_left(ds, rw[1] - rw[2])
	while st < en:
		if nxt[st] == -1:
			ans[st] = rw[2]
			nxt[st] = en
			st += 1
		else:
			st = nxt[st]

for a in ans:
	print(a)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
edges = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	u, v, w = list(map(int, input().split()))
	edges[u].append([v, w % 2])
	edges[v].append([u, w % 2])


bw = [-1 for i in range(n + 1)]
bw[1] = 0

def dfs(frm):
	for ne in edges[frm]:
		if bw[ne[0]] >= 0:
			continue
		else:
			bw[ne[0]] = abs(bw[frm] - ne[1])
			dfs(ne[0])

dfs(1)
for i in range(1, n + 1):
	print(bw[i])


Fixed submission:
n, k = list(map(int, input().split()))
s = list(input())
d = {"A":"a", "B":"b", "C":"c"}
s[k-1] = d[s[k-1]]
print("".join(s))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
edges = [list(map(int, input().split())) for _ in range(n - 1)]
bw = [-1 for i in range(n + 1)]
bw[1] = 0

def dfs(frm):
	tmp = []
	for e in edges[:]:
		if e[0] == frm:
			tmp.append([e[1], e[2]])
			edges.remove(e)
		elif e[1] == frm:
			tmp.append([e[0], e[2]])
			edges.remove(e)

	for t in tmp:
		if bw[t[0]] == -1:
			if t[1] % 2 == 0:
				bw[t[0]] = bw[frm]
			else:
				bw[t[0]] = abs(bw[frm] - 1)
			dfs(t[0])

dfs(1)

for i in range(1, n + 1):
	print(bw[i])

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
edges = [list(map(int, input().split())) for _ in range(n - 1)]
bw = [-1 for i in range(n + 1)]
bw[1] = 0

new_edges = [[] for _ in range(n + 1)]

for e in edges:
	new_edges[e[0]].append([e[1], e[2]]) 
	new_edges[e[1]].append([e[0], e[2]]) 

def dfs(frm, now):
	for ne in new_edges[now]:
		if ne[0] == frm:
			continue
		else:
			if ne[1] % 2 == 0:
				bw[ne[0]] = bw[now]
			else:
				bw[ne[0]] = abs(1 - bw[now])
			dfs(now, ne[0])

dfs(0, 1)

for i in range(1, n + 1):
	print(bw[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
edges = [list(map(int, input().split())) for _ in range(n - 1)]
bw = {1:0}

def dfs(frm, is_b):
	tmp = []
	for e in edges[:]:
		if e[0] == frm:
			tmp.append(e)
			edges.remove(e)
		elif e[1] == frm:
			tmp.append([e[1], e[0], e[2]])
			edges.remove(e)

	for t in tmp:
		if t[2] % 2 == 0:
			bw[t[1]] = is_b
		else:
			bw[t[1]] = abs(is_b - 1)
		dfs(t[1], bw[t[1]])

dfs(1, 0)

for i in range(1, n + 1):
	print(bw[i])


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
edges = [list(map(int, input().split())) for _ in range(n - 1)]
bw = [-1 for i in range(n + 1)]
bw[1] = 0

new_edges = [[] for _ in range(n + 1)]

for e in edges:
	new_edges[e[0]].append([e[1], e[2]]) 
	new_edges[e[1]].append([e[0], e[2]]) 

def dfs(frm, now):
	for ne in new_edges[now]:
		if ne[0] == frm:
			continue
		else:
			if ne[1] % 2 == 0:
				bw[ne[0]] = bw[now]
			else:
				bw[ne[0]] = abs(1 - bw[now])
			dfs(now, ne[0])

dfs(0, 1)

for i in range(1, n + 1):
	print(bw[i])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
stones = [0] + [0 if x == "." else 1 for x in list(input())] + [1]

min_num = 10 ** 6

for i in range(1, n + 2):
	tmp = sum(stones[:i]) + (len(stones[i:]) - sum(stones[i:]))
	#print(tmp, sum(stones[:i]), (len(stones[i:]) - sum(stones[i:])))
	min_num = min(min_num, tmp)

print(min_num)

Fixed submission:
n = int(input())
#n = 10 ** 5
stones = [0 if x == "." else 1 for x in list(input())]
#stones = [0] + [0 for _ in range(n)] + [1]

bf = 0
af = n - sum(stones)
min_num = bf + af

for i in range(n):
	bf += stones[i]
	af -= 1 - stones[i]
	min_num = min(min_num, bf + af)

print(min_num)
Buggy python submission (verdict: Runtime Error):
import numpy as np
import bisect

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

drinks.sort(key = lambda x: x[0])
prices = np.array([x[0] for x in drinks])
vols = np.array([x[1] for x in drinks])
cum_vols = np.cumsum(vols)
idx = bisect.bisect_right(cum_vols, m) #このidxは1 ~ vols[idx]を使う

vols[idx] = m - sum(vols[:idx])
print(np.dot(vols[:(idx+1)], prices[:(idx+1)]))


Fixed submission:
import numpy as np
import bisect

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

drinks.sort(key = lambda x: x[0])
prices = np.array([x[0] for x in drinks])
vols = np.array([x[1] for x in drinks])
cum_vols = np.cumsum(vols)
idx = bisect.bisect_left(cum_vols, m) #このidxは1 ~ vols[idx]を使う

#print(idx)
l = 0 if idx == 0 else sum(vols[:idx])

vols[idx] = m - l
print(np.dot(vols[:(idx+1)], prices[:(idx+1)]))
Buggy python submission (verdict: Runtime Error):
def main():
	n = int(input())

	if n <= 104:
		print(0):
	elif n <= 134:
		print(1)
	elif n <= 188:
		print(2)
	else:
		print(3)


if __name__ == '__main__':
	main()

Fixed submission:
def main():
	n = int(input())

	if n <= 104:
		print(0)
	elif n <= 134:
		print(1)
	elif n <= 164:
		print(2)
	elif n <= 188:
		print(3)
	elif n <= 194:
		print(4)
	else:
		print(5)


if __name__ == '__main__':
	main()
Buggy python submission (verdict: Time Limit Exceeded):
d, g = list(map(int, input().split()))
ps, cs = [], []
for i in range(d):
	p, c = list(map(int, input().split()))
	ps.append(p)
	cs.append(c)

def solve(sum_score, cnt, i, ans):
	if sum_score >= g:
		return min(ans, cnt)
	elif i < d:
		for j in range(ps[i]):
			ans = solve(sum_score + 100 * (i + 1) * j, cnt + j, i + 1, ans)
		ans = solve(sum_score + 100 * (i + 1) * ps[i] + cs[i], cnt + ps[i], i + 1, ans)
	return ans

print(solve(0, 0, 0, 10 ** 10))


Fixed submission:
import itertools

def main():
	d, g = list(map(int, input().split()))
	problems = [list(map(int, input().split())) for _ in range(d)]

	ptns = list(itertools.product([0, 1], repeat = d))

	ans = 10 ** 10

	for pt in ptns:
		rest = g - sum([((i + 1) * 100 * problems[i][0] + problems[i][1]) * pt[i] for i in range(d)])
		tmp = sum([problems[i][0] * pt[i] for i in range(d)])
		
		if rest > 0:
			if 0 in pt:
				rest_max_idx = d - pt[::-1].index(0) - 1
				#print(pt, tmp, rest_max_idx, rest)
				for i in range(problems[rest_max_idx][0]):
					rest -= (rest_max_idx + 1) * 100
					tmp += 1
					if rest <= 0:
						break

		if rest <= 0:
			ans = min(ans, tmp)

	print(ans)


if __name__ == '__main__':
	main()

Buggy python submission (verdict: Time Limit Exceeded):
d, g = list(map(int, input().split()))
ps, cs = [], []
for i in range(d):
	p, c = list(map(int, input().split()))
	ps.append(p)
	cs.append(c)

def solve(sum_score, cnt, i, ans):
	if sum_score >= g:
		return min(ans, cnt)
	elif i < d:
		for j in range(ps[i]):
			ans = solve(sum_score + 100 * (i + 1) * j, cnt + j, i + 1, ans)
		ans = solve(sum_score + 100 * (i + 1) * ps[i] + cs[i], cnt + ps[i], i + 1, ans)
	return ans

print(solve(0, 0, 0, 10 ** 10))


Fixed submission:
import itertools

def main():
	d, g = list(map(int, input().split()))
	problems = [list(map(int, input().split())) for _ in range(d)]

	ptns = list(itertools.product([0, 1], repeat = d))

	ans = 10 ** 10

	for pt in ptns:
		rest = g - sum([((i + 1) * 100 * problems[i][0] + problems[i][1]) * pt[i] for i in range(d)])
		tmp = sum([problems[i][0] * pt[i] for i in range(d)])
		
		if rest > 0:
			if 0 in pt:
				rest_max_idx = d - pt[::-1].index(0) - 1
				#print(pt, tmp, rest_max_idx, rest)
				for i in range(problems[rest_max_idx][0]):
					rest -= (rest_max_idx + 1) * 100
					tmp += 1
					if rest <= 0:
						break

		if rest <= 0:
			ans = min(ans, tmp)

	print(ans)


if __name__ == '__main__':
	main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
	n, m = list(map(int, input().split()))
	rqs = [list(map(int, input().split())) for _ in range(m)]

	rqs.sort(key = lambda x: x[1])

	cnt = 0
	while len(rqs) > 1:
		rqs = [x for x in rqs[1:] if x[0] >= rqs[0][1]]
		cnt += 1
		#print(rqs, cnt)

	if len(rqs) == 1:
		cnt += 1

	print(cnt)

if __name__ == '__main__':
	main()

Fixed submission:
def main():
	n, m = list(map(int, input().split()))
	rqs = [list(map(int, input().split())) for _ in range(m)]

	rqs.sort(key = lambda x: x[1])

	b = -1
	cnt = 0
	
	for x in rqs:
		if b < x[0]:
			b = x[1] - 1
			cnt += 1

	print(cnt)

if __name__ == '__main__':
	main()
Buggy python submission (verdict: Runtime Error):
import math

def main():
	t = int(input())
	qs = [list(map(int, input().split())) for _ in range(t)]
	for q in qs:
		sub(q)

def sub(q):
	a, b, c, d = q
	if d - b < 0:
		print("No")
		return
	
	if a - b < 0:
		print("No")
		return

	if b > c:
		gcd_bd = math.gcd(d, b)
		i = - 10
		while True:
			if 0 < gcd_bd * i + (a - c) % gcd_bd < b - c:
				print("No")
				return
			elif gcd_bd * i + (a - c) % gcd_bd >= b - c:
				print("Yes")
				return
			i += 1
				
	print("Yes")
	return
	
if __name__ == '__main__':
	main()

Fixed submission:
import fractions

def main():
	t = int(input())
	qs = [list(map(int, input().split())) for _ in range(t)]
	for q in qs:
		sub(q)

def sub(q):
	a, b, c, d = q
	if d - b < 0:
		print("No")
		return
	
	if a - b < 0:
		print("No")
		return

	if b > c:
		gcd_bd = fractions.gcd(d, b)
		i = - 10
		while True:
			if 0 < gcd_bd * i + (a - c) % gcd_bd < b - c:
				print("No")
				return
			elif gcd_bd * i + (a - c) % gcd_bd >= b - c:
				print("Yes")
				return
			i += 1
				
	print("Yes")
	return
	
if __name__ == '__main__':
	main()

Buggy python submission (verdict: Runtime Error):
# encoding:utf-8
import math

def main():
	t = int(input())
	qs = [list(map(int, input().split())) for _ in range(t)]
	for q in qs:
		sub(q)

def sub(q):
	a, b, c, d = q
	if d - b < 0:
		print("No")
		return
	
	if a - b < 0:
		print("No")
		return

	if b > c:
		gcd_bd = math.gcd(d, b)
		i = - 10
		while True:
			#print(i)
			#print(gcd_bd, gcd_bd * i + (a - c))
			if 0 < gcd_bd * i + (a - c) % gcd_bd < b - c:
				print("No")
				return
			elif gcd_bd * i + (a - c) % gcd_bd >= b - c:
				print("Yes")
				return
			i += 1
				

	print("Yes")
	return
	
if __name__ == '__main__':
	main()


Fixed submission:
import fractions

def main():
	t = int(input())
	qs = [list(map(int, input().split())) for _ in range(t)]
	for q in qs:
		sub(q)

def sub(q):
	a, b, c, d = q
	if d - b < 0:
		print("No")
		return
	
	if a - b < 0:
		print("No")
		return

	if b > c:
		gcd_bd = fractions.gcd(d, b)
		i = - 10
		while True:
			if 0 < gcd_bd * i + (a - c) % gcd_bd < b - c:
				print("No")
				return
			elif gcd_bd * i + (a - c) % gcd_bd >= b - c:
				print("Yes")
				return
			i += 1
				
	print("Yes")
	return
	
if __name__ == '__main__':
	main()
Buggy python submission (verdict: Time Limit Exceeded):
# encoding:utf-8

import itertools
from collections import defaultdict


def main():
	n = int(input())
	s = input()

	left = s[:n]
	right = s[n:]
	right = right[::-1]

	ans = 0
	#print(left, right)
	for n_r in range(n+1):
		d_left = defaultdict(lambda: 0)
		d_right = defaultdict(lambda: 0)
		#print([1 if x >= n_r else 0 for x in range(n)])
		pts = itertools.combinations(list(range(n)), r = n_r)
		
		for pt in pts:
			#print(pt)
			b_l = "".join([left[i] for i in range(n) if i in pt])
			r_l = "".join([left[i] for i in range(n) if i not in pt])

			d_left[(b_l, r_l)] += 1

			b_r = "".join([right[i] for i in range(n) if i in pt])
			r_r = "".join([right[i] for i in range(n) if i not in pt])

			d_right[(b_r, r_r)] += 1

		for key in d_left:
#			print(n_r, key, d_left[key], d_right[key])
			ans += d_left[key] * d_right[key]

	print(ans)

if __name__ == '__main__':
	main()


Fixed submission:
# encoding:utf-8

import itertools
from collections import defaultdict


def main():
	n = int(input())
	s = input()

	left = s[:n]
	right = s[n:]
	right = right[::-1]

	ans = 0
	#print(left, right)
	for n_r in range(n+1):
		d_left = defaultdict(lambda: 0)
		d_right = defaultdict(lambda: 0)
		#print([1 if x >= n_r else 0 for x in range(n)])
		pts = itertools.combinations(list(range(n)), r = n_r)
		
		for pt in pts:
			#print(pt)
			b_l = ""
			r_l = ""
			b_r = ""
			r_r = ""
			for i in range(n):
				if i in pt:
					b_l += left[i]
					b_r += right[i]
				else:
					r_l += left[i]
					r_r += right[i]

			d_left[(b_l, r_l)] += 1
			d_right[(b_r, r_r)] += 1

		for key in d_left:
#			print(n_r, key, d_left[key], d_right[key])
			ans += d_left[key] * d_right[key]

	print(ans)

	

if __name__ == '__main__':
	main()
Buggy python submission (verdict: Time Limit Exceeded):
# encoding:utf-8

def main():
	s = input()
	k = int(input())
	substr = set()
	for start in range(len(s)):
		for end in range(start, len(s)):
			substr.add(s[start:(end+1)])

	substr = list(substr)
	substr.sort()
	#print(substr)
	print(substr[k-1])

if __name__ == '__main__':
	main()

Fixed submission:
# encoding:utf-8

def main():
	s = input()
	k = int(input())
	substr = set()
	for start in range(len(s)):
		for end in range(start, start+5):
			if end <= len(s):
				substr.add(s[start:(end+1)])

	substr = list(substr)
	substr.sort()
	#print(substr)
	print(substr[k-1])

if __name__ == '__main__':
	main()