Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import numpy as np
import math
A, B, C, D = list(map(int, input().split()))

def lcm(x, y):
    return (x * y) / math.gcd(x, y)
E = lcm(C, D)

u = np.arange(A,B+1)
count_U = len(u)
u_c = [i for i in u if i % C == 0]
count_C = len(u_c)
u_d = [i for i in u if i % D == 0]
count_D = len(u_d)
u_e = [i for i in u if i % E == 0]
count_E = len(u_e)

answer = count_U - (count_C + count_D -count_E)
print(answer)


Fixed submission:
from fractions import gcd
 
a, b, c, d = map(int, input().split())
a = a - 1
 
def main():
    cd = c * d // gcd(c, d)
    print(b - a - f(c) - f(d) + f(cd))
 
def f(x):
    return b // x - a // x
 
main()

Buggy python submission (verdict: Runtime Error):
import numpy as np
import math
A, B, C, D = list(map(int, input().split()))

def lcm(x, y):
    return (x * y) // math.gcd(x, y)
E = lcm(C, D)

u = np.arange(A,B+1)
count_U = len(u)
u_c = [i for i in u if i % C == 0]
count_C = len(u_c)
u_d = [i for i in u if i % D == 0]
count_D = len(u_d)
u_e = [i for i in u if i % E == 0]
count_E = len(u_e)

answer = count_U - (count_C + count_D -count_E)
print(answer)


Fixed submission:
from fractions import gcd
 
a, b, c, d = map(int, input().split())
a = a - 1
 
def main():
    cd = c * d // gcd(c, d)
    print(b - a - f(c) - f(d) + f(cd))
 
def f(x):
    return b // x - a // x
 
main()

Buggy python submission (verdict: Runtime Error):
import numpy as np
import math
A, B, C, D = list(map(int, input().split()))

def lcm(x, y):
    return (x * y) // math.gcd(x, y)
E = lcm(C, D)

u = np.arange(A,B+1)
count_U = len(u)
u_c = [i for i in u if i % C == 0]
count_C = len(u_c)
u_d = [i for i in u if i % D == 0]
count_D = len(u_d)
u_e = [i for i in u if i % E == 0]
count_E = len(u_e)

answer = count_U - (count_C + count_D -count_E)
print(u)
print(u_c)
print(count_C)
print(u_d)
print(count_D)
print(u_e)
print(count_E)
print(answer)

Fixed submission:
from fractions import gcd
 
a, b, c, d = map(int, input().split())
a = a - 1
 
def main():
    cd = c * d // gcd(c, d)
    print(b - a - f(c) - f(d) + f(cd))
 
def f(x):
    return b // x - a // x
 
main()
Buggy python submission (verdict: Runtime Error):
x,a=int(input().split())

if x<a:
  print(0)
else:
  print(10)


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

if x<a:
  print(0)
else:
  print(10)

Buggy python submission (verdict: Runtime Error):
x=int(input())
a=int(input())

if x<a:
  print(0)
else:
  print(10)

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

if x<a:
  print(0)
else:
  print(10)

Buggy python submission (verdict: Runtime Error):
a=int(input())
x=int(input())
if x<10:
  print(0)
else:
  print(10)

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

if x<a:
  print(0)
else:
  print(10)
Buggy python submission (verdict: Runtime Error):
wakarimasendesitaaaaaaaaaaaa
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAA!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Fixed submission:
#  D -Lamp
h,w=map(int,input().split())
g=[input() for i in range(h)]
l=[[0]*w for i in range(h)]
r=[[0]*w for i in range(h)]
u=[[0]*w for i in range(h)]
o=[[0]*w for i in range(h)]

for i in range(h):
    if g[i][0]=='.':
        l[i][0]=1

for i in range(h):
    for j in range(w-1):
        if g[i][j+1]=='.':
            l[i][j+1]=l[i][j]+1
        elif g[i][j+1]=='#':
            l[i][j+1]=0

for i in range(h):
    if g[i][w-1]=='.':
        r[i][w-1]=1

for i in range(h):
    for j in range(w-1,0,-1):
        if g[i][j-1]=='.':
            r[i][j-1]=r[i][j]+1
        elif g[i][j-1]=='#':
            r[i][j-1]=0

for i in range(w):
    if g[0][i]=='.':
        u[0][i]=1

for i in range(w):
    for j in range(h-1):
        if g[j+1][i]=='.':
            u[j+1][i]=u[j][i]+1
        elif g[j+1][i]=='#':
            u[j+1][i]=0

for i in range(w):
    if g[h-1][i]=='.':
        o[h-1][i]=1

for i in range(w):
    for j in range(h-1,0,-1):
        if g[j-1][i]=='.':
            o[j-1][i]=o[j][i]+1
        elif g[j-1][i]=='#':
            o[j-1][i]=0

ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,l[i][j]+r[i][j]+u[i][j]+o[i][j]-3)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# ABC
s=input()
s=s.replace('BC','D')
is_ABC=True
ans=0
while is_ABC:
    t=s.count('AD')
    ans+=t
    s=s.replace('AD','DA')
    if t==0:
        is_ABC=False
print(ans)


Fixed submission:
s=input()
s=s.replace("BC","D")
s=s.replace("B","E")
s=s.replace("C","E")
s=s.split("E")

t=[]
for ss in s:
  if len(ss)!=0:
    t.append(ss)
ans=0

for tt in t:
  d_cnt=0
  for i,ttt in enumerate(tt):
    if ttt=="D":
      ans+=i-d_cnt
      d_cnt+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# ABC
s=input()
s=s.replace('BC','D')
is_ABC=True
ans=0
while is_ABC:
    t=s.count('AD')
    ans+=t
    s=s.replace('AD','DA')
    if t==0:
        is_ABC=False
print(ans)


Fixed submission:
s=input()
s=s.replace("BC","D")
s=s.replace("B","E")
s=s.replace("C","E")
s=s.split("E")

t=[]
for ss in s:
  if len(ss)!=0:
    t.append(ss)
ans=0

for tt in t:
  d_cnt=0
  for i,ttt in enumerate(tt):
    if ttt=="D":
      ans+=i-d_cnt
      d_cnt+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
# ABC126 D - Even Relation
# import sys
# sys.setrecursionlimit(20000000)

def dfs(node,distance):
    for next_node,edge_distangce in G[node]:
        if ans[next_node]==-1:
            ans[next_node] = (distance+edge_distangce)%2
            dfs(next_node,distance+edge_distangce)

N = int(input())
G = [[] for _ in range(N)]

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

ans = [-1]*N
dfs(0,0)
print(*ans,sep='\n')

Fixed submission:
# ABC126 D - Even Relation
import sys
sys.setrecursionlimit(20000000)

def dfs(node,distance):
    for next_node,edge_distangce in G[node]:
        if ans[next_node]==-1:
            ans[next_node] = (distance+edge_distangce)%2
            dfs(next_node,distance+edge_distangce)

N = int(input())
G = [[] for _ in range(N)]

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

ans = [-1]*N
dfs(0,0)
print(*ans,sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
# B - RGB Boxes
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
R,G,B,N = map(int, input().split())
ans = 0
for r in range(3001):
    for g in range(N-r+1):
        t = N-(R*r+g*G)
        if t>=0 and t%B==0:
            ans += 1
print(ans)

Fixed submission:
# B - RGB Boxes
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
R,G,B,N = map(int, input().split())
ans = 0
for r in range(3001):
    for g in range(N-r+1):
        t = N-(R*r+g*G)
        if t>=0 and t%B==0:
            ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# B - RGB Boxes
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
R,G,B,N = map(int, input().split())
ans = 0
for r in range(3001):
    for g in range(3001):
        t = N-(R*r+g*G)
        if t>=0 and t%B==0:
            ans += 1
print(ans)


Fixed submission:
# B - RGB Boxes
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
R,G,B,N = map(int, input().split())
ans = 0
for r in range(3001):
    for g in range(N-r+1):
        t = N-(R*r+g*G)
        if t>=0 and t%B==0:
            ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
a,b,t=map(int,input().split())
print(int(((t+0.5)//a)＊b))

Fixed submission:
a, b, t = map(int, input().split())

ans = int(((t+0.5)//a)*b)
print(ans)

Buggy python submission (verdict: Runtime Error):
a,b,t=map(int,input().split())
print((t+0.5)//a＊b)

Fixed submission:
a, b, t = map(int, input().split())

ans = int(((t+0.5)//a)*b)
print(ans)

Buggy python submission (verdict: Runtime Error):
a,b,t=map(int,input().split())
print((t+0.5)＊b/a)

Fixed submission:
a, b, t = map(int, input().split())

ans = int(((t+0.5)//a)*b)
print(ans)
Buggy python submission (verdict: Runtime Error):
# ABC124 D - Handstand
from math import ceil
n,k=map(int,input().split())
s=input()

l=[]
tmp=''
t_cnt=0
for i,ss in enumerate(s):
    if i==0:
        tmp=ss
        t_cnt+=1
        if len(s)==1:
            l.append(t_cnt)
            break
        continue
    if i==n-1:
        if ss==tmp:
            t_cnt+=1
            l.append(t_cnt)
        else:
            t_cnt=1
            l.append(t_cnt)
        continue
    if ss==tmp:
        t_cnt+=1
    else:
        l.append(t_cnt)
        t_cnt=1
        tmp=ss

# print(l)
l+=[0]
ans=0
if s[0]=='0':
    for i in range(0,ceil(n/2),2):
        if i==0:
            ans=sum(l[:2*k-1])
            continue
        ans=max(ans,ans+l[i+1]-l[i-1])
else:
    for i in range(1,ceil(n/2)+1,2):
        if i==1:
            ans=sum(l[:2*k+1])
            continue
        ans=max(ans,ans+l[i+1]-l[i-1])
    
print(ans)


Fixed submission:
n,k=map(int,input().split())
s=input()
l=[]
if s[0]=="0":
  l.append(0)

from itertools import groupby,accumulate
gr=groupby(s)

for K,g in gr:
  l.append(len(list(g)))

l_sum=list(accumulate(l))
l_sum=[0]+l_sum

add=2*k+1
ans=0
for i in range(0,len(l)+1,2):
  left=i
  right=min(i+add,len(l))
  tmp=l_sum[right]-l_sum[left]
  ans=max(tmp,ans)
print(ans)
Buggy python submission (verdict: Runtime Error):
waaaaaaaaaaaaaaaaaaaaaannnnnnnnnn

Fixed submission:
# D - Cake 123
x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ab=[i+j for j in b for i in a]
ab.sort(reverse=True)
abc=[i+j for j in c[:k] for i in ab[:k]]
abc.sort(reverse=True)

print(*abc[:k],sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
ans=0
for i in range(q):
    l,r=map(int,input().split())
    st=s[l-1:r]
    t=st.count('AC')
    print(t)

Fixed submission:
N,Q = map(int,input().split())
S = input()
t = [0] * (N + 1)

for i in range(N):
    if S[i : i + 2] == 'AC':
        t[i + 1] = t[i] + 1
    else:
        t[i + 1] = t[i]

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
Buggy python submission (verdict: Runtime Error):
oteage

Fixed submission:
n=int(input())
mod=10**9+7
memo=[{} for i in range(n+1)]

def ok(last4):
  for i in range(4):
    t=list(last4)
    if i>=1:
      t[i-1],t[i]=t[i],t[i-1]
    if "".join(t).count("AGC")>=1:
      return False
  return True

def dfs(cur,last3):
  if last3 in memo[cur]:
    return memo[cur][last3]
  if cur==n:
    return 1
  res=0
  for c in "ACGT":
    if ok(last3+c):
      res=(res+dfs(cur+1,last3[1:]+c))%mod
  memo[cur][last3]=res
  return res

print(dfs(0,"TTT"))
Buggy python submission (verdict: Runtime Error):
# ABC121 D - XOR World
from math import log2,ceil
a,b=map(int,input().split())
if a==0:
    pass
elif a>=2:
    na=int(ceil(log2(a)))
nb=int(ceil(log2(b)))
l=[0]*(nb+1)

if a>=2:
    a-=1
    for i in range(na+1):
        q=a//(2**(i+1))
        r=a%(2**(i+1))
        r-=2**i
        if r<0:
            r=0
        elif r>=0:
            r+=1
        l[i]-=q*2**i+r

for i in range(nb+1):
    q=b//(2**(i+1))
    r=b%(2**(i+1))
    r-=2**i
    if r<0:
        r=0
    elif r>=0:
        r+=1
    l[i]+=q*2**i+r

for i in range(len(l)):
    l[i]=l[i]%2

ans=0
for i in range(len(l)):
    ans+=l[i]*2**i
print(ans)

Fixed submission:
# ABC121 D - XOR World
from math import log2,ceil
a,b=map(int,input().split())
if a==0 and b==0:
    print(0)
    exit()
if a==0:
    pass
elif a>=2:
    na=int(ceil(log2(a)))
nb=int(ceil(log2(b)))
l=[0]*(nb+1)

if a>=2:
    a-=1
    for i in range(na+1):
        q=a//(2**(i+1))
        r=a%(2**(i+1))
        r-=2**i
        if r<0:
            r=0
        elif r>=0:
            r+=1
        l[i]-=q*2**i+r

for i in range(nb+1):
    q=b//(2**(i+1))
    r=b%(2**(i+1))
    r-=2**i
    if r<0:
        r=0
    elif r>=0:
        r+=1
    l[i]+=q*2**i+r

for i in range(len(l)):
    l[i]=l[i]%2

ans=0
for i in range(len(l)):
    ans+=l[i]*2**i
print(ans)
Buggy python submission (verdict: Runtime Error):
#ABC119 D - Lazy Faith
from bisect import bisect_left,bisect_right
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

a,b,q = map(int, input().split())
INF = 10**11
S = [-INF]+[int(input()) for _ in range(a)]+[INF]
T = [-INF]+[int(input()) for _ in range(b)]+[INF]
X = [int(input()) for _ in range(q)]

for i in range(q):
    idx_s = bisect_left(S,X[i])
    idx_t = bisect_left(T,X[i])
    ans = INF
    for s in [S[idx_s-1],S[idx_s]]:
        for t in [T[idx_s-1],T[idx_s]]:
            d1,d2 = abs(s-X[i])+abs(s-t),abs(t-X[i])+abs(t-s)
            ans = min(ans,d1,d2)
    print(ans)


Fixed submission:
#ABC119 D - Lazy Faith
from bisect import bisect_left,bisect_right
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

a,b,q = map(int, input().split())
INF = 10**11
S = [-INF]+[int(input()) for _ in range(a)]+[INF]
T = [-INF]+[int(input()) for _ in range(b)]+[INF]
X = [int(input()) for _ in range(q)]

for i in range(q):
    idx_s = bisect_right(S,X[i])
    idx_t = bisect_right(T,X[i])
    ans = INF
    for s in [S[idx_s-1],S[idx_s]]:
        for t in [T[idx_t-1],T[idx_t]]:
            d1,d2 = abs(s-X[i])+abs(s-t),abs(t-X[i])+abs(t-s)
            ans = min(ans,d1,d2)
    print(ans)

Buggy python submission (verdict: Runtime Error):
uwaaaaaaaaaaaaaaaaaaaaaa

Fixed submission:
#ABC119 D - Lazy Faith
from bisect import bisect_left,bisect_right
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

a,b,q = map(int, input().split())
INF = 10**11
S = [-INF]+[int(input()) for _ in range(a)]+[INF]
T = [-INF]+[int(input()) for _ in range(b)]+[INF]
X = [int(input()) for _ in range(q)]

for i in range(q):
    idx_s = bisect_right(S,X[i])
    idx_t = bisect_right(T,X[i])
    ans = INF
    for s in [S[idx_s-1],S[idx_s]]:
        for t in [T[idx_t-1],T[idx_t]]:
            d1,d2 = abs(s-X[i])+abs(s-t),abs(t-X[i])+abs(t-s)
            ans = min(ans,d1,d2)
    print(ans)
Buggy python submission (verdict: Runtime Error):
from math import gcd
# def lcm(x,y):
#   return (x*y)//gcd(x,y)

n=int(input())
a=list(map(int,input().split()))
ans=10**18
t=0
for i in range(1,n):
  if i==1:
    t=gcd(a[i-1],a[i])
    continue
  t=gcd(t,a[i])
  ans=min(t,ans)
print(ans)


Fixed submission:
# ABC118 C - Monsters Battle Royale
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
ans = 10**10

for i in range(n-1):
    t = gcd(a[i],a[i+1])
    ans = min(ans,t)
print(ans)
Buggy python submission (verdict: Runtime Error):
# B - KEYENCE String
S = input()
K = list('keyence')
count = 0
idx_k = 0
is_NG = False

for s in S:
    if K[idx_k]==s:
        if idx_k<7:
            idx_k += 1
        is_NG = False
    else:
        if not is_NG:
            count +=1
            is_NG = True
    
    if count>=2:
        break
  
if count<=1 and idx_k==7:
    print('YES')
else:
    print('NO')


Fixed submission:
# B 
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
s=si()
n=len(s)
for i in range(n):
    for j in range(n-i+1):
        t=s
        t=t[:j]+t[j+i+1:]
        if t=='keyence':
            print('YES')
            exit()
print('NO')

Buggy python submission (verdict: Runtime Error):
# B - KEYENCE String
S = input()
K = list('keyence')
count = 0
idx_k = 0
is_NG = False

for s in S:
    if K[idx_k]==s:
        if is_NG == True:
            is_NG = False    
        idx_k += 1
    else:
        if is_NG == False:
            count +=1
            is_NG = True
  
if count<=1 and idx_k==7:
    print('YES')
else:
    print('NO')


Fixed submission:
# B 
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
s=si()
n=len(s)
for i in range(n):
    for j in range(n-i+1):
        t=s
        t=t[:j]+t[j+i+1:]
        if t=='keyence':
            print('YES')
            exit()
print('NO')
Buggy python submission (verdict: Time Limit Exceeded):
N,W=map(int,input().split())
w,v=[],[]
for i in range(N):
  a,b=map(int,input().split())
  w.append(a)
  v.append(b)
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(N):
  for j in range(W+1):
      if j-w[i]>=0:
          dp[i+1][j]=dp[i][j-w[i]]+v[i]
      dp[i+1][j]=max(dp[i+1][j],dp[i][j])
print(dp[N][W])

Fixed submission:
# D - Knapsack 1 Educational DP Contest / DP
import numpy as np

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

dp = np.zeros(W+1, dtype=np.int64)
for _ in range(N):
    w,v = map(int,input().split())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])

ans = dp.max()
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# D - Knapsack 1
N,W=map(int,input().split())
w,v=[],[]
for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)

dp=[[0]*(W+1) for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        # 選ぶ場合
        if j-w[i]>=0:
            dp[i+1][j]=dp[i][j-w[i]]+v[i]
        dp[i+1][j]=max(dp[i+1][j],dp[i][j])
print(dp[N][W])

Fixed submission:
# D - Knapsack 1 Educational DP Contest / DP
import numpy as np

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

dp = np.zeros(W+1, dtype=np.int64)
for _ in range(N):
    w,v = map(int,input().split())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])

ans = dp.max()
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# D - Knapsack 1 Educational DP Contest / DP
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

N,W = nm()
Weight = []
Value = []

for i in range(N):
    w,v = nm()
    Weight.append(w)
    Value.append(v)

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j >= Weight[i]:
            dp[i+1][j] = max(dp[i][j-Weight[i]]+Value[i],dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[N][W])

Fixed submission:
# D - Knapsack 1 Educational DP Contest / DP
import numpy as np

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

dp = np.zeros(W+1, dtype=np.int64)
for _ in range(N):
    w,v = map(int,input().split())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])

ans = dp.max()
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# F - LCS
s=input()
t=input()
ns=len(s)
nt=len(t)
dp=[[0]*(nt+1) for i in range(ns+1)]

for i in range(ns):
    for j in range(nt):
        if s[i]==t[j]:
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1)
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
ans=''
i,j=ns,nt
while i>0 and j>0:
    # (i-1, j) -> (i, j) と更新されていた場合
    if dp[i][j]==dp[i-1][j]:
        i-=1
    #  (i, j-1) -> (i, j) と更新されていた場合
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    #  (i-1, j-1) -> (i, j) と更新されていた場合
    else:
        ans=s[i-1]+ans
        i-=1
        j-=1
print(ans)

Fixed submission:
# F - LCS
s=input()
t=input()
ns=len(s)
nt=len(t)
dp=[[0]*(nt+1) for i in range(ns+1)]

for i in range(ns):
    for j in range(nt):
        if s[i]==t[j]:
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1)
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
ans=''
i,j=ns,nt
while i>0 and j>0:
    # (i-1, j) -> (i, j) と更新されていた場合
    if dp[i][j]==dp[i-1][j]:
        i-=1
    #  (i, j-1) -> (i, j) と更新されていた場合
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    #  (i-1, j-1) -> (i, j) と更新されていた場合
    else:
        ans=s[i-1]+ans
        i-=1
        j-=1
print(ans)
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    G[x].append(y)

dp = [-1]*(n+1)
# dp[i]:頂点iに到達したときの有向辺の最長の長さ
def dfs(cur):
    if dp[cur] != -1:
        return dp[cur]
    res = 0
    for nx in G[cur]:
        res = max(res,dfs(nx)+1)
    dp[cur] = res
    return res
    
for i in range(n):
    dp[i] = max(dp[i],dfs(i))

print(max(dp))


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

def dfs(cur):
  if dp[cur]!=-1:
    return dp[cur]
  res=0
  for nx in G[cur]:
    res=max(res,dfs(nx)+1)
  dp[cur]=res
  return res

n,m=map(int,input().split())
G=[[] for i in range(n)]
for i in range(m):
  x,y=map(int,input().split())
  G[x-1].append(y-1)

dp=[-1]*n
for i in range(n):
  dp[i]=max(dp[i],dfs(i))
print(max(dp))
Buggy python submission (verdict: Runtime Error):
from fractions import gcd
def lcm(x,y):
    return x*y//gcd(x,y)
n,m = map(int,input().split())
s=input()
t=input()
ss=''
tt=''

l=lcm(n,m)
x=['*']*l

for i in range(n):
    x[i*(l//n)]=s[i]

for i in range(m):
    x[i*(l//m)]=t[i]

for i in range(n):
    if x[i*(l//n)]!=s[i]:
        print(-1)
        exit()

for i in range(m):
    if x[i*(l//m)]!=t[i]:
        print(-1)
        exit()
print(l)


Fixed submission:
from fractions import gcd
def lcm(x,y):
    return x*y//gcd(x,y)
n,m = map(int,input().split())
s=input()
t=input()

l=lcm(n,m)
x=dict()

for i in range(n):
    x[i*(l//n)]=s[i]

for i in range(m):
    j=i*(l//m)
    if j in x and x[j]!=t[i]:
        print(-1)
        exit()
print(l)

Buggy python submission (verdict: Runtime Error):
from fractions import gcd
def lcm(x,y):
    return x*y//gcd(x,y)
n,m = map(int,input().split())
s=input()
t=input()
ss=''
tt=''

l=lcm(n,m)
x=['x']*l

for i in range(n):
    x[i*(l//n)]=s[i]

for i in range(m):
    x[i*(l//m)]=t[i]

for i in range(n):
    if x[i*(l//n)]!=s[i]:
        print(-1)
        exit()

for i in range(m):
    if x[i*(l//m)]!=t[i]:
        print(-1)
        exit()
print(l)


Fixed submission:
from fractions import gcd
def lcm(x,y):
    return x*y//gcd(x,y)
n,m = map(int,input().split())
s=input()
t=input()

l=lcm(n,m)
x=dict()

for i in range(n):
    x[i*(l//n)]=s[i]

for i in range(m):
    j=i*(l//m)
    if j in x and x[j]!=t[i]:
        print(-1)
        exit()
print(l)

Buggy python submission (verdict: Runtime Error):
from math import gcd
def lcm(x,y):
    return x*y//gcd(x,y)
n,m = map(int,input().split())
s=input()
t=input()
ss=''
tt=''

l=lcm(n,m)
x=['x']*l

for i in range(n):
    x[i*(l//n)]=s[i]

for i in range(m):
    x[i*(l//m)]=t[i]

for i in range(n):
    if x[i*(l//n)]!=s[i]:
        print(-1)
        exit()

for i in range(m):
    if x[i*(l//m)]!=t[i]:
        print(-1)
        exit()
print(l)


Fixed submission:
from fractions import gcd
def lcm(x,y):
    return x*y//gcd(x,y)
n,m = map(int,input().split())
s=input()
t=input()

l=lcm(n,m)
x=dict()

for i in range(n):
    x[i*(l//n)]=s[i]

for i in range(m):
    j=i*(l//m)
    if j in x and x[j]!=t[i]:
        print(-1)
        exit()
print(l)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = int(input())
b = int(input())

if n==1:
    print("Hello World")
elif n==2:
    print(a+b)


Fixed submission:
n = int(input())


if n==1:
    print("Hello World")
elif n==2:
    a = int(input())
    b = int(input())
    print(a+b)