Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import deque

n, q = map(int, input().split())

g = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)

c = [0] * n

for j in range(q):
    p, x = map(int, input().split())
    c[p - 1] += x

used = [0] * n
used[0] = 1

def dfs(x):
    cost=c[x]
    for nx in g[x]:
        if used[nx]:
            continue
        used[nx]=1
        c[nx]+=cost
        dfs(nx)
dfs(0)
print(*c)

Fixed submission:
from collections import deque

n,q=map(int,input().split())

g=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)



c=[0]*n

for j in range(q):
    p,x=map(int,input().split())
    c[p-1]+=x

used=[0]*n
used[0]=1
next=deque([0])

while next:
    v=next.popleft()
    cost=c[v]
    for nv in g[v]:
        if used[nv]:
            continue
        used[nv]=1
        next.append(nv)
        c[nv]+=cost

print(*c)

Buggy python submission (verdict: Runtime Error):
n,q=map(int,input().split())
X=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    X[a-1].append(b-1)

C=[0]*n

def dfs(p,x):
    C[p]+=x
    for i in X[p]:
        dfs(i,x)


for i in range(q):
    p,x=map(int,input().split())
    dfs(p-1,x)

print(*C)

Fixed submission:
from collections import deque

n,q=map(int,input().split())

g=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)



c=[0]*n

for j in range(q):
    p,x=map(int,input().split())
    c[p-1]+=x

used=[0]*n
used[0]=1
next=deque([0])

while next:
    v=next.popleft()
    cost=c[v]
    for nv in g[v]:
        if used[nv]:
            continue
        used[nv]=1
        next.append(nv)
        c[nv]+=cost

print(*c)
Buggy python submission (verdict: Runtime Error):
import heapq

n,m=map(int,input().split())
X=[[] for _ in range(m)]
for i in range(n):
    a,b=map(int,input().split())
    X[a-1].append(-b)

ans=0
p=[]
heapq.heapify(p)
for i in range(m):
    if len(p)==0 and len(X[i])==0:
        continue
    for j in range(len(X[i])):
        heapq.heappush(p,X[i][j])
    a=heapq.heappop(p)
    ans+=a*-1
print(ans)

Fixed submission:
import heapq

n,m=map(int,input().split())
X=[[] for _ in range(10**5+5)]
for i in range(n):
    a,b=map(int,input().split())
    X[a-1].append(-b)

ans=0
p=[]
heapq.heapify(p)
for i in range(m):
    if len(p)==0 and len(X[i])==0:
        continue
    for j in range(len(X[i])):
        heapq.heappush(p,X[i][j])
    a=heapq.heappop(p)
    ans+=a*-1
print(ans)

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

n,m=map(int,input().split())
X=[]
for i in range(n):
    a,b=map(int,input().split())
    X.append([a,-b])
Y=sorted(X,key=lambda x:(x[0]))
ans=0
c=0
x=[0]*n
heapq.heapify(x)
flag=True
for i in range(1,m+1):
    if flag:
        while Y[c][0]<=i:
            heapq.heappush(x,Y[c][1])
            c+=1
            if c==len(Y):
                flag=False
                break
    ans+=heapq.heappop(x)*(-1)
print(ans)

Fixed submission:
import heapq

n,m=map(int,input().split())
X=[[] for _ in range(10**5+5)]
for i in range(n):
    a,b=map(int,input().split())
    X[a-1].append(-b)

ans=0
p=[]
heapq.heapify(p)
for i in range(m):
    if len(p)==0 and len(X[i])==0:
        continue
    for j in range(len(X[i])):
        heapq.heappush(p,X[i][j])
    a=heapq.heappop(p)
    ans+=a*-1
print(ans)
Buggy python submission (verdict: Runtime Error):
from math import factorial

MOD=10**9+7
n,k=map(int,input().split())
 
blue=1
red=n-k+1


def modpow(x,p,MOD):
    if p==1:
        return x%MOD
    if p>=2:
        if p%2==0:
            p//=2
            return modpow(x,p,MOD)**2%MOD
        else:
            p-=1
            return x*modpow(x,p,MOD)%MOD
 
for i in range(k):
    red=factorial(k-1)*modpow(factorial(i),MOD-2,MOD)*modpow(factorial(k-i-1),MOD-2,MOD)%MOD
    blue=factorial(n-k+1)*modpow(factorial(i+1),MOD-2,MOD)*modpow(factorial(n-k-i),MOD-2,MOD)%MOD
    print(red*blue)

Fixed submission:
from math import factorial

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

def f(n,k):
    return factorial(n)//(factorial(k)*(factorial(abs(n-k))))

for i in range(k):
    print(f(n-k+1,i+1)*f(k-1,i)%(10**9+7))
Buggy python submission (verdict: Runtime Error):
import math
a,b,c,d=map(int,input().split())
a-=1
y=int(c*d/math.gcd(c,d))

p=a-((a//c)+(a//d)-(a//y))

q=b-((b//c)+(b//d)-(b//y))

print(int(q-p))

Fixed submission:
import fractions
a,b,c,d=map(int,input().split())
a-=1
y=int(c*d/fractions.gcd(c,d))

p=a-((a//c)+(a//d)-(a//y))

q=b-((b//c)+(b//d)-(b//y))

print(int(q-p))
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
n=int(input())
M=[]
for i in range(n):
    x,y=map(int,input().split())
    M.append([x,y])
M.sort(key=lambda x:(x[0],x[1]))
X=defaultdict(int)
for i in range(n-1):
    for j in range(i+1,n):
        a=M[i][0]-M[j][0]
        b=M[i][1]-M[j][1]
        X[(a,b)]+=1
print(n-max(X.values()))

Fixed submission:
n=int(input())
M=[]
for i in range(n):
    x,y=map(int,input().split())
    M.append([x,y])
M.sort(key=lambda x:(x[0],x[1]))
X=[]
Y=[]
for i in range(n-1):
    for j in range(i+1,n):
        a=M[i][0]-M[j][0]
        b=M[i][1]-M[j][1]
        if not [a,b] in Y:
            Y.append([a,b])
            X.append(1)
        else:
            X[Y.index([a,b])]+=1
ans=n
for i in range(len(Y)):
    ans=min(ans,n-X[i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=list(int(input()) for i in range(m))
x=[0]*(n+1)
x[0]=1
for i in range(1,n+1):
    x[i]=(x[i-1]+x[i-2])%(10**9+7)
    if i in a:
        x[i]=0
print(x[n])

Fixed submission:
n,m=map(int,input().split())
A=set(int(input()) for i in range(m))
 
x=[0]*(n+1)
x[0]=1
if 1 in A:
    x[1]=0
else:
    x[1]=1
 
for j in range(2,n+1):
    if j in A:
        x[j]=0
    else:
        x[j]=(x[j-1]+x[j-2])%(10**9+7)
        
 
print(x[n])

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)
x[0]=1
if 1 in A:
    x[1]=0
else:
    x[1]=1

for j in range(2,n+1):
    if j in A:
        x[j]=0
    else:
        x[j]=(x[j-1]+x[j-2])%(10**9+7)
        

print(x[n])
    

Fixed submission:
n,m=map(int,input().split())
A=set(int(input()) for i in range(m))
 
x=[0]*(n+1)
x[0]=1
if 1 in A:
    x[1]=0
else:
    x[1]=1
 
for j in range(2,n+1):
    if j in A:
        x[j]=0
    else:
        x[j]=(x[j-1]+x[j-2])%(10**9+7)
        
 
print(x[n])

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)
x[0]=1
if 1 in A:
    x[1]=0
else:
    x[1]=1

for j in range(2,n+1):
    if j in A:
        x[j]=0
    else:
        x[j]=x[j-1]+x[j-2]
        x[j]=x[j]%1000000007

print(x[n])
    

Fixed submission:
n,m=map(int,input().split())
A=set(int(input()) for i in range(m))
 
x=[0]*(n+1)
x[0]=1
if 1 in A:
    x[1]=0
else:
    x[1]=1
 
for j in range(2,n+1):
    if j in A:
        x[j]=0
    else:
        x[j]=(x[j-1]+x[j-2])%(10**9+7)
        
 
print(x[n])

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)
x[0]=1
if 1 in A:
    x[1]=0
else:
    x[1]=1

for j in range(2,n+1):
    if j in A:
        x[j]=0
    else:
        x[j]=x[j-1]+x[j-2]

print(x[n]%1000000007)

Fixed submission:
n,m=map(int,input().split())
A=set(int(input()) for i in range(m))
 
x=[0]*(n+1)
x[0]=1
if 1 in A:
    x[1]=0
else:
    x[1]=1
 
for j in range(2,n+1):
    if j in A:
        x[j]=0
    else:
        x[j]=(x[j-1]+x[j-2])%(10**9+7)
        
 
print(x[n])
Buggy python submission (verdict: Time Limit Exceeded):
L=input()
l=len(L)
ans=3**(l-1)
a=L.count('1')
cnt=1
for i in range(1,l):
    if L[i]=='1':
        ans+=(2**(cnt))*(3**(l-i-1))%(10**9+7)
        cnt+=1
        
print((ans+2**a)%(10**9+7))

Fixed submission:
mod=10**9+7

L=input()
l=len(L)
ans=3**(l-1)
a=L.count('1')
cnt=1

for i in range(1,l):
    if L[i]=='1':
        ans+=pow(2,cnt,mod)*pow(3,l-i-1,mod)
        cnt+=1
        
print((ans+pow(2,a,mod))%mod)

Buggy python submission (verdict: Time Limit Exceeded):
L=input()
l=len(L)
ans=3**(l-1)
a=L.count('1')
cnt=1
for i in range(1,l):
    if L[i]=='1':
        ans+=(2**(cnt))*(3**(l-i-1))%(10**9+7)
        cnt+=1
        
print((ans+2**a)%(10**9+7))

Fixed submission:
mod=10**9+7

L=input()
l=len(L)
ans=3**(l-1)
a=L.count('1')
cnt=1

for i in range(1,l):
    if L[i]=='1':
        ans+=pow(2,cnt,mod)*pow(3,l-i-1,mod)
        cnt+=1
        
print((ans+pow(2,a,mod))%mod)

Buggy python submission (verdict: Time Limit Exceeded):
L=input()
l=len(L)
ans=3**(l-1)
a=L.count('1')
cnt=1
for i in range(1,l):
    if L[i]=='1':
        ans+=(2**(cnt))*(3**(l-i-1))
        cnt+=1
        
print((ans+2**a)%(10**9+7))

Fixed submission:
mod=10**9+7

L=input()
l=len(L)
ans=3**(l-1)
a=L.count('1')
cnt=1

for i in range(1,l):
    if L[i]=='1':
        ans+=pow(2,cnt,mod)*pow(3,l-i-1,mod)
        cnt+=1
        
print((ans+pow(2,a,mod))%mod)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
x=[]
for i in range(m):
    b,c=map(int,input().split())
    x.append([b,c])
y=sorted(x,key=lambda x:(x[1],x[0]),reverse=True)

d=[]
for i in range(m):
    d.extend([y[i][1]]*y[i][0])

for i in range(n):
    if len(d)<=i:
        break
    if d[i]>a[i]:
        a[i]=d[i]
    else:
        break
print(sum(a))

Fixed submission:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
x=[]
for i in range(m):
    b,c=map(int,input().split())
    x.append([b,c])
y=sorted(x,key=lambda x:(x[1],x[0]),reverse=True)

p=0
q=0
for i in range(n):
    if a[i]<y[p][1]:
        a[i]=y[p][1]
        q+=1
    else:
        break
    if q==y[p][0]:
        p+=1
        q=0
        if p==m:
            break

print(sum(a))

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
x=[]
for i in range(m):
    b,c=map(int,input().split())
    x.append([b,c])
y=sorted(x,key=lambda x:(x[1],x[0]),reverse=True)

d=[]
for i in range(m):
    d.extend([y[i][1]]*y[i][0])

for i in range(n):
    if d[i]>a[i]:
        a[i]=d[i]
    else:
        break
print(sum(a))

Fixed submission:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
x=[]
for i in range(m):
    b,c=map(int,input().split())
    x.append([b,c])
y=sorted(x,key=lambda x:(x[1],x[0]),reverse=True)

p=0
q=0
for i in range(n):
    if a[i]<y[p][1]:
        a[i]=y[p][1]
        q+=1
    else:
        break
    if q==y[p][0]:
        p+=1
        q=0
        if p==m:
            break

print(sum(a))
Buggy python submission (verdict: Runtime Error):
from collections import deque
n=int(input())
X=[[] for _ in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    X[u-1].append([v-1,w])
    X[v-1].append([u-1,w])
C=[0]*n
q=deque([])
for i in range(len(X[0])):
    q.append([X[0][i]])
visited=[0]*n

while q:
    v,w=q.popleft()
    if visited[v]==1:
        continue
    visited[v]=1
    if w%2==0:
        C[v]=C[u]
    else:
        if C[u]==0:
            C[v]=1
        else:
            C[v]=0
    for pv,pw in X[v]:
        q.append([pv,pw])

for c in C:
    print(c)

Fixed submission:
from collections import deque
n=int(input())
X=[[] for _ in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    X[u-1].append([v-1,w])
    X[v-1].append([u-1,w])
C=[0]*n
q=deque([])
for v,w in X[0]:
    q.append([v,w])
visited=[0]*n

while q:
    v,w=q.popleft()

    if visited[v]==1:
        continue
    visited[v]=1
    if w%2==0:
        C[v]=0
    else:
        C[v]=1
    for pv,pw in X[v]:
        q.append([pv,pw+w])

for c in C:
    print(c)
Buggy python submission (verdict: Runtime Error):
s=input()
res=0
for i in range(len(s)+1):
    for j in range(i+1,len(s)+1):
       
        if set(list(s[i:j]))|{'A','G','C','T'}=={'A','G','C','T'}:
            cnt=len(s[i:j])
        if res<cnt:
            res=cnt

print(res)

Fixed submission:
s=input()

res=0
for i in range(len(s)+1):
    for j in range(i+1,len(s)+1):
        cnt=0
        for x in s[i:j]:
            if x not in ['A','G','C','T']:
                break
            cnt+=1
        if res<cnt:
            res=cnt

print(res)

Buggy python submission (verdict: Runtime Error):
s=input()
res=0
for i in range(len(s)+1):
    for j in range(i+1,len(s)+1):
        print(list(s[i:j]))
        if set(list(s[i:j]))|{'A','G','C','T'}=={'A','G','C','T'}:
            cnt=len(s[i:j])
        if res<cnt:
            res=cnt

print(res)

Fixed submission:
s=input()

res=0
for i in range(len(s)+1):
    for j in range(i+1,len(s)+1):
        cnt=0
        for x in s[i:j]:
            if x not in ['A','G','C','T']:
                break
            cnt+=1
        if res<cnt:
            res=cnt

print(res)

Buggy python submission (verdict: Runtime Error):
s=input()
res=0
for i in range(len(s)):
    for j in range(i+1,len(s)):
        if set(list(s[i:j]))|{'A','G','C','T'}=={'A','G','C','T'}:
            cnt=len(s[i:j])
        if res<cnt:
            res=cnt

print(res)

Fixed submission:
s=input()

res=0
for i in range(len(s)+1):
    for j in range(i+1,len(s)+1):
        cnt=0
        for x in s[i:j]:
            if x not in ['A','G','C','T']:
                break
            cnt+=1
        if res<cnt:
            res=cnt

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
from _collections import defaultdict
from itertools import combinations
n=int(input())
S=input()
X=defaultdict(int)
for s in S:
    X[s]+=1
A=0
for i in range(1,len(X.keys())+1):
    for comb in combinations(X.keys(),i):
        ans=1
        for c in comb:
            ans*=X[c]
        A+=ans
print(A%(10**9+7))

Fixed submission:
from _collections import defaultdict
n=int(input())
S=input()
X=defaultdict(int)
for s in S:
    X[s]+=1
ans=1
for v in X.values():
    ans*=(v+1)
print((ans-1)%(10**9+7))
Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())

for i in range(50):
    if a>=2**i and a<2**(i+1):
        A=i+1
    if b>=2**i and b<2**(i+1):
        B=i+1

N=[0]*B

for i in range(a,2**A):
    X=format(i,'b')
    for j in range(-1,-A-1,-1):
        N[j]+=int(X[j])
    
for i in range(2**(B-1),b+1):
    Y=format(i,'b')
    for j in range(B):
        N[j]+=int(Y[j])
ans=0
for i in range(B):
    if N[i]%2==1:
        ans+=2**(B-i-1)
print(ans)

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

if a%2==0:
    fa=(a//2)%2
else:
    fa=(((a-1)//2)%2)^(a-1)

if b%2==0:
    fb=((b//2)%2)^b
else:
    fb=((b+1)//2)%2
    
print(fb^fa)
Buggy python submission (verdict: Runtime Error):
s=input()

x='10'
y='01'

def hoge(s):
    if x in s or y in s:
        for i in range(len(s)-1):
            if s[i]+s[i+1]==x or s[i]+s[i+1]==y:
                s=s[:i]+s[i+2:]
                
                return hoge(s)+2
    else:
        return 0

print(hoge(s))

Fixed submission:
s=input()

x=s.count('1')
y=s.count('0')

a=max(x,y)
b=min(x,y)

print(len(s)-(a-b))
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
par=[-1]*n
def find(n):
    if par[n]<0:
        return n
    else:
        par[n]=find(par[n])
        return par[n]
def union(x,y):
    x,y=find(x),find(y) 
    if x!=y:
        if x>y:
            x,y=y,x
        par[x]+=par[y]
        par[y]=x
M=[]
for i in range(m):
    a,b=map(int,input().split())
    M.append([a,b])
ANS=[n*(n-1)//2]
for i in reversed(range(1,m)):
    s=n*(n-1)//2
    a,b=M[i][0],M[i][1]
    union(a-1,b-1)
    for i in range(n):
        if par[i]<-1:
            s-=par[i]*(par[i]+1)//2
    ANS.append(s)
for ans in ANS[::-1]:
    print(ans)

Fixed submission:
n,m=map(int,input().split())
par=[-1]*n
def find(n):
    if par[n]<0:
        return n
    else:
        par[n]=find(par[n])
        return par[n]
def union(x,y,s):
    x,y=find(x),find(y) 
    if x!=y:
        if x>y:
            x,y=y,x
        s-=par[x]*par[y]
        par[x]+=par[y]
        par[y]=x
    return s
        
M=[]
for i in range(m):
    a,b=map(int,input().split())
    M.append([a,b])
ANS=[n*(n-1)//2]
s=n*(n-1)//2
for i in reversed(range(1,m)):
    a,b=M[i][0],M[i][1]
    s=union(a-1,b-1,s)
    ANS.append(s)
for ans in ANS[::-1]:
    print(ans)
Buggy python submission (verdict: Runtime Error):
import math
n=int(input())
X=list(map(int,input().split()))
x=X[0]
for i in range(1,n):
    x=math.gcd(x,X[i])

if x!=1:
    print(x)
else:
    print(1)

Fixed submission:
n=int(input())
X=list(map(int,input().split()))
x=X[0]
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a


for i in range(1,n):
    x=gcd(x,X[i])
if x!=1:
    print(x)
else:
    print(1)

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

n=int(input())

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



def amari(a,b):
    x=max(a,b)
    y=min(a,b)
    return x%y

while len(X)>1:
    Y=list(itertools.combinations(X,2))
    Z=[]
    for i in range(len(Y)):
        z=amari(Y[i][0],Y[i][1])
        if z>0:
            Z.append(z)
    X=list(set(Z))
    
print(X[0])

Fixed submission:
n=int(input())
X=list(map(int,input().split()))
x=X[0]
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a


for i in range(1,n):
    x=gcd(x,X[i])
if x!=1:
    print(x)
else:
    print(1)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())

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

X.sort()

C=[]
for i in range(m-1):
    c=abs(X[i+1]-X[i])
    C.append(c)

C.sort()

sum_c=0
for  j in range(n+1):
    sum_c+=C[j]
    
print(sum_c)

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

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

X.sort()

C=[]
for i in range(m-1):
    c=abs(X[i+1]-X[i])
    C.append(c)

if(n>=m):
    print(0)
else:
    C.sort()
    sum_c=0
    for j in range(len(C)-n+1):
        sum_c+=C[j]
    print(sum_c)
Buggy python submission (verdict: Runtime Error):
a,b,c=map(int,input().split())

x=[a,b,c]

x.sort()

print(x[0]*x[1]/2]

Fixed submission:
a,b,c=map(int,input().split())
 
x=[a,b,c]
 
x.sort()
 
print(int(x[0]*x[1]/2))
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())

x=[]
for i in range(n):
    x.append(int(input()))

x.sort()

y=[]

for j in range(n):
  p=x[j+k-1]-x[j]
  y.append(p)

y.sort()

print(y[0])

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

x=[]
for i in range(n):
    x.append(int(input()))

x.sort()

y=[]

for j in range(n-k+1):
  p=x[j+k-1]-x[j]
  y.append(p)

y.sort()

print(y[0])
Buggy python submission (verdict: Time Limit Exceeded):
n=input()

count=0
for j in range(1,int(n)+1):
    X=[]
    X=[int(x) for x in list(str(j))]
    if set(X)=={3,5,7}:
        count+=1
        
print(count)
    

Fixed submission:
n=int(input())


L=[3,5,7]

def dfs(s):
    count=0
    for i in L:
        p=s*10+i
        if p<=n:
            if set([int(j) for j in str(p)])==set(L):
                count+=dfs(p)+1 #条件を満たしているので+1
            else:
                count+=dfs(p)
    return count

print(dfs(0))

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

count=0
for j in range(1,int(n)+1):
    X=[]
    str_j=str(j)
    for k in range(len(str_j)):
        X.append(int(str_j[k]))
    if set(X)=={3,5,7}:
        count+=1
        
print(count)

Fixed submission:
n=int(input())


L=[3,5,7]

def dfs(s):
    count=0
    for i in L:
        p=s*10+i
        if p<=n:
            if set([int(j) for j in str(p)])==set(L):
                count+=dfs(p)+1 #条件を満たしているので+1
            else:
                count+=dfs(p)
    return count

print(dfs(0))
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())

X=[]
S=[]
for _ in range(m):
    x=list(map(int,input().split()))
    X.append(x)

   
for i in range(m):
    first_num="000000"
    last_num="000000"
    
    chushutsu_list=[j for j in X if j[0]==X[i][0]]
    chushutsu_list.sort(key=lambda x:x[1])
    
    count=chushutsu_list.index(X[i])+1
    
    
    first_num=first_num[:6-len(str(X[i][0]))]+str(X[i][0])
    last_num=last_num[:6-len(str(count))]+str(count)
    print(first_num+last_num)

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

X=[]

for i in range(m):
    a=i
    b,c=map(int,input().split())
    X.append([a,b,c])

sort_X=sorted(X,key=lambda x:(x[1],x[2]))
sort_X[0].append(1)

for i in range(1,m):
    if sort_X[i][1]!=sort_X[i-1][1]:
        sort_X[i].append(1)
    else:
        sort_X[i].append(sort_X[i-1][3]+1)
   
X=sorted(sort_X,key=lambda x:x[0])
for i in range(m):
    count=X[i][3]
    first_num="000000"
    last_num="000000"
    
    
    first_num=first_num[:6-len(str(X[i][1]))]+str(X[i][1])
    last_num=last_num[:6-len(str(count))]+str(count)
    print(first_num+last_num)
Buggy python submission (verdict: Runtime Error):
N,M = map(int, input().split())
L = []
 
for i in range(1,(M**0.5)+1):
    if M % i == 0:
        L.append(i)
        L.append(int(M / i))
L1 = [i for i in L if M / i >= N]
print(max(L1))

Fixed submission:
N,M = map(int, input().split())
L = []
 
for i in range(1,int(M**0.5)+1):
    if M % i == 0:
        L.append(i)
        L.append(int(M / i))
L1 = [i for i in L if M / i >= N]
print(max(L1))

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
res=0
for i in range(m//n+1)[::-1]:
    if m%i==0:
        res=i
        break

print(res)

Fixed submission:
N,M = map(int, input().split())
L = []
 
for i in range(1,int(M**0.5)+1):
    if M % i == 0:
        L.append(i)
        L.append(int(M / i))
L1 = [i for i in L if M / i >= N]
print(max(L1))

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

if m%n==0:
    print(int(m/n))
else:
    for i in range(n+1,m+1):
        if m%i==0:
            print(int(m/i))
            break

Fixed submission:
N,M = map(int, input().split())
L = []
 
for i in range(1,int(M**0.5)+1):
    if M % i == 0:
        L.append(i)
        L.append(int(M / i))
L1 = [i for i in L if M / i >= N]
print(max(L1))
Buggy python submission (verdict: Runtime Error):
import collections

n=int(input())


X=list(map(int,input().split()))
odd=[]
even=[]
for i in range(int(n/2)):
    odd.append(X[2*i+1])
    even.append(X[2*i])

odd_counter=collections.Counter(odd) #登場回数とその値の辞書型
even_counter=collections.Counter(even)

odd_count=sorted(odd_counter.values(),reverse=True) #登場回数の多い順に並べた配列
even_count=sorted(even_counter.values(),reverse=True)

max_odd_value=max(odd_counter,key=odd_counter.get) #登場回数が最大の値
max_even_value=max(even_counter,key=even_counter.get)

if max_odd_value!=max_even_value:
    print(n-odd_count[0]-even_count[0])

else:
    print(min(n-odd_count[0]-even_count[1],n-odd_count[1]-even_count[0]))

Fixed submission:
import collections

n=int(input())


X=list(map(int,input().split()))
odd=[]
even=[]
for i in range(int(n/2)):
    odd.append(X[2*i+1])
    even.append(X[2*i])

odd_counter=collections.Counter(odd) #登場回数とその値の辞書型
even_counter=collections.Counter(even)

odd_count=sorted(odd_counter.values(),reverse=True) #登場回数の多い順に並べた配列
even_count=sorted(even_counter.values(),reverse=True)

max_odd_value=max(odd_counter,key=odd_counter.get) #登場回数が最大の値
max_even_value=max(even_counter,key=even_counter.get)

if max_odd_value!=max_even_value:
    print(n-odd_count[0]-even_count[0])
elif len(set(odd))!=1 and len(set(even))!=1:
    print(min(n-odd_count[0]-even_count[1],n-odd_count[1]-even_count[0]))
elif len(set(odd))==1 and len(set(even))==1:
    print(int(n/2))
elif len(set(odd))==1:
    print(int(n/2)-even_count[1])
elif len(set(even))==1:
    print(int(n/2)-odd_count[1])
Buggy python submission (verdict: Time Limit Exceeded):
n,x=map(int,input().split())

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

X.append(x)

X.sort()

dif=[]
for i in range(n):
    dif.append(X[i+1]-X[i])

for j in range(max(dif),0,-1):
    if all(x%j==0  for x  in dif):
        print(j)
        break

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

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

dif=[]
for i in range(n):
    dif.append(abs(X[i]-x))

def gcd(a,b):
    a,b=max(a,b),min(a,b)
    if b>0:
        return gcd(b,a%b)
    else:
        return a

ans=dif[0]
for i in range(1,n):
    ans=gcd(ans,dif[i])

    
    
print(ans)