Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = []
for i in range(M):
  A.append(int(input()))

X = [0] * (N + 1)
for i in range(N + 1):
  if i == 0:
    X[i] = 1
  elif i == 1:
    if 1 not in A:
      X[i] = 1
    else:
      X[i] = 0
  else:
    if i in A:
      X[i] = 0
    else:
      X[i] = (X[i - 1] + X[i - 2]) % 1000000007

print(X[N])


Fixed submission:
N, M = map(int, input().split())
A = []
for i in range(M):
  A.append(int(input()))

X = [0] * (N + 1)
for i in A:
  X[i] = -1

for i in range(N + 1):
  if i == 0:
    X[i] = 1
  elif i == 1:
    if X[i] == -1:
      X[i] = 0
    else:
      X[i] = 1
  else:
    if X[i] == -1:
      X[i] = 0
    else:
      X[i] = (X[i - 1] + X[i - 2]) % 1000000007

print(X[N])
Buggy python submission (verdict: Runtime Error):
import heapq

N = int(input())
E = [list(map(lambda x: int(x)-1,input().split())) for _ in range(N-1)]
C = sorted(list(map(lambda x: int(x)*(-1),input().split())))
m = -sum(C[1:])
heapq.heapify(C)

V = [set() for _ in range(N)]
for u,v in E:
  V[u].add(v)
  V[v].add(u)

A = [0 for _ in range(N)]
def dfs(v,s):
  A[v] = -heapq.heappop(C)
  for u in V[v]:
    if u != s:
      dfs(u,v)
dfs(0,-1)

print(m)
print(*A)


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 9)
import heapq

N = int(input())
E = [list(map(lambda x: int(x)-1,input().split())) for _ in range(N-1)]
C = sorted(list(map(lambda x: int(x)*(-1),input().split())))
m = -sum(C[1:])
heapq.heapify(C)

V = [set() for _ in range(N)]
for u,v in E:
  V[u].add(v)
  V[v].add(u)

A = [0 for _ in range(N)]
def dfs(v,s):
  A[v] = -heapq.heappop(C)
  for u in V[v]:
    if u != s:
      dfs(u,v)
dfs(0,-1)

print(m)
print(*A)

Buggy python submission (verdict: Runtime Error):
import heapq

N = int(input())
E = [list(map(lambda x: int(x)-1,input().split())) for _ in range(N-1)]
C = list(map(lambda x: int(x)*(-1),input().split()))
heapq.heapify(C)

V = [set() for _ in range(N)]
for u,v in E:
  V[u].add(v)
  V[v].add(u)

A = [0 for _ in range(N)]
def dfs(v,s):
  A[v] = -heapq.heappop(C)
  for u in V[v]:
    if u != s:
      dfs(u,v)
dfs(0,-1)
print(*A)


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 9)
import heapq

N = int(input())
E = [list(map(lambda x: int(x)-1,input().split())) for _ in range(N-1)]
C = sorted(list(map(lambda x: int(x)*(-1),input().split())))
m = -sum(C[1:])
heapq.heapify(C)

V = [set() for _ in range(N)]
for u,v in E:
  V[u].add(v)
  V[v].add(u)

A = [0 for _ in range(N)]
def dfs(v,s):
  A[v] = -heapq.heappop(C)
  for u in V[v]:
    if u != s:
      dfs(u,v)
dfs(0,-1)

print(m)
print(*A)
Buggy python submission (verdict: Runtime Error):
import bisect

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
BC = []
for i in range(M):
  B,C = map(int,input().split())
  BC.append([B,C])
BC.sort(key = lambda val: val[1], reverse = True)
#print(A)
#print(BC)

ans = 0
j = 0
count = BC[j][0]
for i in range(N):
  #print(ans)
  if A[i] < BC[j][1]:
    ans += BC[j][1]
    count -= 1
    if count == 0:
      j += 1
      count = BC[j][0]
      if j >= M:
        break
  else:
    break
if i < N:
  ans += sum(A[i:])
print(ans)


Fixed submission:
import bisect

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
BC = []
for i in range(M):
  B,C = map(int,input().split())
  BC.append([B,C])
BC.sort(key = lambda val: val[1], reverse = True)
#print(A)
#print(BC)

ans = 0
j = 0
count = BC[j][0]
for i in range(N):
  #print(ans)
  if A[i] < BC[j][1]:
    ans += BC[j][1]
    count -= 1
    if count == 0:
      j += 1
      if j >= M:
        if i < N-1:
          ans += sum(A[i+1:])
        break
      count = BC[j][0]
  else:
    ans += sum(A[i:])
    break
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  u,v,w = map(int,input().split())
  u -= 1
  v -= 1
  edge[u].append((v,w))
  edge[v].append((u,w))

#print(edge)

def dfs(u,v):
  for e,w in edge[u]:
    if e != v:
      ans[e] = (w + ans[u]) % 2
      # print(ans)
      dfs(e,u)

ans = [0] + [-1] * (N-1)
dfs(0,-1)
print(*ans)


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

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  u,v,w = map(int,input().split())
  u -= 1
  v -= 1
  edge[u].append((v,w))
  edge[v].append((u,w))

#print(edge)

def dfs(u,v):
  for e,w in edge[u]:
    if e != v:
      ans[e] = (w + ans[u]) % 2
      # print(ans)
      dfs(e,u)

ans = [0] + [-1] * (N-1)
dfs(0,-1)
print(*ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
edge = [[] for _ in range(N)]
length = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N-1):
  u,v,w = map(int,input().split())
  edge[u-1].append(v-1)
  edge[v-1].append(u-1)
  length[u-1][v-1] = w
  length[v-1][u-1] = w

#print(edge)
#print(length)

def bfs(u,v):
  for e in edge[u]:
    if e != v:
      ans[e] = (length[e][u] + ans[u]) % 2
      bfs(e,u)

ans = [0] * N
bfs(0,-1)
print(*ans)


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

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  u,v,w = map(int,input().split())
  u -= 1
  v -= 1
  edge[u].append((v,w))
  edge[v].append((u,w))

#print(edge)

def dfs(u,v):
  for e,w in edge[u]:
    if e != v:
      ans[e] = (w + ans[u]) % 2
      # print(ans)
      dfs(e,u)

ans = [0] + [-1] * (N-1)
dfs(0,-1)
print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
  X,Y,Z = map(int, input().split())
  X -= 1
  Y -= 1
  G[X].append(Y)
  G[Y].append(X)
#print(G)

def dfs(u,v):
  for t in G[u]:
    #if t != v:
    if not Visited[t]:
      Visited[t] = True
      dfs(t,u)

Visited = [False for _ in range(N)]
ans = 0
for i in range(N):
  if not Visited[i]:
    Visited[i] = True
    ans += 1
    dfs(i,-1)
print(ans)


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

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
  X,Y,Z = map(int, input().split())
  X -= 1
  Y -= 1
  G[X].append(Y)
  G[Y].append(X)
#print(G)

def dfs(u,v):
  for t in G[u]:
    #if t != v:
    if not Visited[t]:
      Visited[t] = True
      dfs(t,u)

Visited = [False for _ in range(N)]
ans = 0
for i in range(N):
  if not Visited[i]:
    Visited[i] = True
    ans += 1
    dfs(i,-1)
print(ans)

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

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
  X,Y,Z = map(int, input().split())
  X -= 1
  Y -= 1
  G[X].append(Y)
  G[Y].append(X)
#print(G)

def dfs(u,v):
  for t in G[u]:
    #if t != v:
    if not Visited[t]:
      Visited[t] = True
      dfs(t,u)

Visited = [False for _ in range(N)]
ans = 0
for i in range(N):
  if not Visited[i]:
    Visited[i] = True
    ans += 1
    dfs(i,-1)
print(ans)


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

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
  X,Y,Z = map(int, input().split())
  X -= 1
  Y -= 1
  G[X].append(Y)
  G[Y].append(X)
#print(G)

def dfs(u,v):
  for t in G[u]:
    #if t != v:
    if not Visited[t]:
      Visited[t] = True
      dfs(t,u)

Visited = [False for _ in range(N)]
ans = 0
for i in range(N):
  if not Visited[i]:
    Visited[i] = True
    ans += 1
    dfs(i,-1)
print(ans)

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

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
  X,Y,Z = map(int, input().split())
  X -= 1
  Y -= 1
  G[X].append(Y)
  G[Y].append(X)
#print(G)

def dfs(u,v):
  for t in G[u]:
    #if t != v:
    if not Visited[t]:
      Visited[t] = True
      dfs(t,u)

Visited = [False for _ in range(N)]
ans = 0
for i in range(N):
  if not Visited[i]:
    Visited[i] = True
    ans += 1
    dfs(i,-1)
print(ans)


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

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
  X,Y,Z = map(int, input().split())
  X -= 1
  Y -= 1
  G[X].append(Y)
  G[Y].append(X)
#print(G)

def dfs(u,v):
  for t in G[u]:
    #if t != v:
    if not Visited[t]:
      Visited[t] = True
      dfs(t,u)

Visited = [False for _ in range(N)]
ans = 0
for i in range(N):
  if not Visited[i]:
    Visited[i] = True
    ans += 1
    dfs(i,-1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

divs = []
for i in range(1,N):
  if N % i == 0:
    if i < N//i -1:
      divs.append(N//i-1)
    else:
      break
print(sum(divs))


Fixed submission:
N = int(input())

divs = []
for i in range(1,int(N**0.5)+2):
  if N % i == 0:
    if i < N//i -1:
      divs.append(N//i-1)
    else:
      break
print(sum(divs))
Buggy python submission (verdict: Time Limit Exceeded):
import fractions
from functools import reduce

def gcd_list(numbers):
  return reduce(fractions.gcd, numbers)

N = int(input())
A = [int(i) for i in input().split()]
ans = 0
for i in range(N):
  B = A[:]
  B.remove(B[i])
  ans = max(ans, gcd_list(B))
print(ans)


Fixed submission:
from fractions import gcd

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

L = [0 for _ in range(N)]
R = [0 for _ in range(N)]
L[0] = A[0]
R[-1] = A[-1]
for i in range(N-1):
  L[i+1] = gcd(L[i],A[i+1])
  R[N-2-i] = gcd(R[N-1-i],A[N-2-i])
#print(L)
#print(R)

ans = 0
for i in range(N):
  if i == 0:
    ans = max(ans,R[1])
  elif i == N-1:
    ans = max(ans,L[N-2])
  else:
    ans = max(ans,gcd(L[i-1],R[i+1]))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import fractions
from functools import reduce

def gcd_list(numbers):
  return reduce(fractions.gcd, numbers)

N = int(input())
A = [int(i) for i in input().split()]
ans = 0
for i in range(N):
  B = A[:]
  B.remove(B[i])
  ans = max(ans, gcd_list(B))
print(ans)


Fixed submission:
from fractions import gcd

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

L = [0 for _ in range(N)]
R = [0 for _ in range(N)]
L[0] = A[0]
R[-1] = A[-1]
for i in range(N-1):
  L[i+1] = gcd(L[i],A[i+1])
  R[N-2-i] = gcd(R[N-1-i],A[N-2-i])
#print(L)
#print(R)

ans = 0
for i in range(N):
  if i == 0:
    ans = max(ans,R[1])
  elif i == N-1:
    ans = max(ans,L[N-2])
  else:
    ans = max(ans,gcd(L[i-1],R[i+1]))
print(ans)
Buggy python submission (verdict: Runtime Error):
A, B, C = map(int, input().split())
if (A < C and C < B) or (B < C and C < A):
  print('Yes')
else:
  prnt('No')

Fixed submission:
A, B, C = map(int, input().split())
if (A < C and C < B) or (B < C and C < A):
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()
K = int(input())

target = S[K - 1]
for i in range(N):
  if S[i] != target:
    S[i] = '*'
print(S)

Fixed submission:
N = int(input())
S = input()
K = int(input())

target = S[K - 1]
ans = ''
for i in range(N):
  if S[i] != target:
    ans += '*'
  else:
    ans += S[i]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
S = input()

if S.count('1') == N or S.count('0') == N:
  print(N)
  exit()

S += '2'
s = S[0]
L0 = []
if s == '0':
  L1 = [0]
else:
  L1 = []
c = 1
for i in range(1,N+1):
  if S[i] != s:
    if s == '0':
      L0.append(c)
    else:
      L1.append(c)
    s = S[i]
    c = 1
  else:
    c += 1
L1 += [0]
#print(L0)
#print(L1)

if len(L0) <= K:
  print(N)
  exit()

ans = 0
for i in range(len(L0)-K+1):
    ans = max(ans,sum(L0[i:i+K])+sum(L1[i:i+K+1]))
print(ans)


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

if S.count('1') == N or S.count('0') == N:
  print(N)
  exit()

S += '2'
s = S[0]
L0 = []
if s == '0':
  L1 = [0]
else:
  L1 = []
c = 1
for i in range(1,N+1):
  if S[i] != s:
    if s == '0':
      L0.append(c)
    else:
      L1.append(c)
    s = S[i]
    c = 1
  else:
    c += 1
L1 += [0]
#print(L0)
#print(L1)

if len(L0) <= K:
  print(N)
  exit()

SL0 = [0 for _ in range(len(L0)+1)]
for i in range(1,len(L0)+1):
  SL0[i] = SL0[i-1] + L0[i-1]
SL1 = [0 for _ in range(len(L1)+1)]
for i in range(1,len(L1)+1):
  SL1[i] = SL1[i-1] + L1[i-1]

ans = 0
for i in range(len(L0)-K+1):
    #ans = max(ans,sum(L0[i:i+K])+sum(L1[i:i+K+1]))
    ans = max(ans,SL0[i+K]-SL0[i] + SL1[i+K+1]-SL1[i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
X,Y,Z,K = map(int, input().split())
A = sorted(list(map(int, input().split())),reverse=True)
B = sorted(list(map(int, input().split())),reverse=True)
C = sorted(list(map(int, input().split())),reverse=True)

D = [[0,0,0]]
used = []
ans = []
for k in range(K):
  #print(k,D)
  mxd = 0
  mxi = 0
  for i in range(len(D)):
    d = A[D[i][0]]+B[D[i][1]]+C[D[i][2]]
    if d >= mxd:
      mxd = d
      mxi = i
  ans.append(mxd)
  if D[mxi][0]+1 < X and [D[mxi][0]+1,D[mxi][1],D[mxi][2]] not in D and [D[mxi][0]+1,D[mxi][1],D[mxi][2]] not in used:
    D.append([D[mxi][0]+1,D[mxi][1],D[mxi][2]])
  if D[mxi][1]+1 < Y and [D[mxi][0],D[mxi][1]+1,D[mxi][2]] not in D and [D[mxi][0],D[mxi][1]+1,D[mxi][2]] not in used:
    D.append([D[mxi][0],D[mxi][1]+1,D[mxi][2]])
  if D[mxi][2]+1 < Z and [D[mxi][0],D[mxi][1],D[mxi][2]+1] not in D and [D[mxi][0],D[mxi][1],D[mxi][2]+1] not in used:
    D.append([D[mxi][0],D[mxi][1],D[mxi][2]+1])
  used.append(D[mxi])
  del D[mxi]
#print(D)
for a in ans:
  print(a)


Fixed submission:
X,Y,Z,K = map(int, input().split())
A = sorted(list(map(int, input().split())),reverse=True)
B = sorted(list(map(int, input().split())),reverse=True)
C = sorted(list(map(int, input().split())),reverse=True)

D = {(0,0,0)}
used = set()
ans = []
for k in range(K):
  #print(k,D)
  mxdsum = 0
  for d in D:
    dsum = A[d[0]]+B[d[1]]+C[d[2]]
    if dsum >= mxdsum:
      mxdsum = dsum
      mxd = d
  ans.append(mxdsum)
  if mxd[0]+1 < X and (mxd[0]+1,mxd[1],mxd[2]) not in used:
    D.add((mxd[0]+1,mxd[1],mxd[2]))
  if mxd[1]+1 < Y and (mxd[0],mxd[1]+1,mxd[2]) not in used:
    D.add((mxd[0],mxd[1]+1,mxd[2]))
  if mxd[2]+1 < Y and (mxd[0],mxd[1],mxd[2]+1) not in used:
    D.add((mxd[0],mxd[1],mxd[2]+1))
  used.add(mxd)
  D.remove(mxd)
#print(D)
for a in ans:
  print(a)
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()

C = []
for i in range(0, N, 100):
  if N >= i + 101:
    C.append(S[i: i + 101].count('AC'))

for i in range(Q):
  l, r = map(int, input().split())
  if (r - 1) // 100 - (l - 1) // 100 < 2:
    ans = S[l - 1: r].count('AC')
  else:
    ans  = S[l - 1: ((l - 1) // 100) * 100 + 101].count('AC')
    for j in range((l - 1) // 100 + 1, (r - 1) // 100):
      ans += C[j]
    ans += S[((r - 1) // 100) * 100 - 1: r].count('AC')
  print(ans)


Fixed submission:
N,Q = map(int,input().split())
S = input()
LR = [list(map(int,input().split())) for _ in range(Q)]
#print(LR)

C = [0 for _ in range(N+1)]
for i in range(1,N):
  if S[i-1] == 'A' and S[i] == 'C':
    C[i+1] = C[i] + 1
  else:
    C[i+1] = C[i]
#print(C)
for l,r in LR:
  print(C[r]-C[l])

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
for i in range(Q):
  l, r = map(int, input().split())
  # print(S[l - 1: r].count('AC'))
  T = S[l - 1: r]
  R = T.replace('AC', '')
  print((len(T) - len(R)) // 2)

Fixed submission:
N,Q = map(int,input().split())
S = input()
LR = [list(map(int,input().split())) for _ in range(Q)]
#print(LR)

C = [0 for _ in range(N+1)]
for i in range(1,N):
  if S[i-1] == 'A' and S[i] == 'C':
    C[i+1] = C[i] + 1
  else:
    C[i+1] = C[i]
#print(C)
for l,r in LR:
  print(C[r]-C[l])

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
for i in range(Q):
  l, r = map(int, input().split())
  print(S[l - 1: r].count('AC'))

Fixed submission:
N,Q = map(int,input().split())
S = input()
LR = [list(map(int,input().split())) for _ in range(Q)]
#print(LR)

C = [0 for _ in range(N+1)]
for i in range(1,N):
  if S[i-1] == 'A' and S[i] == 'C':
    C[i+1] = C[i] + 1
  else:
    C[i+1] = C[i]
#print(C)
for l,r in LR:
  print(C[r]-C[l])
Buggy python submission (verdict: Runtime Error):
import datetime
S = input()
if datetime.datetime.strptime(S, "%Y/%m/%d") <= datetime.datetime(2019, 4, 30, 0 ,0 ,0):
  print('Heisei')
else:
  print('TBD'

Fixed submission:
import datetime
S = input()
if datetime.datetime.strptime(S, "%Y/%m/%d") <= datetime.datetime(2019, 4, 30, 0 ,0 ,0):
  print('Heisei')
else:
  print('TBD')
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
a = list(map(int,input().split()))

d1 = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
d2 = {2:[1],3:[7],4:[4],5:[5,3,2],6:[9,6],7:[8]}

# dp[i]:i本のマッチを使用した場合の最大桁数
dp = [-float('inf') for _ in range(n+1)]
dp[0] = 0
for i in range(1,n+1):
  for ai in a:
    if i-d1[ai] >= 0:
      dp[i] = max(dp[i-d1[ai]]+1,dp[i])

a.sort(reverse = True)
ans = ''
r = n
k = dp[n]
while(r > 0):
  for ai in a:
    if dp[r-d1[ai]] == k-1:
      ans += str(ai)
      r -= d1[ai]
      k -= 1
      break

print(ans)


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

d1 = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
d2 = {2:[1],3:[7],4:[4],5:[5,3,2],6:[9,6],7:[8]}

# dp[i]:i本のマッチを使用した場合の最大桁数
dp = [-float('inf') for _ in range(n+1)]
dp[0] = 0
for i in range(1,n+1):
  for ai in a:
    if i-d1[ai] >= 0:
      dp[i] = max(dp[i-d1[ai]]+1,dp[i])

a.sort(reverse = True)
ans = ''
r = n
k = dp[n]
while(r > 0):
  for ai in a:
    if r-d1[ai] >= 0 and dp[r-d1[ai]] == k-1:
      ans += str(ai)
      r -= d1[ai]
      k -= 1
      break

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
t = input()

ans = ''
#dp[i][j]:sをi文字目、tをj文字目まで見たときの最長部分列
dp = [['' for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j] + s[i]
    else:
      if len(dp[i+1][j])>len(dp[i][j+1]):
        dp[i+1][j+1] = dp[i+1][j]
      else:
        dp[i+1][j+1] = dp[i][j+1]
    #print(dp)
print(dp[len(s)][len(t)])


Fixed submission:
s = input()
t = input()

ans = ''
#dp[i][j]:sをi文字目、tをj文字目まで見たときの最長部分列長
dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j] + 1
    else:
      if dp[i+1][j] > dp[i][j+1]:
        dp[i+1][j+1] = dp[i+1][j]
      else:
        dp[i+1][j+1] = dp[i][j+1]
    #print(dp)
#print(dp)
#print(dp[len(s)][len(t)])

# dpを逆にたどって最長部分文字列を復元する
ans = ''
i = len(s)
j = len(t)
while(dp[i][j]>0):
  if dp[i][j] == dp[i-1][j-1] +1 and dp[i][j] == dp[i-1][j] +1 and dp[i][j] == dp[i][j-1] +1:
    ans += s[i-1]
    i -= 1
    j -= 1
  elif dp[i-1][j] > dp[i][j-1]:
    i -= 1
  else:
    j -= 1
print(''.join(reversed(list(ans))))

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
t = input()

ans = ''
#dp[i][j]:sをi文字目、tをj文字目まで見たときの最長部分列
dp = [['' for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j] + s[i]
    else:
      if len(dp[i+1][j])>len(dp[i][j+1]):
        dp[i+1][j+1] = dp[i+1][j]
      else:
        dp[i+1][j+1] = dp[i][j+1]
    #print(dp)
print(dp[len(s)][len(t)])


Fixed submission:
s = input()
t = input()

ans = ''
#dp[i][j]:sをi文字目、tをj文字目まで見たときの最長部分列長
dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j] + 1
    else:
      if dp[i+1][j] > dp[i][j+1]:
        dp[i+1][j+1] = dp[i+1][j]
      else:
        dp[i+1][j+1] = dp[i][j+1]
    #print(dp)
#print(dp)
#print(dp[len(s)][len(t)])

# dpを逆にたどって最長部分文字列を復元する
ans = ''
i = len(s)
j = len(t)
while(dp[i][j]>0):
  if dp[i][j] == dp[i-1][j-1] +1 and dp[i][j] == dp[i-1][j] +1 and dp[i][j] == dp[i][j-1] +1:
    ans += s[i-1]
    i -= 1
    j -= 1
  elif dp[i-1][j] > dp[i][j-1]:
    i -= 1
  else:
    j -= 1
print(''.join(reversed(list(ans))))
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
E = [[] for _ in range(N)]
for i in range(M):
  x,y = map(int,input().split())
  x -= 1
  y -= 1
  E[x].append(y)
#print(E)

# dp[i]:頂点iを始点とする最長パスの長さ
dp = [-1 for _ in range(N)]

def rec(v):
  if dp[v] != -1:
    return dp[v]
  res = 0
  for u in E[v]:
    res = max(res, rec(u)+1)
  dp[v] = res
  return dp[v]

for i in range(N):
  rec(i)
print(max(dp))


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

N,M = map(int,input().split())
E = [[] for _ in range(N)]
for i in range(M):
  x,y = map(int,input().split())
  x -= 1
  y -= 1
  E[x].append(y)
#print(E)

# dp[i]:頂点iを始点とする最長パスの長さ
dp = [-1 for _ in range(N)]

def rec(v):
  if dp[v] != -1:
    return dp[v]
  res = 0
  for u in E[v]:
    res = max(res, rec(u)+1)
  dp[v] = res
  return dp[v]

for i in range(N):
  rec(i)
print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input()) 
A = list(map(int,input().split()))

CSUM = [0 for _ in range(N)]
CSUM[0] = A[0]
for i in range(1,N):
  CSUM[i] = CSUM[i-1] + A[i]
#print(CSUM)
def csum(i,j):
  if i == 0:
    return CSUM[j]
  else:
    return CSUM[j]-CSUM[i-1]

dp = [[0 for _ in range(N)] for _ in range(N)]

for k in range(1,N):
  for i in range(N-k):
    j = i+k
    tmp = 10**10
    for l in range(i,j):
      tmp = min(tmp,dp[i][l]+dp[l+1][j])
    dp[i][j] = tmp + csum(i,j)

print(dp[0][N-1])
#print(dp)


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

CSUM = [0 for _ in range(N)]
CSUM[0] = A[0]
for i in range(1,N):
  CSUM[i] = CSUM[i-1] + A[i]
#print(CSUM)
def csum(i,j):
  if i == 0:
    return CSUM[j]
  else:
    return CSUM[j]-CSUM[i-1]

dp = [[0 for _ in range(N)] for _ in range(N)]

for k in range(1,N):
  for i in range(N-k):
    j = i+k
    tmp = 10**18
    for l in range(i,j):
      tmp = min(tmp,dp[i][l]+dp[l+1][j] + csum(i,j))
    dp[i][j] = tmp

print(dp[0][N-1])
#print(dp)

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 9)

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

CSUM = [0 for _ in range(N)]
CSUM[0] = A[0]
for i in range(1,N):
  CSUM[i] = CSUM[i-1] + A[i]
#print(CSUM)
def csum(i,j):
  if i == 0:
    return CSUM[j]
  else:
    return CSUM[j]-CSUM[i-1]

dp = [[0 for _ in range(N)] for _ in range(N)]

for k in range(1,N):
  for i in range(N-k):
    j = i+k
    tmp = 10**10
    for l in range(i,j):
      tmp = min(tmp,dp[i][l]+dp[l+1][j])
    dp[i][j] = tmp + sum(S[i:j+1])

print(dp[0][N-1])
#print(dp)


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

CSUM = [0 for _ in range(N)]
CSUM[0] = A[0]
for i in range(1,N):
  CSUM[i] = CSUM[i-1] + A[i]
#print(CSUM)
def csum(i,j):
  if i == 0:
    return CSUM[j]
  else:
    return CSUM[j]-CSUM[i-1]

dp = [[0 for _ in range(N)] for _ in range(N)]

for k in range(1,N):
  for i in range(N-k):
    j = i+k
    tmp = 10**18
    for l in range(i,j):
      tmp = min(tmp,dp[i][l]+dp[l+1][j] + csum(i,j))
    dp[i][j] = tmp

print(dp[0][N-1])
#print(dp)