Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=(1+a[i])/2
x=[0]*(n+k-1)
for i in range(n):
  for j in range(i,i+k):
    x[j]+=a[i]
print('{:.10f}'.format(max(x)))

Fixed submission:
a,b=input().split()
x,y=map(int,input().split())
c=input()
if a==c:
  x=x-1
else:
  y=y-1
print(x,y)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=(1+a[i])/2
x=[0]*(n+k-1)
for i in range(n):
  for j in range(i,i+k):
    x[j]+=a[i]
print('{:.10f}'.format(max(x)))

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

tmp=sum(p[:k])
ans=tmp
for i in range(n-k):
    tmp=tmp-p[i]+p[i+k]
    if tmp>ans:
        ans=tmp
print((ans+k)/2)

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=(1+a[i])/2
x=[0]*(n+k-1)
for i in range(n):
  for j in range(i,i+k):
    x[j]+=a[i]
print('{:.10f}'.format(max(x)))

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

tmp=sum(p[:k])
ans=tmp
for i in range(n-k):
    tmp=tmp-p[i]+p[i+k]
    if tmp>ans:
        ans=tmp
print((ans+k)/2)
Buggy python submission (verdict: Runtime Error):
    N,M = map(int, input().split())
	ac = [0]*N
	wa = [0]*N
	for i in range(M):
		p,s = input().split()
		if s == 'AC':
			if ac[int(p) - 1] != 0:
				continue
			else:	
				ac[int(p) - 1] = 1
		else:
			if ac[int(p) - 1] != 0:
				continue
			else:
				wa[int(p) - 1] += 1
	AC,WA = 0,0

	for i in range(N):
		AC += ac[i]
		if ac[i] >= 1:
			WA += wa[i]
	print(AC,WA)




Fixed submission:
N,M = map(int, input().split())
ac = [0]*N
wa = [0]*N
for i in range(M):
	p,s = input().split()
	if s == 'AC':
		if ac[int(p) - 1] != 0:
			continue
		else:	
			ac[int(p) - 1] = 1
	else:
		if ac[int(p) - 1] != 0:
			continue
		else:
			wa[int(p) - 1] += 1
AC,WA = 0,0

for i in range(N):
  AC += ac[i]
  if ac[i] >= 1:
    WA += wa[i]
print(AC,WA)
Buggy python submission (verdict: Time Limit Exceeded):
n,k,q=map(int,input().split())
a=[k]*n
for i in range(q):
  x=int(input())-1
  d=[1]*n
  a = [x - y for (x, y) in zip(a,d)]
  a[x]+=1
for i in range(n):
  if a[i]>0:
    print("Yes")
  else:
    print("No")

Fixed submission:
n,k,q=map(int,input().split())
a=[0]*n
for i in range(q):
  x=int(input())-1
  a[x]+=1
for i in range(n):
  if k-(q-a[i])>0:
    print("Yes")
  else:
    print("No")

Buggy python submission (verdict: Time Limit Exceeded):
n,k,q=map(int,input().split())
a=[]
for i in range(q):
  x=int(input())
  a.append(x-1)

C=[0]*n
for i in range(n):
  C[i]=a.count(i)
  if k-(q-C[i])>0:
    print("Yes")
  else:
    print("No")

Fixed submission:
n,k,q=map(int,input().split())
a=[0]*n
for i in range(q):
  x=int(input())-1
  a[x]+=1
for i in range(n):
  if k-(q-a[i])>0:
    print("Yes")
  else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
l,r=map(int,input().split())
if r-l+1>=2019:
  print(0)
else:
  l=l%2019
  r=r%2019
  
  if l>=r:
    print(0)
    exit()
ans=10000000
for i in range(l,r+1):
  for j in range(i+1,r+1):
    ans=min(ans,(i*j)%2019)
print(ans)

Fixed submission:
l,r=map(int,input().split())
if r-l+1>=2019:
  print(0)
  exit()
else:
  l=l%2019
  r=r%2019
  
  if l>=r:
    r+=2019
ans=10000000
for i in range(l,r+1):
  for j in range(i+1,r+1):
    ans=min(ans,(i*j)%2019)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
l,r=map(int,input().split())
if r-l+1>=2019:
  print(0)
else:
  l=l%2019
  r=r%2019
  
  if l>=r:
    r+=2019
ans=10000000
for i in range(l,r+1):
  for j in range(i+1,r+1):
    ans=min(ans,(i*j)%2019)
print(ans)

Fixed submission:
l,r=map(int,input().split())
if r-l+1>=2019:
  print(0)
  exit()
else:
  l=l%2019
  r=r%2019
  
  if l>=r:
    r+=2019
ans=10000000
for i in range(l,r+1):
  for j in range(i+1,r+1):
    ans=min(ans,(i*j)%2019)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
l,r=map(int,input().split())
if r-l+1>=2019:
  print(0)
else:
  l=l%2019
  r=r%2019
  
  if l>=r:
    r+=2019
ans=10000000
for i in range(l,r+1):
  for j in range(i+1,r+1):
    ans=min(ans,(i*j)%2019)
print(ans)

Fixed submission:
l,r=map(int,input().split())
if r-l+1>=2019:
  print(0)
  exit()
else:
  l=l%2019
  r=r%2019
  
  if l>=r:
    r+=2019
ans=10000000
for i in range(l,r+1):
  for j in range(i+1,r+1):
    ans=min(ans,(i*j)%2019)
print(ans)
Buggy python submission (verdict: Runtime Error):
w,h,x,y=map(int,input().split())
if 2*x==w and 2*y==h:
  q=1
else:
  q==0
p=[max(min(x*h,(w-x)*h),(min(y*w,(h-y)*w))),q]
print(*p)

Fixed submission:
w,h,x,y=map(int,input().split())
if 2*x==w and 2*y==h:
  q=1
else:
  q=0
p=[w*h/2,q]
print(*p)
Buggy python submission (verdict: Time Limit Exceeded):
r,g,b,n=map(int,input().split())
R=n//r
ans=0
for i in range(R+1):
  for j in range(((n-i*r)//g)+2):
    if 0<=n-i*r-j*g and (n-i*r-j*g)%b==0:
      ans+=1
print(ans)

Fixed submission:
r,g,b,n=map(int,input().split())
R=n//r
ans=0
for i in range(R+1):
  for j in range(((n-i*r)//g)+2):
    if 0<=n-i*r-j*g and (n-i*r-j*g)%b==0:
      ans+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a=int(n/4)+1
b=int(n/7)+1
ans=0
for i in range(a+1):
  for j in range(b+1):
    if 4*i+7*j=n:
      ans+=1
if ans==0:
  print("No")
else:
  print("Yes")

Fixed submission:
n = int(input())
a=int(n/4)+1
b=int(n/7)+1
ans=0
for i in range(a+1):
  for j in range(b+1):
    if 4*i+7*j==n:
      ans+=1
if ans==0:
  print("No")
else:
  print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
N=list(map(int,input().split()))
m=int(input())
M=list(map(int,input().split()))

for i in M:
  if i in N:
    N.remove(i)
  else:
    print("NO")
    exit()
print("YES")

Fixed submission:
from collections import Counter
n = int(input())
d= Counter(list(map(int, input().split())))
m = int(input())
t= Counter(list(map(int, input().split())))
if t-d=={}:
    print("YES")
else:
    print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
dic = []
for _ in range(N):
  A = input()
  if A in dic:
    dic.remove(A)
  else:
    dic.append(A)
print(len(dic))

Fixed submission:
N = int(input())
dic = {}
for _ in range(N):
  A = input()
  if A in dic:
    del dic[A]
  else:
    dic[A]=0
print(len(dic))

Buggy python submission (verdict: Time Limit Exceeded):
import collections

n=int(input())
a=[0]*n
for i in range(n):
  a[i]=int(input())
  
c = collections.Counter(a)
l=len(set(a))
ans=0

for i in range(l):
  a[i]=c.most_common()[i][1]
  if a[i]%2==1:
    ans+=1
print(ans)


Fixed submission:
N = int(input())
dic = {}
for _ in range(N):
  A = input()
  if A in dic:
    del dic[A]
  else:
    dic[A]=0
print(len(dic))
Buggy python submission (verdict: Runtime Error):
N=int(input())
a=list(map(int,input().split()))
m=max(a)
mm=min(a)
p=[0]*(m-mm)

if 1<=len(a)<=3:
  print(len(a))
else:
  for i in range(mm,m-1):
    p[i]=a.count(i)+a.count(i+1)+a.count(i+2)
  print(max(p))

Fixed submission:
N=int(input())
a=list(map(int,input().split()))
M=max(a)
m=min(a)
x=[0]*(M-m+3)
for i in a:
  x[i-m]+=1
  x[i-m+1]+=1
  x[i-m+2]+=1
print(max(x))

Buggy python submission (verdict: Runtime Error):
N=int(input())
a=list(map(int,input().split()))
m=max(a)
mm=min(a)
p=[0]*(m-mm)

if 1<=len(a)<=3:
  print(len(a))
else:
  for i in range(mm,m-1):
    p[i]=a.count(i)+a.count(i+1)+a.count(i+2)
  print(max(p))

Fixed submission:
N=int(input())
a=list(map(int,input().split()))
M=max(a)
m=min(a)
x=[0]*(M-m+3)
for i in a:
  x[i-m]+=1
  x[i-m+1]+=1
  x[i-m+2]+=1
print(max(x))

Buggy python submission (verdict: Runtime Error):
N=int(input())
a=list(map(int,input().split()))
m=max(a)
mm=min(a)
p=[0]*(m-mm)

for i in range(mm,m-1):
  p[i]=a.count(i)+a.count(i+1)+a.count(i+2)
  
print(max(p))

Fixed submission:
N=int(input())
a=list(map(int,input().split()))
M=max(a)
m=min(a)
x=[0]*(M-m+3)
for i in a:
  x[i-m]+=1
  x[i-m+1]+=1
  x[i-m+2]+=1
print(max(x))

Buggy python submission (verdict: Runtime Error):
N=int(input())
a=list(map(int,input().split()))
m=max(a)
p=[0]*(m-1)

for i in range(m-1):
  p[i]=a.count(i)+a.count(i+1)+a.count(i+2)
  
print(max(p))

Fixed submission:
N=int(input())
a=list(map(int,input().split()))
M=max(a)
m=min(a)
x=[0]*(M-m+3)
for i in a:
  x[i-m]+=1
  x[i-m+1]+=1
  x[i-m+2]+=1
print(max(x))
Buggy python submission (verdict: Runtime Error):
S=set(input())
A={"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"}
D=sorted(list(A-S))
print(D[0])

Fixed submission:
S=set(input())
A={"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"}
D=sorted(list(A-S))
if len(D)==0:
  print("None")
else:
  print(D[0])
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
b=-1
ans=[]
for ai in a:
  if len(ans)==2:
    break
  if b==ai:
    ans.append(ai)
    b=-1
  else:
    b=ai
print(ans[0]*ans[1])

Fixed submission:
n=int(input())
a=sorted((list(map(int,input().split()))),reverse=True)
con=1
sta=a[0]
check=0
for i in range(1,n):
  if a[i]==sta:
    con+=1
    if con==2:
      check+=1
      x=sta
      a.remove(sta)
      a.remove(sta)
      break
  else:
    con=1
    sta=a[i]
sta=a[0]
con=1
for i in range(1,n-2):
  if a[i]==sta:
    con+=1
    if con==2:
      check+=1
      y=sta
      break
  else:
    con=1
    sta=a[i]
print(x*y if check==2 else "0")
Buggy python submission (verdict: Runtime Error):
import math

P=[]
n=int(input())
N=int(math.sqrt(n))

for i in range(1,n+1):
  if n%i==0:
    p=max(len(str(i)),len(str(int(n/i))))
    P.append(p)
    
print(min(P))

Fixed submission:
a,b=map(int,input().split())
if a+b<24:
  print(a+b)
else:
  print(a+b-24)
Buggy python submission (verdict: Time Limit Exceeded):
import math

P=[]
n=int(input())
N=int(math.sqrt(n))

for i in range(1,n+1):
  if n%i==0:
    p=max(len(str(i)),len(str(int(n/i))))
    P.append(p)
    
print(min(P))

Fixed submission:
import math

P=[]
n=int(input())
N=int(math.sqrt(n))

for i in range(1,N+2):
  if n%i==0:
    p=max(len(str(i)),len(str(int(n/i))))
    P.append(p)
    
print(min(P))

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

P=[]
n=int(input())
N=int(math.sqrt(n))

for i in range(1,n+1):
  if n%i==0:
    p=max(len(str(i)),len(str(int(n/i))))
    P.append(p)
    
print(min(P))

Fixed submission:
import math

P=[]
n=int(input())
N=int(math.sqrt(n))

for i in range(1,N+2):
  if n%i==0:
    p=max(len(str(i)),len(str(int(n/i))))
    P.append(p)
    
print(min(P))
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
ans=0
for i in range(n+1):
  for j in range(n+1):
    for l in range(n+1):
      if i+j+l==k:
        ans+=1
print(ans)


Fixed submission:
n,k=map(int,input().split())
ans=0
for i in range(n+1):
  for j in range(n+1):
    if 0<=k-i-j<=n:
      ans+=1
print(ans)

Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
ans=0
for i in range(n+1):
  for j in range(n+1):
    for l in range(n+1):
if i+j+l==k:
  ans+=1
print(ans)

Fixed submission:
n,k=map(int,input().split())
ans=0
for i in range(n+1):
  for j in range(n+1):
    if 0<=k-i-j<=n:
      ans+=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a,b,n=map(int,input().split())
ans=0
for i in range(a,b+1):
  if i%n==0:
    ans+=1
print(ans)

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

if a%n==0:
  x=a//n
else:
  x=((a//n)+1)
  
if b%n==0:
  y=b//n
else:
  y=((b//n))
  
print(y-x+1)
Buggy python submission (verdict: Runtime Error):
a,b,c = map(int,input().split())
d = a/3 + b/3 + c/3
if d == a or d == b or d == c:
  print(Yes)
else:
  print(No)

Fixed submission:
a,b,c = map(int,input().split())
d = a/2 + b/2 + c/2
if d == a or d == b or d == c:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
a,b,c = map(int,input().split())
if a = b and b = c:
  print(1)
elif a = b or b = c or a = c:
  print(2)
else:
  print(3)


Fixed submission:
a,b,c = map(int,input().split())
if a==b and b==c:
  print(1)
elif a==b or b==c or a==c:
  print(2)
else:
  print(3)

Buggy python submission (verdict: Runtime Error):
a,b,c = map(int,input().split())
if a=b and b=c:
  print(1)
elif a=b or b=c or a=c:
  print(2)
else:
  print(3)


Fixed submission:
a,b,c = map(int,input().split())
if a==b and b==c:
  print(1)
elif a==b or b==c or a==c:
  print(2)
else:
  print(3)

Buggy python submission (verdict: Runtime Error):
a,b,c = map(int,input().split())
if a=b and b=c:
  print(1)
elif (a=b or b=c or a=c):
  print(2)
else:
  print(3)


Fixed submission:
a,b,c = map(int,input().split())
if a==b and b==c:
  print(1)
elif a==b or b==c or a==c:
  print(2)
else:
  print(3)

Buggy python submission (verdict: Runtime Error):
a,b,c = map(int,input().split())
if a=b=c:
  print(1)
elif (a=b or b=c or a=c):
  print(2)
else:
  print(3)


Fixed submission:
a,b,c = map(int,input().split())
if a==b and b==c:
  print(1)
elif a==b or b==c or a==c:
  print(2)
else:
  print(3)

Buggy python submission (verdict: Runtime Error):
a,b,c = map(int.input().split())
if a=b and b=c:
  print(1)
elif (a=b or b=c or a=c):
  print(2)
else:
  print(3)


Fixed submission:
a,b,c = map(int,input().split())
if a==b and b==c:
  print(1)
elif a==b or b==c or a==c:
  print(2)
else:
  print(3)

Buggy python submission (verdict: Runtime Error):
a,b,c = map(int.input().split())
if a=b=c:
  print(1)
elif (a=b or b=c or a=c):
  print(2)
else:
  print(3)


Fixed submission:
a,b,c = map(int,input().split())
if a==b and b==c:
  print(1)
elif a==b or b==c or a==c:
  print(2)
else:
  print(3)

Buggy python submission (verdict: Runtime Error):
a,b,c = int(input().split())
if a=b=c:
  print(1)
elif (a=b or b=c or a=c):
  print(2)
else:
  print(3)


Fixed submission:
a,b,c = map(int,input().split())
if a==b and b==c:
  print(1)
elif a==b or b==c or a==c:
  print(2)
else:
  print(3)
Buggy python submission (verdict: Runtime Error):
S,W = map(int, input.split())

        if S > W :
            print("safe")
        else :
            print("unsafe")





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

if S > W :
    print("safe")
else :
    print("unsafe")
Buggy python submission (verdict: Runtime Error):
s=int(input())
if s=='ABC':
  print("ABC")
  
elif s=='ARC':
  print("ARC")

else:
  pass

Fixed submission:
s=str(input())
if s=='ABC':
  print('ARC')
  
elif s=='ARC':
  print('ABC')
  
else:
  pass
Buggy python submission (verdict: Time Limit Exceeded):
# D - I hate Factorization
x = (int)(input())

flg = False
for i in range(-x, x):
    for j in range(-x, x):
        if i ** 5 - j ** 5 == x:
            flg = True
            break
    
    if flg:
        break

print(str(i) + " " + str(j))

Fixed submission:
# D - I hate Factorization
x = (int)(input())

flg = False
if x >= 0:
    for i in range(0, x + 1):
        for j in range(-i - 1, i + 1):
            if i ** 5 - j ** 5 == x:
                flg = True
                break

        if flg:
            print(str(i) + " " + str(j))
            break
else:
    for i in range(0, x + 1):
        for j in range(-i - 1, i + 1):
            if i ** 5 - j ** 5 == x:
                flg = True
                break

        if flg:
            print(str(j) + " " + str(i))
            break
Buggy python submission (verdict: Time Limit Exceeded):
# C - Walk on Multiplication Table
n = (int)(input())

flg = False

minimum = n
for i in range(1, n):
    if n % i == 0:
        minimum = (int)(min(i + n / i - 2, minimum))

print(minimum)

Fixed submission:
# C - Walk on Multiplication Table
n = (int)(input())

minimum = 1e18
i = 1
while(i*i <= n):
    if n % i != 0:
        i += 1
        continue;
    j = (int) (n / i)
    minimum = min(i + j - 2, minimum)
    i +=1

print(minimum)
Buggy python submission (verdict: Time Limit Exceeded):
# D - Triangles
n = (int)(input())
length = list(map(int, input().split()))

sum = 0

for i in range(n):
    for j in range(n):
        for k in range(n):

            a = length[i]
            b = length[j]
            c = length[k]


            if i >= j or i >= k or j >= k:
                continue

            if a < b + c and b < c + a and c < a + b:
                sum += 1

print(sum)

Fixed submission:
# D - Triangles

import bisect

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

sum = 0

length.sort()

for i in range(n):
    for j in range(n):

            a = length[i]
            b = length[j]

            if i < j:
                k = bisect.bisect_left(length, a + b)
                sum += k - j - 1

print(max(0, sum))
Buggy python submission (verdict: Time Limit Exceeded):
# C - Go to School
n = (int)(input())

a = list(map(int, input().split()))
map = {}

for i in range(n):
    map[a[i]] = i + 1

a.sort()

result = ""
for j in a:
    result = result + str(map[j]) + " "

print(result[:-1])

Fixed submission:
# C - Go to School
n = (int)(input())

a = list(map(int, input().split()))
map = {}

for i in range(n):
    map[a[i]] = i + 1

a.sort()

result = ""
for j in a:
    print(map[j], end="")
    if len(a) != j:
        print(' ', end="")
Buggy python submission (verdict: Time Limit Exceeded):
# C - Attack Survival
n,k,q= map(int, input().split())

list = [k] * n

for i in range(q):
    a = int(input())
    for j in range(n):
        if j != a - 1:
            list[j] = list[j] - 1

for k in range(n):
    if(list[k] > 0):
        print('Yes')
    else:
        print('No')


Fixed submission:
# C - Attack Survival
n,k,q= map(int, input().split())

list = [0] * n

for i in range(q):
    a = int(input())
    list[a - 1] = list[a - 1] + 1

for j in range(n):

    if(k - q + list[j] > 0):
        print('Yes')
    else:
        print('No')
Buggy python submission (verdict: Time Limit Exceeded):
# D - Powerful Discount Tickets
n,m= map(int, input().split())

list = [int(s) for s in input().split()]

list.sort(reverse=True)

i = 0
while (m != 0):
    list[i] = (int)(list[i] / 2)
    m = m - 1
    if len(list) == 0:
        continue
    else:
        list.sort(reverse=True)

print(sum(list))

Fixed submission:
# D - Powerful Discount Tickets
import heapq
n,m= map(int, input().split())

a = [int(s) for s in input().split()]
a = list(map(lambda x: x*(-1), a))  # 各要素を-1倍

heapq.heapify(a)

while (m != 0):
    heapq.heappush(a, (int)(heapq.heappop(a) / 2))
    m = m - 1

print(-sum(a))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np

N = int(sys.stdin.readline())

dp = np.zeros((N+1, N+1))
ans = np.zeros((N+1, N+1, N+1))

def gcd(a, b):
    if a < b:
        a, b = b, a
    
    if dp[a][b] != 0:
        return dp[a][b]

    while b>0:
        a, b = b, a % b
    
    dp[a][b] = a
    return a

for i in range(1,N+1):
    for j in range(1,N+1):
        temp = gcd(i, j)
        for k in range(1,N+1):
            ans[i][j][k] = gcd(temp, k)
            
print(int(ans.sum()))

Fixed submission:
import sys
import numpy as np

from math import gcd

N = int(sys.stdin.readline())
ans = 0
"""
dp = np.zeros((N+1, N+1))
def gcd(a, b):
    if a < b:
        a, b = b, a
    
    if dp[a][b] != 0:
        return dp[a][b]

    while b>0:
        a, b = b, a % b
    
    dp[a][b] = a
    return a
"""
for i in range(1,N+1):
    for j in range(1,N+1):
        temp = gcd(i, j)
        for k in range(1,N+1):
            ans += gcd(temp, k)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
from math import gcd

def solv():
    n = int(input())
    ans = 0
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            a = gcd(i, j)
            for k in range(1, n + 1):
                ans += gcd(a, k)
    print(ans)

solve()

Fixed submission:
import sys
import numpy as np

from math import gcd

N = int(sys.stdin.readline())
ans = 0
"""
dp = np.zeros((N+1, N+1))
def gcd(a, b):
    if a < b:
        a, b = b, a
    
    if dp[a][b] != 0:
        return dp[a][b]

    while b>0:
        a, b = b, a % b
    
    dp[a][b] = a
    return a
"""
for i in range(1,N+1):
    for j in range(1,N+1):
        temp = gcd(i, j)
        for k in range(1,N+1):
            ans += gcd(temp, k)
            
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
N = int(sys.stdin.readline())

 if N % 2 == 0:
    print(0.5)
else:
    print(N / (2*N + 1))

Fixed submission:
import sys

N = int(sys.stdin.readline())

if N % 2 == 0:
  a = 1 / 2
else:
  a = (N+1) / (2 * N)

print('%.10f' %a)
Buggy python submission (verdict: Runtime Error):
A = sys.stdin.readline()
B = sys.stdin.readline()
ans = 0

for i in range(3):
  if A[i] == B[i]:
    ans += 1
    
print(ans)

Fixed submission:
import sys

A = sys.stdin.readline()
B = sys.stdin.readline()
ans = 0

for i in range(3):
  if A[i] == B[i]:
    ans += 1
    
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys

n = int(sys.stdin.readline())

dp = [0 for i in range(n+1)]
cost = list(map(int, sys.stdin.readline().split()))

dp[1] = cost[0]
dp[2] = abs(dp[1] - cost[2])


for i in range(3, n+1):
  dp[i] = min(dp[i-1] + abs(cost[i+1] - cost[i]), dp[i-2] + abs(cost[i-1] - cost[i+1]))
  
print(dp[n])


Fixed submission:
import sys

n = int(sys.stdin.readline())

dp = [0 for i in range(n+1)]
cost = list(map(int, sys.stdin.readline().split())) # 0~3
cost.insert(0, 0)

dp[2] = abs(cost[1] - cost[2])


for i in range(3, n+1):
  dp[i] = min(dp[i-1] + abs(cost[i-1] - cost[i]), dp[i-2] + abs(cost[i-2] - cost[i]))
  
print(dp[n])

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

n = int(sys.stdin.readline())

dp = [0 for i in range(n+1)]
cost = list(map(int, sys.stdin.readline()))

dp[1] = cost[0]
dp[2] = abs(dp[1] - cost[2])


for i in range(3, n+1):
  dp[i] = min(dp[i-1] + abs(cost[i+1] - cost[i]), dp[i-2] + abs(cost[i-1] - cost[i+1]))
  
print(dp[n])

Fixed submission:
import sys

n = int(sys.stdin.readline())

dp = [0 for i in range(n+1)]
cost = list(map(int, sys.stdin.readline().split())) # 0~3
cost.insert(0, 0)

dp[2] = abs(cost[1] - cost[2])


for i in range(3, n+1):
  dp[i] = min(dp[i-1] + abs(cost[i-1] - cost[i]), dp[i-2] + abs(cost[i-2] - cost[i]))
  
print(dp[n])

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

n = int(sys.stdin.readline())

dp = [0 for i in range(n+1)]
cost = list(map(int, sys.stdin.readline()))

dp[1] = cost[0]
dp[2] = abs(dp[1] - cost[2])


for i in range(3, n+1):
  dp[i] = min(dp[i-1] + abs(cost[i+1] - cost[i]), dp[i-2] + abs(cost[i-1] - cost[i+1])

Fixed submission:
import sys

n = int(sys.stdin.readline())

dp = [0 for i in range(n+1)]
cost = list(map(int, sys.stdin.readline().split())) # 0~3
cost.insert(0, 0)

dp[2] = abs(cost[1] - cost[2])


for i in range(3, n+1):
  dp[i] = min(dp[i-1] + abs(cost[i-1] - cost[i]), dp[i-2] + abs(cost[i-2] - cost[i]))
  
print(dp[n])
Buggy python submission (verdict: Time Limit Exceeded):
import sys

n, k = map(int, sys.stdin.readline().split())

dp = [[0 for i in range(k+1)] for j in range(n+1)]


for i in range(1,n+1):
    w, v = map(int, sys.stdin.readline().split())
    
    for j in range(0, k+1):
        if j >= w:
            dp[i][j] = max(dp[i-1][j-w] + v, dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
            
print(max(dp[-1]))

Fixed submission:
import sys
import numpy as np

n, k = map(int, sys.stdin.readline().split())

dp = np.zeros((n+1, k+1))

for i in range(1,n+1):
    w, v = map(int, sys.stdin.readline().split())
    dp[i] = dp[i-1]
    dp[i][w:] = np.maximum(dp[i-1][:-w]+v, dp[i-1][w:])

print(int(np.max(dp[n])))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

n, k = map(int, sys.stdin.readline().split())

dp = [0 for i in range(k+1)]


for i in range(n):
    w, v = map(int, sys.stdin.readline().split())
    
    temp = dp.copy()
    for j in range(k+1):
        if j+w <= k:
            dp[j+w] = max(temp[j+w], temp[j]+v)
            
print(max(dp))

Fixed submission:
import sys
import numpy as np

n, k = map(int, sys.stdin.readline().split())

dp = np.zeros((n+1, k+1))

for i in range(1,n+1):
    w, v = map(int, sys.stdin.readline().split())
    dp[i] = dp[i-1]
    dp[i][w:] = np.maximum(dp[i-1][:-w]+v, dp[i-1][w:])

print(int(np.max(dp[n])))