Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10000)
n = int(input())
ls = list(map(int,input().split()))
di = []
ans = 0 
def culc(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        if n % 2 == 0:
            a = culc(n/2)*2
        else:
            a = culc(n/2)+culc((n/2)+1)
        return a
now = 0
for i in range(n):
    if ls[i] == i+1:
        now += 1
    else:
        if now != 0:
            di.append(now)
            now = 0
if now != 0:
    di.append(now)
for j in di:
    ans += culc(j)
print(ans)

Fixed submission:
n = int(input())
ls = list(map(int,input().split()))
di = []
ans = 0 
now = 0
for i in range(n):
    if ls[i] == i+1:
        now += 1
    else:
        if now != 0:
            di.append(now)
            now = 0
if now != 0:
    di.append(now)
for j in di:
    if j % 2 == 0:
        ans += j//2
    else:
        ans += (j//2) + 1
print(ans)

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10000)
n = int(input())
ls = list(map(int,input().split()))
di = []
ans = 0 
def culc(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        if n % 2 == 0:
            a = culc(n/2)*2
        else:
            a = culc(n/2)+culc((n/2)+1)
        return a
now = 0
for i in range(n):
    if ls[i] == i+1:
        now += 1
    else:
        if now != 0:
            di.append(now)
            now = 0
if now != 0:
    di.append(now)
for j in di:
    ans += culc(j)
print(ans)

Fixed submission:
n = int(input())
ls = list(map(int,input().split()))
di = []
ans = 0 
now = 0
for i in range(n):
    if ls[i] == i+1:
        now += 1
    else:
        if now != 0:
            di.append(now)
            now = 0
if now != 0:
    di.append(now)
for j in di:
    if j % 2 == 0:
        ans += j//2
    else:
        ans += (j//2) + 1
print(ans)
Buggy python submission (verdict: Runtime Error):
import collections
n = int(input())
ls = list(map(int,input().split()))
c =collections.Counter(ls)
d = list(c)
p = []
for i in range(len(d)):
    if c[d[i]] >1:
        p.append(d[i])
mx1 = max(p)
p.remove(mx1)
mx2 = max(p)
print(mx1 * mx2)
    

Fixed submission:
import collections
import sys
n = int(input())
ls = list(map(int,input().split()))
c =collections.Counter(ls)
d = list(c)
p = []
q = []
mm = 0
mx3 = 0
for i in range(len(d)):
    if c[d[i]] >=4:
        p.append(d[i])
    if c[d[i]] >=2:
        q.append(d[i])
if p == [] and len(q) < 2:
    print(0)
    sys.exit()
if len(q) >= 2:
    mx1 = max(q)
    q.remove(mx1)
    mx2 = max(q)
    mm = mx1 * mx2
if p != []:
    mx3 = max(p)**2
print(max(mm,mx3))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
n,m = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(m)]
di = []
for i in range(m):
    if ls[i][0] == 1:
        di.append(ls[i][1])
for j in range(m):
    if ls[j][0] in di and ls[j][1] == n:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

Fixed submission:
import sys
n,m = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(m)]
di = []
new = []
for i in range(m):
    if ls[i][0] == 1:
        di.append(ls[i][1])
    if ls[i][1] == n:
        new.append(ls[i][0])
f = list(set(di) & set(new))
if len(f) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
n = int(input())
ls = [int(input()) for _ in range(n)]
if 2 not in ls:
    print(-1)
    sys.exit()
i = 1
k = 0
di = []
for j in range(n):
    i = ls[i-1]
    if i in di:
        print(-1)
        break
    di.append(i)
    k += 1
    if i == 2:
        print(k)
        break

Fixed submission:
import sys
n = int(input())
ls = [int(input()) for _ in range(n)]
if 2 not in ls:
    print(-1)
    sys.exit()
i = 1
k = 0
for j in range(n):
    i = ls[i-1]
    k += 1
    if i == 2:
        print(k)
        sys.exit()
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
n = int(input())
ls = [int(input()) for _ in range(n)]
if 2 not in ls:
    print(-1)
    sys.exit()
i = 1
k = 0
di = []
for j in range(n):
    i = ls[i-1]
    if i in di:
        print(-1)
        sys.exit()
    di.append(i)
    k += 1
    if i == 2:
        break
print(k)

Fixed submission:
import sys
n = int(input())
ls = [int(input()) for _ in range(n)]
if 2 not in ls:
    print(-1)
    sys.exit()
i = 1
k = 0
for j in range(n):
    i = ls[i-1]
    k += 1
    if i == 2:
        print(k)
        sys.exit()
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
n = int(input())
ls = [int(input()) for _ in range(n)]
if 2 not in ls:
    print(-1)
    sys.exit()
i = 1
k = 0
di = []
while True:
    i = ls[i-1]
    if i in di:
        print(-1)
        sys.exit()
    di.append(i)
    k += 1
    if i == 2:
        break
print(k)

Fixed submission:
import sys
n = int(input())
ls = [int(input()) for _ in range(n)]
if 2 not in ls:
    print(-1)
    sys.exit()
i = 1
k = 0
for j in range(n):
    i = ls[i-1]
    k += 1
    if i == 2:
        print(k)
        sys.exit()
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
n = int(input())
ls = [int(input()) for _ in range(n)]
i = 1
k = 0
di = []
while True:
    i = ls[i-1]
    if i in di:
        print(-1)
        sys.exit()
    di.append(i)
    k += 1
    if i == 2:
        break
print(k)

Fixed submission:
import sys
n = int(input())
ls = [int(input()) for _ in range(n)]
if 2 not in ls:
    print(-1)
    sys.exit()
i = 1
k = 0
for j in range(n):
    i = ls[i-1]
    k += 1
    if i == 2:
        print(k)
        sys.exit()
print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ls = [e for e in range(n+1)]
if (int((2*n)**(1/2))+1)*(int((2*n)**(1/2)))/2 < n:
    print(int((2*n)**(1/2))+1)
else:
    print(int((2*n)**(1/2)))

Fixed submission:
n = int(input())
if (int((2*n)**(1/2))+1)*(int((2*n)**(1/2)))/2 < n:
    print(int((2*n)**(1/2))+1)
else:
    print(int((2*n)**(1/2)))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ls = [e for e in range(n+1)]
if sum(ls[:int((2*n)**(1/2))+1]) < n:
    print(int((2*n)**(1/2))+1)
else:
    print(int((2*n)**(1/2)))

Fixed submission:
n = int(input())
if (int((2*n)**(1/2))+1)*(int((2*n)**(1/2)))/2 < n:
    print(int((2*n)**(1/2))+1)
else:
    print(int((2*n)**(1/2)))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ls = {}
ls[1] = 1
ans = 0
for i in range(2,n+1):
    ls[i] = ls[i-1]+i
for j in range(1,n+1):
    if ls[j] >= n:   
        ans = j
        break
for k in range(1,ans+1):
    if ls[ans] - n != k:
        print(k)
    else:
        continue

Fixed submission:
n = int(input())
a = 1
ans = 0
if a >= n:
    ans = 1
else:
    for i in range(2,n+1):
        a += i
        if a >= n:
            ans = i
            break
for k in range(1,ans+1):
    if a - n != k:
        print(k)
    else:
        continue
Buggy python submission (verdict: Runtime Error):
import sys
sa = list(input())
sb = list(input())
sc = list(input())
sa = sa[::-1]
sb = sb[::-1]
sc = sc[::-1]
p = "a"
while True:
    if p == "a":
        p = sa.pop(-1)
        if len(sa) == 0 and p == "a":
            print("A")
            sys.exit()
    elif p == "b":
        p = sb.pop(-1)
        if len(sb) == 0 and p == "b":
            print("B")
            sys.exit()
    else:
        p = sc.pop(-1)
        if len(sc) == 0 and p == "c":
            print("C")
            sys.exit()
    

Fixed submission:
import sys
sa = list(input())
sb = list(input())
sc = list(input())
sa = sa[::-1]
sb = sb[::-1]
sc = sc[::-1]
p = "a"
while True:
    if p == "a":
        if len(sa) > 0:
            p = sa.pop(-1)
        if len(sa) == 0 and p == "a":
            print("A")
            sys.exit()
    elif p == "b":
        if len(sb) > 0:
            p = sb.pop(-1)
        if len(sb) == 0 and p == "b":
            print("B")
            sys.exit()
    else:
        if len(sc) > 0:
            p = sc.pop(-1)
        if len(sc) == 0 and p == "c":
            print("C")
            sys.exit()
Buggy python submission (verdict: Runtime Error):
cnt = 0
for _ in range(n):
  a, b = map(int, input().split())
  if a == b:
    cnt += 1
  else:
    cnt = 0
  
  if cnt == 3:
    print("Yes")
    exit()

print("No")

Fixed submission:
n = int(input())
cnt = 0
for _ in range(n):
  a, b = map(int, input().split())
  if a == b:
    cnt += 1
  else:
    cnt = 0
  
  if cnt == 3:
    print("Yes")
    exit()

print("No")
Buggy python submission (verdict: Time Limit Exceeded):
N = 1000
L = list(range(2,N+1))
p = list()
while L[0]**2<=N:
    tmp = L[0]
    p.append(tmp)
    L = [e for e in L if e%tmp!=0]
p = p + L

def function(n):
    memo = set()
    r = int((n+1)**0.5)
    for i in p:
        if n % i == 0:
            c = 0
            while n % i == 0:
                c += 1
                n //= i
            memo.add(i)
    if n > 1:
        memo.add(n)
    return memo

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


total = set()
cnt = 0
seki = set(p)
for a in A:
    s = function(a)
    total = total | s
    seki = seki & s
    cnt += len(s)
# print(total)

if seki == set():  # 全部に共通する素因数はない
    if len(total) != cnt:  # どこかに共通あり
        print("setwise coprime")
    else:
        print("pairwise coprime")
else:
    print("not coprime")

Fixed submission:
from math import gcd

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

m = 10**6
D = [-1]* (m+1)
for i in range(2, m+1):
    if D[i] == -1:
      for j in range(i, m+1, i):
          if D[j] == -1:
              D[j] = i


wa_set = set()
cnt = 0
for a in A:
    a_set = set()
    while a > 1:
        a_set.add(D[a])
        a //= D[a]
    wa_set |= a_set
    cnt += len(a_set)

if cnt == len(wa_set):
    print("pairwise coprime")
else:
    t = A[0]
    for a in A:
        t = gcd(a, t)
    if t == 1:
        print("setwise coprime")
    else:
        print("not coprime")
Buggy python submission (verdict: Runtime Error):
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int. input().split())
Ch, Cw, Dh, Dw = Ch-1, Cw-1, Dh-1, Dw-1

maze = [input() for _ in range(H)]
visit = [[-1] * W for _ in range(H)]
visit[Ch][Cw] = 0

DQ = deque([[Ch, Cw]])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

while DQ:
  px, py = DQ.popleft()
  if px==Dh and py==Dw:
    print(visit[px][py])
    exit()
  
  for i in range(4):
    nx = px + dx[i]
    ny = py + dy[i]
    if 0<=nx<=H-1 and 0<=ny<=C-1 and maze[nx][ny]=="." and  (visit[nx][ny]>visit[px][py] or visit[nx][ny]==-1):
      visit[nx][ny] = visit[px][py]
      DQ.append([nx, ny])
    
  for i in range(-2, 3):
    for j in range(-2, 3):
      if i==j==0:
        continue
      nx = px + i
      ny = py + j
      if 0<=nx<=H-1 and 0<=ny<=C-1 and maze[nx][ny]=="." and visit[nx][ny]==-1:
        visit[nx][ny] = visit[px][py] + 1
        DQ.append([nx, ny])

print(-1)

Fixed submission:
from collections import deque

h, w = map(int, input().split())
C = list(map(int, input().split()))
C = tuple([C[0]-1, C[1]-1])
D = tuple(map(int, input().split()))
D = tuple([D[0]-1, D[1]-1])
maze = [list(input()) for _ in range(h)]

visit = [[False]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            visit[i][j] = True

DQ = deque([C])
DQ_warp = deque([])

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

ans = 0

while DQ or DQ_warp:
    while DQ:
        now = DQ.popleft()
        if now == D:
            print(ans)
            exit()
        x, y = now[0], now[1]
        if visit[x][y]:
            continue
        visit[x][y] = True
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<=h-1 and 0<=ny<=w-1 and visit[nx][ny]==False:
                DQ.append(tuple([nx, ny]))

        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == j == 0: continue
                nx = x + i
                ny = y + j
                if 0<=nx<=h-1 and 0<=ny<=w-1 and visit[nx][ny]==False:
                    DQ_warp.append(tuple([nx, ny]))

    if DQ_warp:
        DQ = DQ_warp.copy()
        DQ_warp = deque([])
        ans += 1

print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
H, W, m = map(int, input().split())

H_bomb = [0]*H
W_bomb = [0]*W
S = set()

for _ in range(m):
    h, w = map(int, input().split())
    h, w = h-1, w-1
    S.add(tuple([h, w]))
    H_bomb[h] += 1
    W_bomb[w] += 1

H_max = max(H_bomb)
W_max = max(W_bomb)

H_memo = []
W_memo = []

for i in range(H):
    if H_bomb[i] == H_max:
        H_memo.append(i)

for j in range(W):
    if W_bomb[j] == W_max:
        W_memo.append(j)

ans = H_max + W_max

daburi = 1

for i in H_memo:
    for j in W_memo:
        if tuple([i, j]) not in S:
            daburi = 0
print(ans - daburi)

Fixed submission:
import sys

H, W, m = map(int, input().split())

H_bomb = [0]*H
W_bomb = [0]*W
S = set()

for _ in range(m):
    h, w = map(int, sys.stdin.readline().split())
    h, w = h-1, w-1
    S.add(tuple([h, w]))
    H_bomb[h] += 1
    W_bomb[w] += 1

H_max = max(H_bomb)
W_max = max(W_bomb)

H_memo = []
W_memo = []

for i in range(H):
    if H_bomb[i] == H_max:
        H_memo.append(i)

for j in range(W):
    if W_bomb[j] == W_max:
        W_memo.append(j)

ans = H_max + W_max

for i in H_memo:
    for j in W_memo:
        if tuple([i, j]) not in S:
            print(ans)
            exit()
print(ans-1)
Buggy python submission (verdict: Runtime Error):
import math

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

l = 0
r = 10**9+1

while l < r:
    mid = (l+r)//2
    count = 0
    for i in range(n):
        if A[i] > mid:
            count += math.ceil(A[i]//mid)

    if count <= k:
        r = mid
    else:
        l = mid+1



print(l)

Fixed submission:
import math

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

l = 1
r = 10**9+1

while l < r:
    mid = (l+r)//2
    count = 0
    for i in range(n):
        if A[i] > mid:
            count += math.ceil(A[i]//mid)

    if count <= k:
        r = mid
    else:
        l = mid+1


print(l)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import math

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

H = []

for i in range(n):
    heapq.heappush(H, (-A[i], 1))

for i in range(k):
    long, num = heapq.heappop(H)
    heapq.heappush(H, (long*num/(num+1), num+1) )

print(math.ceil(-H[0][0]))

Fixed submission:
import math

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

l = 1
r = 10**9+1

while l < r:
    mid = (l+r)//2
    count = 0
    for i in range(n):
        if A[i] > mid:
            count += math.ceil(A[i]//mid)

    if count <= k:
        r = mid
    else:
        l = mid+1


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

# まずK学期の評点を求めておきます
score = 1
for i in range(k):
  score *= A[i]

for i in range(n-k):
  new_score = score // A[i] * A[i+k]
  if score < new_score:
    print("Yes")
  else:
    print("No")
  score = new_score

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

for i in range(n-k):
    if A[i+k] > A[i]:
        print("Yes")
    else:
        print("No")

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

for i in range(n-k):
  pre = 1
  now = 1
  for j in range(k):
    pre *= A[i+j]
    now *= A[i+j+1]
  if pre < now:
    print("Yes")
  else:
    print("No")

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

for i in range(n-k):
    if A[i+k] > A[i]:
        print("Yes")
    else:
        print("No")
Buggy python submission (verdict: Runtime Error):
v

Fixed submission:
n = int(input())

i = 0
while i*1000<n:
    i += 1

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

dp = [0] * (max(A)+1)

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

ans = 0

for i in range(max(A)+1):
    if dp[i] == 1:
        ans += 1
    if dp[i] != 0:
        for j in range(2*i, max(A)+1, i):
            if dp[j] != 0:
                dp[j] += 1

print(ans)

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

LIST=[0]*(10**6+1)

for a in A:
    LIST[a]+=1
ANS=0

for i in range(10**6+1):
    if LIST[i]==1:
        ANS+=1
    if LIST[i]!=0:
        for j in range(2*i,10**6+1,i):
            if LIST[j]!=0:
                LIST[j]+=1
print(ANS)

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

a.sort()

ans = 0

for i in range(n):
    ai = a[i]

    if i != n-1:
        if ai == a[i+1]:
            continue

    if i != 0:
        if ai == a[i-1]:
            continue

    for j in range(i):
        aj = a[j]

        if aj*2 > ai:
            ans += 1
            break

        if ai % a[j] == 0:
            break
    else:
        ans += 1



print(ans)

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

LIST=[0]*(10**6+1)

for a in A:
    LIST[a]+=1
ANS=0

for i in range(10**6+1):
    if LIST[i]==1:
        ANS+=1
    if LIST[i]!=0:
        for j in range(2*i,10**6+1,i):
            if LIST[j]!=0:
                LIST[j]+=1
print(ANS)

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

a.sort()

ans = 0

for i in range(n):
    ai = a[i]

    if i != n-1:
        if ai == a[i+1]:
            continue

    for j in range(i):
        if ai % a[j] == 0:
            break
    else:
        ans += 1


print(ans)

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

LIST=[0]*(10**6+1)

for a in A:
    LIST[a]+=1
ANS=0

for i in range(10**6+1):
    if LIST[i]==1:
        ANS+=1
    if LIST[i]!=0:
        for j in range(2*i,10**6+1,i):
            if LIST[j]!=0:
                LIST[j]+=1
print(ANS)

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

ans = 0

for i in range(n):
    ai = a[i]
    for j in range(n):
        if i == j:
            continue

        if ai % a[j] == 0:
            break

    else:
        ans += 1

print(ans)

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

LIST=[0]*(10**6+1)

for a in A:
    LIST[a]+=1
ANS=0

for i in range(10**6+1):
    if LIST[i]==1:
        ANS+=1
    if LIST[i]!=0:
        for j in range(2*i,10**6+1,i):
            if LIST[j]!=0:
                LIST[j]+=1
print(ANS)
Buggy python submission (verdict: Time Limit Exceeded):
n =int(input())
a = list(map(int, input().split()))

ans = 1
for i in a:
    ans *= i

if ans > 10**18:
    print(-1)

else:
    print(ans)

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

ans = 1

if min(a)==0:
    print(0)
    exit()

for i in a:
    ans *= i
    if ans > 10**18:
        print(-1)
        exit()

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from math import sqrt

n = int(input())

if n == 1:
    print(0)

n_sqrt = int(sqrt(n))

dp = [-1] * (n_sqrt+2)

for i in range(2, n_sqrt+2):
    if dp[i] == -1:
        dp[i] = 1
        for j in range(i*2, n_sqrt+2, i):
            dp[j] = 0

prime = []

for i in range(2, n_sqrt+2):
    if dp[i] == 1:
        prime.append(i)

prime.append(n)

memo = []
for p in prime:
    cnt = 0
    while n%p==0:
        n //= p
        cnt += 1

    if cnt:
        memo.append(cnt)

if n > 1:
    memo.append(1)

ans = 0

for j in memo:
    k = 1
    while True:

        if k*(k+1)//2 <= j <= k*(k+3)//2:
            ans += k
            break
        k += 1

print(ans)

Fixed submission:
from math import sqrt

n = int(input())

if n == 1:
    print(0)
    exit()

n_sqrt = int(sqrt(n))

dp = [-1] * (n_sqrt+2)

for i in range(2, n_sqrt+2):
    if dp[i] == -1:
        dp[i] = 1
        for j in range(i*2, n_sqrt+2, i):
            dp[j] = 0

prime = []

for i in range(2, n_sqrt+2):
    if dp[i] == 1:
        prime.append(i)

prime.append(n)

memo = []
for p in prime:
    cnt = 0
    while n%p==0:
        n //= p
        cnt += 1

    if cnt:
        memo.append(cnt)

if n > 1:
    memo.append(1)

ans = 0

for j in memo:
    k = 1
    while True:

        if k*(k+1)//2 <= j <= k*(k+3)//2:
            ans += k
            break
        k += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
A = list(map(int, input().split()))
A = [x-1 for x in A]

town = 0
cnt = 0

memo = []
visited = [False] * n
visited[0] = -1

start = 0
for i in range(min(n, k)):
    town = A[town]
    memo.append(town)
    if visited[town] != False:
        start_cnt = i + 1
        loop = i - visited[town]
        break
    else:
        visited[town] = i

for i in range((k-start_cnt)%loop):
    town = A[town]

print(town+1)

Fixed submission:
n, k = map(int, input().split())
A = list(map(int, input().split()))
A = [x-1 for x in A]

town = 0
cnt = 0

# memo = []
# visited = [False] * n
# visited[0] = -1

# start = 0
# loop = 10**8
# start_cnt = 0
# for i in range(n*2):
#     town = A[town]
#     memo.append(town)
#     if visited[town] != False:
#         start_cnt = i + 1
#         loop = i - visited[town]
#         break
#     else:
#         visited[town] = i
#
# for i in range((k-start_cnt)%loop):
#     town = A[town]
#
# print(town+1)

visited = [False] * n
visited[0] = 0

for i in range(n):
    town = A[town]
    if visited[town]:
        good_town = town
        break
    visited[town] = i+1

town = good_town

for i in range(n):
    town = A[town]
    if town == good_town:
        loop = i + 1

if k >= visited[good_town]:
    k = ((k-visited[good_town])%loop)+visited[good_town]


town = 0
for i in range(k):
    town = A[town]
print(town+1)
Buggy python submission (verdict: Runtime Error):
n, m, k = map(int, input().split())
mod = 998244353

N = 10**5  # N!まで求める
fact  = [1, 1]  # 階乗の元テーブル
fact_inv = [1, 1]  # 階乗の逆元テーブル
inv = [0, 1]  # 逆元テーブル計算用テーブル 1,2,,...の逆元を求めてる

# 計算 O(1)
def comb(n, r, mod):
    if (r<0 or r>n):
        return 0
    r = min(r, n-r)
    return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

# 順列
def perm(n, r, mod):
    if (r<0 or r>n):
        return 0
    return fact[n] *  fact_inv[n-r] % mod

# 前処理 O(n)
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod//i)) % mod)
    fact_inv.append((fact_inv[-1] * inv[-1]) % mod)

ans = 0
for i in range(k+1):
    ans += comb(n-1, i, mod) * m * pow(m-1, n-i-1, mod)
    ans %= mod

print(ans)

Fixed submission:
n, m, k = map(int, input().split())
mod = 998244353

N = 10**6  # N!まで求める
fact  = [1, 1]  # 階乗の元テーブル
fact_inv = [1, 1]  # 階乗の逆元テーブル
inv = [0, 1]  # 逆元テーブル計算用テーブル 1,2,,...の逆元を求めてる

# 計算 O(1)
def comb(n, r, mod):
    if (r<0 or r>n):
        return 0
    r = min(r, n-r)
    return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

# 順列
def perm(n, r, mod):
    if (r<0 or r>n):
        return 0
    return fact[n] *  fact_inv[n-r] % mod

# 前処理 O(n)
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod//i)) % mod)
    fact_inv.append((fact_inv[-1] * inv[-1]) % mod)

ans = 0
for i in range(k+1):
    ans += comb(n-1, i, mod) * m * pow(m-1, n-i-1, mod)
    ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
A = [x[1] for x in AB]

DP = [float("inf") for _ in range(h+1)]
DP[0] = 0

for i in range(h):
    for damage, cost in AB:
        next_index = min(i+damage, h)
        DP[next_index] = min(DP[next_index], DP[i]+cost)

print(DP[-1])

Fixed submission:
h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
A = [x[1] for x in AB]

DP = [float("inf") for _ in range(h+1)]
DP[0] = 0

for i in range(h):
    for damage, cost in AB:
        next_index = min(i+damage, h)
        DP[next_index] = min(DP[next_index], DP[i]+cost)

print(DP[-1])