Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
#ABC137_C
N=int(input())
str_list=["".join(sorted(input(),reverse=True)) for _ in range(N)]
cnt=0
for _ in range(N-1):
    cnt+=str_list.count(str_list.pop(-1))
print(cnt)

Fixed submission:
#ABC137_C
from collections import Counter
N=int(input())
S=[input() for i in range(N)]

ctr=Counter()
ans=0

for s in S:
    a=''.join(sorted(list(s)))
    if a in ctr:
        ans+=ctr[a]
    ctr[a]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#ABC137_C
N=int(input())
str_list=["".join(sorted(input(),reverse=True)) for _ in range(N)]
cnt=0
for _ in range(N-1):
    cnt+=str_list.count(str_list.pop(-1))
print(cnt)

Fixed submission:
#ABC137_C
from collections import Counter
N=int(input())
S=[input() for i in range(N)]

ctr=Counter()
ans=0

for s in S:
    a=''.join(sorted(list(s)))
    if a in ctr:
        ans+=ctr[a]
    ctr[a]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
#ABC137_C
N=int(input())
ans=[]
cnt=0
for _ in range(N):
    str_list=input()
    dic={}
    for i in range(10):
        if str_list[i] in dic:
            dic[str_list[i]]+=1
        else:
            dic[str_list[i]]=1
    ans.append(dic)
while len(ans)>1: 
    cnt+=ans.count(ans.pop(0))
print(cnt) 

Fixed submission:
#ABC137_C
from collections import Counter
N=int(input())
S=[input() for i in range(N)]

ctr=Counter()
ans=0

for s in S:
    a=''.join(sorted(list(s)))
    if a in ctr:
        ans+=ctr[a]
    ctr[a]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
ans=[]
cnt=0
for _ in range(N):
    str_list=input()
    dic={}
    for i in range(10):
        if str_list[i] in dic:
            dic[str_list[i]]+=1
        else:
            dic[str_list[i]]=1
    ans.append(dic)
while len(ans)>1: 
    cnt+=ans.count(ans.pop(0))
print(cnt) 

Fixed submission:
#ABC137_C
from collections import Counter
N=int(input())
S=[input() for i in range(N)]

ctr=Counter()
ans=0

for s in S:
    a=''.join(sorted(list(s)))
    if a in ctr:
        ans+=ctr[a]
    ctr[a]+=1
print(ans)

Buggy python submission (verdict: Runtime Error):
#ABC137_C
N=int(input())
ans=[]
cnt=0
for _ in range(N):
    str_list=input()
    dic={}
    for i in range(10):
        if str_list[i] in dic:
            dic[str_list[i]]+=1
        else:
            dic[str_list[i]]=1
    ans.append(dic)
while len(ans)>1: 
    cnt+=temp=ans.count(ans.pop(0))
print(cnt) 

Fixed submission:
#ABC137_C
from collections import Counter
N=int(input())
S=[input() for i in range(N)]

ctr=Counter()
ans=0

for s in S:
    a=''.join(sorted(list(s)))
    if a in ctr:
        ans+=ctr[a]
    ctr[a]+=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#ABC132_C
N=int(input())
d=list(map(int,input().split()))

L=2
R=2*10**5


while 1:
    #print('Lis',L)
    #print('Ris',R)
    k=int((L+R)/2)
    #print('kis',k)
    ABC_num=0
    for i in range(len(d)):
        if d[i]<k:
            ABC_num+=1
    #print('ABC_num_is',ABC_num)
    if ABC_num==N/2:
        k_start=k
        break
    elif (L+1)==R:
        k_start=0
        break
    elif ABC_num<N/2:
        L=k
    else:
        R=k       
if k_start!=0:
    k=k_start+1
    while 1:
        ABC_num=0
        for i in range(len(d)):
            if d[i]<k:
                ABC_num+=1
        if ABC_num==N/2:
            k+=1
        else:
            k_r=k-1
            break
    k=k_start-1
    while 1:
        ABC_num=0
        for i in range(len(d)):
            if d[i]<k:
                ABC_num+=1
        if ABC_num==N/2:
            k-=1
        else:
            k_l=k+1
            break
    #print('k_ris',k_r)
    #print('k_lis',k_l)
    print(k_r-k_l+1)
else:
    print(0)

Fixed submission:
#ABC132_C
N=int(input())
d=list(map(int,input().split()))

d.sort()

ans=d[int(N/2)]-d[int(N/2-1)]
print(ans)
Buggy python submission (verdict: Runtime Error):
#ABC_131_C
import math

A,B,C,D=list(map(int,input().split()))


def f(A,B,X):
    if A%X==0 or B%X==0:
        X_num=1+(B-A)//X
    else:
        X_num=(B-A)//X
    return X_num


C_num=f(A,B,C)
D_num=f(A,B,D)

CD_m=C*D//math.gcd(C,D)

CD_num=f(A,B,CD_m)

ans=(B-A+1)-C_num-D_num+CD_num
print(ans)

Fixed submission:
#ABC_131_C
import fractions
A,B,C,D=list(map(int,input().split()))
#B以下の答え
CD_lcm=C*D//fractions.gcd(C,D)

underB=B-B//C-B//D+B//CD_lcm
underA_1=A-1-(A-1)//C-(A-1)//D+(A-1)//CD_lcm

print(underB-underA_1)
Buggy python submission (verdict: Time Limit Exceeded):
#ABC125_C
import fractions
from functools import reduce
 
def gcd(nums):
    return reduce(fractions.gcd,nums)
 
N=int(input())
A=list(map(int,input().split()))
ans=1
       
for i in range(N):
    temp=A.copy()
    temp.remove(temp[i])
    if gcd(temp) > ans:
        ans=gcd(temp)
print(ans)

Fixed submission:
#ABC125_C

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

def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    return gcd(x%y,y)

LCD=[A[0]]
RCD=[A[-1]]
for i in range(1,N):
    LCD.append(gcd(LCD[-1],A[i]))
    RCD.append(gcd(RCD[-1],A[-i-1]))

ans=1

if RCD[N-2]>ans:
    ans=RCD[N-2]

for i in range(1,N-1):
    if gcd(LCD[i-1],RCD[N-i-2])>ans:
        ans=gcd(LCD[i-1],RCD[N-i-2])

if LCD[N-2]>ans:
    ans=LCD[N-2]
print(ans)

Buggy python submission (verdict: Runtime Error):
#ABC125_C
import fractions
from functools import reduce
 
def gcd(nums):
    return reduce(fractions.gcd,nums)
 
N=int(input())
A=list(map(int,input().split()))
ans=1
       
for i in range(N):
    temp=A.copy()
    temp.reduce(temp[i])
    if gcd(temp) > ans:
        ans=gcd(temp)
print(ans)   

Fixed submission:
#ABC125_C

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

def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    return gcd(x%y,y)

LCD=[A[0]]
RCD=[A[-1]]
for i in range(1,N):
    LCD.append(gcd(LCD[-1],A[i]))
    RCD.append(gcd(RCD[-1],A[-i-1]))

ans=1

if RCD[N-2]>ans:
    ans=RCD[N-2]

for i in range(1,N-1):
    if gcd(LCD[i-1],RCD[N-i-2])>ans:
        ans=gcd(LCD[i-1],RCD[N-i-2])

if LCD[N-2]>ans:
    ans=LCD[N-2]
print(ans)

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

def gcd(nums):
    return reduce(fractions.gcd,nums)

N=int(input())
A=list(map(int,input().split()))
ans=1
       
for i in range(N):
       temp=A.copy()
       temp.pop(i)
       if gcd(temp) > ans:
           ans=gcd(temp)
print(ans)   

Fixed submission:
#ABC125_C

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

def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    return gcd(x%y,y)

LCD=[A[0]]
RCD=[A[-1]]
for i in range(1,N):
    LCD.append(gcd(LCD[-1],A[i]))
    RCD.append(gcd(RCD[-1],A[-i-1]))

ans=1

if RCD[N-2]>ans:
    ans=RCD[N-2]

for i in range(1,N-1):
    if gcd(LCD[i-1],RCD[N-i-2])>ans:
        ans=gcd(LCD[i-1],RCD[N-i-2])

if LCD[N-2]>ans:
    ans=LCD[N-2]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#ABC124_C
S=input()
 
S_rev=list(S)[::-1]
 
s=0
st0=0
st1=0
 
def bit_count(x):
    x=bin(x)[2:]
    ans=0
    for i in range(len(x)):
        if int(x[i])==1:
            ans+=1
    return ans
            
 
for i in range(len(S)):
    if i%2==0:
        st0+=2**i
    else:
        st1+=2**i
    if int(S_rev[i])==1:
        s+=2**i
 
cand0=st0^s
cand1=st1^s
 
    
bc0=bit_count(cand0)
bc1=bit_count(cand1)
if bc0>bc1:
    print(bc1)
else:
    print(bc0)
    

Fixed submission:
#124_C

S=input()

a=''
b=''

lenS=len(S)

for i in range(lenS):
    if i%2==0:
        a+='1'
        b+='0'
    else:
        a+='0'
        b+='1'
        
ca=0
cb=0
for i in range(lenS):
    if a[i]!=S[i]:
        ca+=1
    if b[i]!=S[i]:
        cb+=1
print(min(ca,cb))

Buggy python submission (verdict: Runtime Error):
#ABC124_C
S=input()
 
S_rev=list(S)[::-1]
 
s=0
st0=0
st1=0
 
def bit_count(x):
    x=bin(x)[2:]
    ans=0
    for i in range(len(x)):
        if int(x[i])==1:
            ans+=1
    return ans
            
 
for i in range(len(S)):
    if i%2==0:
        st0+=2**i
    else:
        st1+=2**i
    if int(S_rev[i])==1:
        s+=2**i
 
cand0=st0^s
cand1=st1^s
 
    
bc0=bit_count(cand0)
bc1=bit_count(cand1)
if bc0>bc1:
    print(bc1)
else:
    print(bc0
    

Fixed submission:
#124_C

S=input()

a=''
b=''

lenS=len(S)

for i in range(lenS):
    if i%2==0:
        a+='1'
        b+='0'
    else:
        a+='0'
        b+='1'
        
ca=0
cb=0
for i in range(lenS):
    if a[i]!=S[i]:
        ca+=1
    if b[i]!=S[i]:
        cb+=1
print(min(ca,cb))

Buggy python submission (verdict: Time Limit Exceeded):
#ABC124_C
S=input()

S_rev=list(S)[::-1]

s=0
st0=0
st1=0

def bit_count(x):
    x=bin(x)[2:]
    ans=0
    for i in range(len(x)):
        if int(x[i])==1:
            ans+=1
    return ans
            

for i in range(len(S)):
    if i%2==0:
        st0+=2**i
    else:
        st1+=2**i
    if int(S_rev[i])==1:
        s+=2**i

cand0=st0^s
cand1=st1^s

if bit_count(cand0)>bit_count(cand1):
    print(bit_count(cand1))
else:
    print(bit_count(cand0))

Fixed submission:
#124_C

S=input()

a=''
b=''

lenS=len(S)

for i in range(lenS):
    if i%2==0:
        a+='1'
        b+='0'
    else:
        a+='0'
        b+='1'
        
ca=0
cb=0
for i in range(lenS):
    if a[i]!=S[i]:
        ca+=1
    if b[i]!=S[i]:
        cb+=1
print(min(ca,cb))
Buggy python submission (verdict: Runtime Error):
#ABC122B パターン１　部分文字列全探索
S=input()
N=len(S)

ans=0
'''
for i in range(N):
    if S[i] in "ACGT":
        ans=1

for l in range(N-1):
    for r in range(l+1,N):
        for s in S[l:r]:
            if not s in "ACGT":
                break
        else:
            ans=max(ans,len(S[l:r])) 
'''

for i in range(N):
    for j in range(i,N):
        if all("ACGT".count(c)==1 if for c in S[i:j+1]):
            ans=max(ans,j-i+1)

print(ans)


Fixed submission:
#ABC122B パターン2　カウントアップMAX方式

S=input()
N=len(S)

cnt=0
ans=0
for s in S:
    if s in "ACGT":
        cnt+=1
        ans=max(ans,cnt)
    else:
        cnt=0

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#ABC122_C
N,Q=map(int,input().split())
S=input()

ls=[0]

Spre=S[0]
for i in range(1,N):
    
    Si=S[i]
    if Spre=='A' and Si=='C':
        ls.append(1)
    else:
        ls.append(0)
    Spre=Si

for i in range(Q):
    l,r=map(int,input().split())
    print(sum(ls[l:r]))





Fixed submission:
#ABC122_C
N,Q=map(int,input().split())
S=input()

ls=[0]

Spre=S[0]
for i in range(1,N):
    Si=S[i]
    if Spre=='A' and Si=='C':
        ls.append(ls[-1]+1)
    else:
        ls.append(ls[-1])
    Spre=Si
 
for i in range(Q):
    l,r=map(int,input().split())
    print(ls[r-1]-ls[l-1])
Buggy python submission (verdict: Runtime Error):
N,A,B,C=map(int,input().split())
L=[int(input()) for _ in range(N)]

#for i in range(N):
#    L.append(int(input())

ans=10**18
def cost_calc(pp,TAKEs):
    if TAKEs==[]:
        return 10**8
    
    else:
        ans=0
        ans+=(len(TAKEs)-1)*10
        ans+=abs(pp-sum(TAKEs))
        return ans

assign=[]#[A,B,C,none]

for pattern in product([0,1,2,3],repeat=N):
    MP=0
    take=[0]*3
    for index,length in zip(pattern,l):
        if index==3:
            continue
        if take[index]!=0:
            MP+=10
        take[index]+=length
    if take[0]!=0 and take[1]!=0 and take[2]!=0:
        MP+=abs(A-take[0])
        MP+=abs(B-take[1])
        MP+=abs(C-take[2])
        ans=min(MP,ans)
print(ans)

Fixed submission:
N,A,B,C=map(int,input().split())
L=[int(input()) for _ in range(N)]
from itertools import product

ans=10**18

for pattern in product(range(4),repeat=N):
    MP=0
    take=[0]*3
    for index,length in zip(pattern,L):
        if index==3:
            continue
        if take[index]!=0:
            MP+=10
        take[index]+=length
    if take[0]!=0 and take[1]!=0 and take[2]!=0:
        MP+=abs(A-take[0])
        MP+=abs(B-take[1])
        MP+=abs(C-take[2])
        ans=min(MP,ans)
print(ans)
Buggy python submission (verdict: Runtime Error):
from fractions import gcd
from functools import reduce

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

print(reduce(gcd,A))

Fixed submission:
#ABC118_C
from fractions import gcd
from functools import reduce

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

ans=reduce(gcd,A)
print(ans)

Buggy python submission (verdict: Runtime Error):
from fractions import gcd
from functools import reduce

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

print(reduce(gcd,A))

Fixed submission:
#ABC118_C
from fractions import gcd
from functools import reduce

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

ans=reduce(gcd,A)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*N
for i in range(1,N):
    dp[i]=min(
        
        dp[j]+abs(h[j]-h[i]) for j in range(max(i-K,0),i)

        )


print(dp[N-1])


Fixed submission:
def main():
    N,K=map(int,input().split())
    h=list(map(int,input().split()))
    dp=[0]*N
    for i in range(1,N):
        dp[i]=min(
            
            dp[j]+abs(h[j]-h[i]) for j in range(max(i-K,0),i)
            )
    print(dp[N-1])
main()
Buggy python submission (verdict: Time Limit Exceeded):
#EDPC D

#dp[ i ][ sum_w ] := i-1 番目までの品物から重さが 
# sum_w以下となるときの、価値の総和の最大値

#dpのindexはややこしくなりがち

N,W=map(int,input().split())
w,v=[0],[0]#w,vのindexと品物の番号を合わせるため、頭に0を追加

for _ in range(N):
    wi,vi=map(int,input().split())
    w.append(wi)
    v.append(vi)

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


for i in range(N):
    for sum_w in range(1,W+1):
        if sum_w-w[i+1]>=0:
            dp[i+1][sum_w]=max(dp[i][sum_w-w[i+1]]+v[i+1],dp[i][sum_w])
        else:
            dp[i+1][sum_w]=dp[i][sum_w]

print(dp[N][W])

Fixed submission:
#EDPC D

#dp[ i ][ sum_w ] := i-1 番目までの品物から重さが 
# sum_w以下となるときの、価値の総和の最大値

#dpのindexはややこしくなりがち

N,W=map(int,input().split())
w,v=[0],[0]#w,vのindexと品物の番号を合わせるため、頭に0を追加
def main():
  for _ in range(N):
      wi,vi=map(int,input().split())
      w.append(wi)
      v.append(vi)

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


  for i in range(N):
      for sum_w in range(1,W+1):
          if sum_w-w[i+1]>=0:
              dp[i+1][sum_w]=max(dp[i][sum_w-w[i+1]]+v[i+1],dp[i][sum_w])
          else:
              dp[i+1][sum_w]=dp[i][sum_w]

  print(dp[N][W])
main()

Buggy python submission (verdict: Time Limit Exceeded):
#EDPC D

#dp[ i ][ sum_w ] := i-1 番目までの品物から重さが 
# sum_w以下となるときの、価値の総和の最大値

#dpのindexはややこしくなりがち

N,W=map(int,input().split())
w,v=[0],[0]#w,vのindexと品物の番号を合わせるため、頭に0を追加

for _ in range(N):
    wi,vi=map(int,input().split())
    w.append(wi)
    v.append(vi)

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


for i in range(N):
    for sum_w in range(1,W+1):
        if sum_w-w[i+1]>=0:
            dp[i+1][sum_w]=max(dp[i][sum_w-w[i+1]]+v[i+1],dp[i][sum_w])
        else:
            dp[i+1][sum_w]=dp[i][sum_w]

print(dp[N][W])

Fixed submission:
#EDPC D

#dp[ i ][ sum_w ] := i-1 番目までの品物から重さが 
# sum_w以下となるときの、価値の総和の最大値

#dpのindexはややこしくなりがち

N,W=map(int,input().split())
w,v=[0],[0]#w,vのindexと品物の番号を合わせるため、頭に0を追加
def main():
  for _ in range(N):
      wi,vi=map(int,input().split())
      w.append(wi)
      v.append(vi)

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


  for i in range(N):
      for sum_w in range(1,W+1):
          if sum_w-w[i+1]>=0:
              dp[i+1][sum_w]=max(dp[i][sum_w-w[i+1]]+v[i+1],dp[i][sum_w])
          else:
              dp[i+1][sum_w]=dp[i][sum_w]

  print(dp[N][W])
main()
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
G=[[] for _ in range(N)]
for _ in  range(M):
    xi,yi=map(int,input().split())
    G[xi-1].append(yi-1)

dp=[-1]*(N+1) #各ノードを始点とした時の最長経路

def rec(v):
    if dp[v]!=-1:
        return dp[v]
    
    res=0

    for nv in G[v]:
        res=max(res,rec(nv)+1)
    
    dp[v]=res
    return res

ans=0
for v in range(N):
    ans=max(ans,rec(v))
print(ans)

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

N,M=map(int,input().split())
G=[[] for _ in range(N)]
for _ in  range(M):
    xi,yi=map(int,input().split())
    G[xi-1].append(yi-1)

dp=[-1]*N #各ノードを始点とした時の最長経路

def rec(v):
    if dp[v]!=-1:
        return dp[v]
    
    res=0

    for nv in G[v]:
        res=max(res,rec(nv)+1)
    
    dp[v]=res
    return res

ans=0
for v in range(N):
    ans=max(ans,rec(v))
print(ans)

Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
G=[[] for _ in range(N)]
for _ in  range(M):
    xi,yi=map(int,input().split())
    G[xi-1].append(yi-1)

dp=[-1]*N #各ノードを始点とした時の最長経路

def rec(v):
    if dp[v]!=-1:
        return dp[v]
    
    res=0

    for nv in G[v]:
        res=max(res,rec(nv)+1)
    
    dp[v]=res
    return res

ans=0
for v in range(N):
    ans=max(ans,rec(v))
print(ans)


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

N,M=map(int,input().split())
G=[[] for _ in range(N)]
for _ in  range(M):
    xi,yi=map(int,input().split())
    G[xi-1].append(yi-1)

dp=[-1]*N #各ノードを始点とした時の最長経路

def rec(v):
    if dp[v]!=-1:
        return dp[v]
    
    res=0

    for nv in G[v]:
        res=max(res,rec(nv)+1)
    
    dp[v]=res
    return res

ans=0
for v in range(N):
    ans=max(ans,rec(v))
print(ans)

Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())

G=[[] for _ in range(N)]
for _ in  range(M):
    xi,yi=map(int,input().split())
    G[xi-1].appedn(yi-1)

dp=[-1]*N #各ノードを始点とした時の最長経路

def rec(v):
    if dp[v]!=-1:
        return dp[v]
    
    res=0

    for nv in G[v]:
        res=max(res,rec(nv)+1)
    
    dp[v]=res
    return res

ans=0
for v in range(N):
    ans=max(ans,rec(v))
print(ans)


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

N,M=map(int,input().split())
G=[[] for _ in range(N)]
for _ in  range(M):
    xi,yi=map(int,input().split())
    G[xi-1].append(yi-1)

dp=[-1]*N #各ノードを始点とした時の最長経路

def rec(v):
    if dp[v]!=-1:
        return dp[v]
    
    res=0

    for nv in G[v]:
        res=max(res,rec(nv)+1)
    
    dp[v]=res
    return res

ans=0
for v in range(N):
    ans=max(ans,rec(v))
print(ans)
Buggy python submission (verdict: Runtime Error):
H,W=map(int,input().split())
#G=[[-1 if input() else 0 for i in range(W)] for _ in range(H)]

'''リストver
dp=[[-1]*W for _ in range(H)]
for i in range(H):
    s=input()
    for j in range(W):
        if s[j]=='#':
            dp[i][j]=0
dp[0][0]=1
'''

#numpy ver
import numpy as np
dp=np.array([list(input()) for _ in range(H)])

dp=np.where(dp=='.',-1,dp)
dp=np.where(dp=='#',0,dp)

dp=dp.astype(int)
dp[0][0]=1

for i in range(H):
    for j in range(W):
        if dp[i][j]==-1:
            if i>0 and j>0:
                dp[i][j]=dp[i-1][j]+dp[i][j-1]
            elif i>=1 and j==0:
                dp[i][j]=dp[i-1][j]
            elif i==0 and j>=1:
                dp[i][j]=dp[i][j-1]

print(dp[H-1][W-1])

Fixed submission:
H,W=map(int,input().split())
#G=[[-1 if input() else 0 for i in range(W)] for _ in range(H)]
MOD=10**9+7
#リストver
dp=[[-1]*W for _ in range(H)]
for i in range(H):
    s=input()
    for j in range(W):
        if s[j]=='#':
            dp[i][j]=0
dp[0][0]=1

'''
#numpy ver
import numpy as np
dp=np.array([list(input()) for _ in range(H)])

dp=np.where(dp=='.',-1,dp)
dp=np.where(dp=='#',0,dp)

dp[0][0]=1
'''
for i in range(H):
    for j in range(W):
        if dp[i][j]==-1:
            if i>0 and j>0:
                dp[i][j]=dp[i-1][j]+dp[i][j-1]
            elif i>=1 and j==0:
                dp[i][j]=dp[i-1][j]
            elif i==0 and j>=1:
                dp[i][j]=dp[i][j-1]

print(dp[H-1][W-1]%MOD)
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
H=list(map(int,input().split()))
H.sort()
ans=10**6

for i in range(N-K):
    ans=min(ans,H[i]-H[i+K])

print(ans)    

Fixed submission:
N,K=map(int,input().split())
H=[int(input()) for _ in range(N)]
H.sort(reverse=True)
ans=10**9

for i in range(N-K+1):
    ans=min(ans,H[i]-H[i+K-1])

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
def dfs(s): # 文字列 s で始まる七五三数の個数 
if int(s) > N:
	return 0
ret = 1 if all(s.count(c) > 0 for c in '753') else 0 # s 自体が七五三数なら +1 
for c in '753':
  ret += dfs(s + c)
  return ret
print(dfs('0')) # 本当は dfs('') と書きたいが 4 行目でのエラーを防ぐため仕方なく


Fixed submission:
n=int(input())
 
def dfs(s):
  if int(s)>n:
    return 0
  cnt=1 if all(s.count(i)>0 for i in '753') else 0
  for j in '753':
    cnt+=dfs(s+j)
  return cnt
  
print(dfs('0'))

Buggy python submission (verdict: Runtime Error):
N = int(input())
def dfs(s): # 文字列 s で始まる七五三数の個数 if int(s) > N:
return 0
ret = 1 if all(s.count(c) > 0 for c in '753') else 0 # s 自体が七五三数なら +1 for c in '753':
         ret += dfs(s + c)
     return ret
print(dfs('0')) # 本当は dfs('') と書きたいが 4 行目でのエラーを防ぐため仕方なく


Fixed submission:
n=int(input())
 
def dfs(s):
  if int(s)>n:
    return 0
  cnt=1 if all(s.count(i)>0 for i in '753') else 0
  for j in '753':
    cnt+=dfs(s+j)
  return cnt
  
print(dfs('0'))
Buggy python submission (verdict: Runtime Error):
#111
from collections import Counter
n=int(input())
v=list(map(int,input().split()))
L=list(Counter(v[0::2]).items())
R=list(Counter(v[1::2]).items())


if L[0][0]!=R[0][0]:#再頻出の数がRとLで同一ではない場合
    ans=n-L[0][1]-R[0][1]
elif len(R)!=1 and len(L)!=1:
    ans=n-max(L[0][1]+R[1][1],L[1][1]+R[0][1])
elif len(R)!=1 and len(L)==1:
    ans=n-R[1][1]-L[0][1]
elif len(R)==1 and len(L)!=1:
    ans=n-R[0][1]-L[1][1]
elif : len(R)==1 and len(L)==1:
    ans=n//2
print(ans)    


Fixed submission:
#111
from collections import Counter
n=int(input())
v=list(map(int,input().split()))

c0=Counter(v[0::2]).most_common()
c1=Counter(v[1::2]).most_common()

if c0[0][0]!=c1[0][0]:#再頻出の数がRとLで同一ではない場合
    ans=n-c0[0][1]-c1[0][1]
elif len(c0)!=1 and len(c1)!=1:
    ans=n-max(c0[0][1]+c1[1][1],c0[1][1]+c1[0][1])
elif len(c0)!=1 and len(c1)==1:
    ans=n-c0[1][1]-c1[0][1]
elif len(c0)==1 and len(c1)!=1:
    ans=n-c0[0][1]-c1[1][1]
elif len(c0)==1 and len(c1)==1:
    ans=n//2
print(ans)

Buggy python submission (verdict: Runtime Error):
#112
from itertools import product

N=int(input())
px=[]
py=[]
ph=[]

for _ in range(N):
    x,y,h=map(int,input().split())
    if h!=0:
        px.append(x)
        py.append(y)
        ph.append(h)


        
def Calc_H(Cxi,Cyj,pxi,pyj,hi):
    return hi+abs(Cxi-pxi)+abs(Cyj-pyj)

    
    
for Cxi,Cyj in product(range(101),range(101)):
    preH=Calc_H(Cxi,Cyj,px[0],py[0],ph[0])
    for i in range(1,N):
        nowH=Calc_H(Cxi,Cyj,px[i],py[i],ph[i])
        if preH!=nowH:
            break
        preH=nowH
    else:
        print(Cxi,Cyj,nowH)

Fixed submission:
#111
from collections import Counter
n=int(input())
v=list(map(int,input().split()))

c0=Counter(v[0::2]).most_common()
c1=Counter(v[1::2]).most_common()

if c0[0][0]!=c1[0][0]:#再頻出の数がRとLで同一ではない場合
    ans=n-c0[0][1]-c1[0][1]
elif len(c0)!=1 and len(c1)!=1:
    ans=n-max(c0[0][1]+c1[1][1],c0[1][1]+c1[0][1])
elif len(c0)!=1 and len(c1)==1:
    ans=n-c0[1][1]-c1[0][1]
elif len(c0)==1 and len(c1)!=1:
    ans=n-c0[0][1]-c1[1][1]
elif len(c0)==1 and len(c1)==1:
    ans=n//2
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import Counter

S=input()
T=input()

S=Counter(S).values()
T=Counter(T).values()

S.sort()
T.sort()

if S==T:
    print('Yes')
else:
    print('No')


Fixed submission:
from collections import Counter

S=input()
T=input()

S=list(Counter(S).values())
T=list(Counter(T).values())

S.sort()
T.sort()

if S==T:
  print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
from fractions import gcd
from functools import reduce

N,X=map(int,input().split())
ls=[]

for _ in range(N):
    ls.append(abs(int(input())-X))

print(reduce(gcd,ls))


Fixed submission:
from fractions import gcd
from functools import reduce

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

def int_X(x):
    return abs(int(x)-X)

ls=list(map(int_X,input().split()))

print(reduce(gcd,ls))

Buggy python submission (verdict: Runtime Error):
from fractions import gcd
from functools import reduce

N,X=map(int,input().split())
ls=[abs(int(input())-X) for _ in range(N)]

print(reduce(gcd,ls))


Fixed submission:
from fractions import gcd
from functools import reduce

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

def int_X(x):
    return abs(int(x)-X)

ls=list(map(int_X,input().split()))

print(reduce(gcd,ls))