Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
from itertools import combinations as cmb
n=int(input())
s=set(input())
combiset=set(cmb(s,3))
print(len(combiset))

Fixed submission:
m,d=map(int,input().split(" "))
mm,dd=map(int,input().split(" "))
if m==mm:print(0)
else:print(1)

Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
from itertools import combinations as cmb
n=int(input())
s=list(input())
sss=[]
for i in s:
    sss.append(i)
combiset=set(cmb(sss,3))
print(len(combiset))

Fixed submission:
m,d=map(int,input().split(" "))
mm,dd=map(int,input().split(" "))
if m==mm:print(0)
else:print(1)

Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline

n=int(input())
s=input()
dp=[[[False]*1000 for j in range(4)] for i in range(n+1)]

dp[0][0][0]=True

for i in range(n):
    for j in range(4):
        for k in range(1000):
            if dp[i][j][k]==False:continue
            dp[i+1][j][k]=True
            if j<=2:
                dp[i+1][j+1][k*10+int(s[i])]=True
cnt=0
for i in range(1000):
    if dp[n][3][i]==1:cnt+=1
print(cnt)

Fixed submission:
m,d=map(int,input().split(" "))
mm,dd=map(int,input().split(" "))
if m==mm:print(0)
else:print(1)

Buggy python submission (verdict: Runtime Error):
# 動的計画法

n=int(input())
s=input()
dp=[[[False for k in range(1000)] for j in range(4)] for i in range(n+1)]

dp[0][0][0]=True

for i in range(n):
    for j in range(4):
        for k in range(1000):
            if dp[i][j][k]==False:continue
            dp[i+1][j][k]=True
            if j<=2:
                dp[i+1][j+1][k*10+int(s[i])]=True
cnt=0
for i in range(1000):
    if dp[n][3][i]==True:cnt+=1
print(cnt)

Fixed submission:
m,d=map(int,input().split(" "))
mm,dd=map(int,input().split(" "))
if m==mm:print(0)
else:print(1)

Buggy python submission (verdict: Runtime Error):
n=int(input())
s=input()
dp=[[[False for k in range(1000)] for j in range(4)] for i in range(n+1)]

dp[0][0][0]=True

for i in range(n):
    for j in range(4):
        for k in range(1000):
            if dp[i][j][k]==False:continue
            print(i,j,k)
            dp[i+1][j][k]=True
            print(i+1,j,k,i,j,k)
            if j<=2:
                dp[i+1][j+1][k*10+int(s[i])]=True
                print(i+1,j+1,k*10+int(s[i]),i,j,k)
cnt=0
for i in range(1000):
    if dp[n][3][i]==True:cnt+=1
print(cnt)

Fixed submission:
m,d=map(int,input().split(" "))
mm,dd=map(int,input().split(" "))
if m==mm:print(0)
else:print(1)
Buggy python submission (verdict: Runtime Error):
a,b,x=map(int,input().split())
def binary_search(start,end):
    if end-start<=1:return start
    else:
        i=(start+end)//2
        s = a * (i) + b * len(str(i))
        if s<=x:return binary_search(i,end)
        else:return binary_search(start,i)
print(binary_search(0,10**9+1))

Fixed submission:
S=input()
if S=="SUN":print("7")
if S=="MON":print("6")
if S=="TUE":print("5")
if S=="WED":print("4")
if S=="THU":print("3")
if S=="FRI":print("2")
if S=="SAT":print("1")
Buggy python submission (verdict: Runtime Error):
n=int(input())
ans=n
i=1
while(i<math.sqrt(n)):
    if n%i==0:
        d=i+n/i-2
        ans=min(ans,d)
    i+=1
print(int(ans))

Fixed submission:
import math
n=int(input())
ans=n
i=1
while(i<=math.sqrt(n)):
    if n%i==0:
        d=i+n/i-2
        ans=min(ans,d)
    i+=1
print(int(ans))
Buggy python submission (verdict: Runtime Error):
import bisect
n=int(input())
L=[]*n
L=list(map(int,input().split()))
L.sort()
cnt=0
for i in range(n-2):
    for j in range(i+1,n-1):
        ab=L[i]+L[j]
        num=bisect.bisect_left(L[j+1:],ab)
        cnt+=num
print(cnt)

Fixed submission:
A,B = map(int,input().split(" "))
print(max(A-B*2,0))
Buggy python submission (verdict: Runtime Error):
N = input()
D=[]*N
D=map(int,input().split(" "))
sum=0
for i,di in enumerate(D):
    for j,jd in enumerate(D):
        if i!=j:
            sum+=jd*id
print(sum)

Fixed submission:
import itertools
N = int(input())
D=[]*N
D=map(int,input().split(" "))
sum=0
for i,j in itertools.permutations(D,2):
    sum+=i*j

print(int(sum/2))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n=int(input())
L=[]*n
L=list(map(int,input().split()))
L.sort()
cnt=0
for i in range(n-2):
    for j in range(i+1,n-1):
        ab=L[i]+L[j]
        num=bisect.bisect_left(L[j+1:],ab)
        cnt+=num
print(cnt)

Fixed submission:
import bisect
n=int(input())
L=[]*n
L=list(map(int,input().split()))
L.sort()
cnt=0
for i in range(n-1):
    for j in range(i+1,n):
        ab=L[i]+L[j]
        num=bisect.bisect_left(L[j+1:],ab)
        cnt+=num
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n=int(input())
L=[]*n
L=list(map(int,input().split()))
L.sort()
cnt=0
for i in range(n-1):
    for j in range(i+1,n):
        ab=L[i]+L[j]
        num=bisect.bisect_left(L[j+1:],ab)
        cnt+=num
print(cnt)

Fixed submission:
import bisect
n=int(input())
L=[]*n
L=list(map(int,input().split()))
L.sort()
cnt=0
for i in range(n-1):
    for j in range(i+1,n):
        ab=L[i]+L[j]
        num=bisect.bisect_left(L[j+1:],ab)
        cnt+=num
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
N = int(input())
L=[]*N
L=map(int,input().split(" "))
ans=0
for a,b,c in itertools.combinations(L,3):
    if (a<b+c) & (b<c+a) & (c<a+b):ans+=1
print(ans)

Fixed submission:
import bisect
n=int(input())
L=[]*n
L=list(map(int,input().split()))
L.sort()
cnt=0
for i in range(n-1):
    for j in range(i+1,n):
        ab=L[i]+L[j]
        num=bisect.bisect_left(L[j+1:],ab)
        cnt+=num
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
N = int(input())
L=[]*N
L=map(int,input().split(" "))
ans=0
for a,b,c in itertools.combinations(L,3):
    if (a<b+c) & (b<c+a) & (c<a+b):ans+=1
print(ans)

Fixed submission:
import bisect
n=int(input())
L=[]*n
L=list(map(int,input().split()))
L.sort()
cnt=0
for i in range(n-1):
    for j in range(i+1,n):
        ab=L[i]+L[j]
        num=bisect.bisect_left(L[j+1:],ab)
        cnt+=num
print(cnt)
Buggy python submission (verdict: Runtime Error):
S = input()
K = int(input())
cnt = 0
for i in range(len(S)):
    if (S[i]==S[i+1])&(S[i]!=S[i-1]):
        cnt += K
print(cnt)


Fixed submission:
s=input()
k=int(input())
l=len(s)
now=1
seq=[]
re=False
all=False
for i in range(l):
    if s[i%l]==s[(i+1)%l]:
        if i==l-1:
            re=True
            if len(seq)==0:
                all=True
            else:
                first=seq[0]//2
                end=now//2
                seq[0]=(seq[0]+now)
        now+=1
    else:
        seq.append(now)
        now=1
if all:
    ans=len(s)*k//2
else:
    seq=[i//2 for i in seq]
    if re:
        ans=sum(seq)*k-seq[0]+first+end
    else:
        ans=sum(seq)*k

print(ans)

Buggy python submission (verdict: Runtime Error):
S = input()
K = int(input())
cnt = 0
for i in range(len(S)-1):
    if (S[i]==S[i+1])&&(S[i-1]!=S[i]):
        cnt += K
print(cnt)

Fixed submission:
s=input()
k=int(input())
l=len(s)
now=1
seq=[]
re=False
all=False
for i in range(l):
    if s[i%l]==s[(i+1)%l]:
        if i==l-1:
            re=True
            if len(seq)==0:
                all=True
            else:
                first=seq[0]//2
                end=now//2
                seq[0]=(seq[0]+now)
        now+=1
    else:
        seq.append(now)
        now=1
if all:
    ans=len(s)*k//2
else:
    seq=[i//2 for i in seq]
    if re:
        ans=sum(seq)*k-seq[0]+first+end
    else:
        ans=sum(seq)*k

print(ans)

Buggy python submission (verdict: Runtime Error):
S = input()
K = int(input())
cnt = 0
for i in range(len(S)-1):
    if S[i]==S[i+1]&&S[i-1]!=S[i]:
        cnt += K
print(cnt)

Fixed submission:
s=input()
k=int(input())
l=len(s)
now=1
seq=[]
re=False
all=False
for i in range(l):
    if s[i%l]==s[(i+1)%l]:
        if i==l-1:
            re=True
            if len(seq)==0:
                all=True
            else:
                first=seq[0]//2
                end=now//2
                seq[0]=(seq[0]+now)
        now+=1
    else:
        seq.append(now)
        now=1
if all:
    ans=len(s)*k//2
else:
    seq=[i//2 for i in seq]
    if re:
        ans=sum(seq)*k-seq[0]+first+end
    else:
        ans=sum(seq)*k

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

n=int(input())
x=[]
y=[]
for i in range(n):
    xx,yy=list(map(int,input().split()))
    x.append(xx)
    y.append(yy)

dif=defaultdict(int)

for i in range(n):
    for j in range(n):
        if i==j:continue
        p=x[j]-x[i]
        q=y[j]-y[i]
        dif[(p,q)]+=1

dif=sorted(dif.items(),key=lambda x:x[1],reverse=True)
ans=n-dif[0][1]

print(ans)

Fixed submission:
from collections import defaultdict

n=int(input())
if n==1:
    print(1)
    exit()
x=[]
y=[]
for i in range(n):
    xx,yy=list(map(int,input().split()))
    x.append(xx)
    y.append(yy)

dif=defaultdict(int)

for i in range(n):
    for j in range(n):
        if i==j:continue
        p=x[j]-x[i]
        q=y[j]-y[i]
        dif[(p,q)]+=1

dif=sorted(dif.items(),key=lambda x:x[1],reverse=True)
ans=n-dif[0][1]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
m=len(s)-1
idx=[0 for i in range(m)]

for i in range(m):
    if s[i]=="A" and s[i+1]=="C":idx[i]=1
ans=[]
for i in range(q):
    l,r=map(int,input().split())
    ans.append(sum(idx[l-1:r-1]))

for i in ans:
    print(i)

Fixed submission:
n,q=map(int,input().split())
s=input()
idx=[0 for i in range(n+1)]

for i in range(n-1):
    if s[i:i+2]=="AC":idx[i+1]=idx[i]+1
    else:idx[i+1]=idx[i]

ans=[]
for i in range(q):
    l,r=map(int,input().split())
    print(idx[r-1]-idx[l-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
s=input()
t=input()

from fractions import gcd
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

long=lcm([n,m])

ln=int(long/n)
lm=int(long/m)

ans=[]
ok=True
for i in range(long):
    an=i%ln
    am=i%lm
    kn=i//ln
    km=i//lm
    if (an==0)&(am==0):
        if s[kn]==t[km]:
            ans.append(s[kn])
        else:ok=False
    elif an==0:
        ans.append(s[kn])
    elif am==0:
        ans.append(t[km])
    else:
        ans.append("a")
lll=len(ans)
if not ok:
    lll=-1

print(lll)

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

from fractions import gcd
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

long=lcm([n,m])

ln=int(long/n)
lm=int(long/m)

#ans=[]

ok=True

for i in range(n-1):
    if (i*ln)%lm==0:
        if s[i]!=t[(i*ln)//lm]:
            ok=False

if n==1:
    if s!=t[0]:ok=False
if m==1:
    if t!=s[0]:ok=False

if not ok:long=-1

print(long)
Buggy python submission (verdict: Runtime Error):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

lis=make_divisors(m)

for mm in lis:
    if mm<=i:
        ans=mm
        break

print(ans)

Fixed submission:
# 解説AC

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

i=m//n

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

lis=make_divisors(m)

for mm in lis:
    if mm<=i:
        ans=mm
        break

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def inv_gcd(a,b):
    a=a%b
    if a==0:
        return (b,0)
    s=b;t=a
    m0=0;m1=1
    while(t):
        u=s//t
        s-=t*u
        m0-=m1*u
        s,t=t,s
        m0,m1=m1,m0
    if m0<0:
        m0+=b//s
    return (s,m0)
def inv_mod(x,m):
    assert 1<=m
    z=inv_gcd(x,m)
    assert z[0]==1
    return z[1]
def crt(r,m):
    assert len(r)==len(m)
    n=len(r)
    r0=0;m0=1
    for i in range(n):
        assert 1<=m[i]
        r1=r[i]%m[i]
        m1=m[i]
        if m0<m1:
            r0,r1=r1,r0
            m0,m1=m1,m0
        if (m0%m1==0):
            if (r0%m1!=r1):
                return (0,0)
            continue
        g,im=inv_gcd(m0,m1)
        u1=m1//g
        if ((r1-r0)%g):
            return (0,0)
        x=(r1-r0)//g % u1*im%u1
        r0+=x*m0
        m0*=u1
        if r0<0:
            r0+=m0
    return (r0,m0)
N=int(input())
def divide(n):
    res=[]
    i=1
    while(i*i<=n):
        if n%i==0:
            res.append(i)
            if i*i!=n:
                res.append(n//i)
        i+=1
    return res
ans=2*N
for b in divide(2*N):
    c=(2*N)//b
    tmp=crt([0,c-1],[b,c])
    if tmp==(0,0):
        continue
    x=tmp[0]
    if x==0:
        x=tmp[1]
    ans=min(x,ans)
print(ans)


Fixed submission:
def inv_gcd(a,b):
    a=a%b
    if a==0:
        return (b,0)
    s=b;t=a
    m0=0;m1=1
    while(t):
        u=s//t
        s-=t*u
        m0-=m1*u
        s,t=t,s
        m0,m1=m1,m0
    if m0<0:
        m0+=b//s
    return (s,m0)
def inv_mod(x,m):
    assert 1<=m
    z=inv_gcd(x,m)
    assert z[0]==1
    return z[1]
def crt(r,m):
    assert len(r)==len(m)
    n=len(r)
    r0=0;m0=1
    for i in range(n):
        assert 1<=m[i]
        r1=r[i]%m[i]
        m1=m[i]
        if m0<m1:
            r0,r1=r1,r0
            m0,m1=m1,m0
        if (m0%m1==0):
            if (r0%m1!=r1):
                return (0,0)
            continue
        g,im=inv_gcd(m0,m1)
        u1=m1//g
        if ((r1-r0)%g):
            return (0,0)
        x=(r1-r0)//g % u1*im%u1
        r0+=x*m0
        m0*=u1
        if r0<0:
            r0+=m0
    return (r0,m0)
N=int(input())
def divide(n):
    res=[]
    i=1
    while(i*i<=n):
        if n%i==0:
            res.append(i)
            if i*i!=n:
                res.append(n//i)
        i+=1
    return res
ans=2*N
for b in divide(2*N):
    c=(2*N)//b
    tmp=crt([0,c-1],[b,c])
    if tmp==(0,0):
        continue
    x=tmp[0]
    if x==0:
        x=tmp[1]
    ans=min(x,ans)
print(ans)
Buggy python submission (verdict: Runtime Error):
N,X,M=map(int,input().split())
dist=[0 for i in range(M)]
A=X
loopin=-1
loopout=-1
ans=[0]
for i in range(N+1):
    if dist[A]!=0:
        loopin=dist[A]
        loopout=i
        ans.append(ans[-1]+A)
        break
    else:
        dist[A]=i
        ans.append(ans[-1]+A)
        A=(A*A)%M
if loopin==-1:
    print(ans[N])
#print(roopin,roopout)
#print(ans)
A=X
loop=loopout-loopin
def solve(l,r):
    assert 0<=l and l<=r
    if r<=loopout:
        return ans[r]-ans[l]
    if l<loopin:
        return ans[loopin]-ans[l]+solve(loopin,r)
    x=(l-loopin)//loop
    y=(r-loopin)//loop
    #x*loop+loopin<=l<(x+1)*loop+loopin
    #y*loop+loopin<=r<(y+1)*loop+loopin
    if x==y:
        return ans[r-y*loop]-ans[l-x*loop]
    #以降はx<y
    tmp1=ans[l-x*loop]-ans[loopin]
    tmp2=(ans[loopout]-ans[loopin])*(y-x)
    tmp3=ans[r-y*loop]-ans[loopin]
    #print(l,r,x,y,tmp1,tmp2,tmp3)
    return tmp1+tmp2+tmp3
print(solve(0,N))


Fixed submission:
N,X,M=map(int,input().split())
dist=[0 for i in range(M)]
A=X
loopin=-1
loopout=-1
ans=[0]
for i in range(N+1):
    if dist[A]!=0:
        loopin=dist[A]
        loopout=i
        ans.append(ans[-1]+A)
        break
    else:
        dist[A]=i
        ans.append(ans[-1]+A)
        A=(A*A)%M
if loopin==-1:
    print(ans[N])
    exit()
#print(roopin,roopout)
#print(ans)
A=X
loop=loopout-loopin
def solve(l,r):
    assert 0<=l and l<=r
    if r<=loopout:
        return ans[r]-ans[l]
    if l<loopin:
        return ans[loopin]-ans[l]+solve(loopin,r)
    x=(l-loopin)//loop
    y=(r-loopin)//loop
    #x*loop+loopin<=l<(x+1)*loop+loopin
    #y*loop+loopin<=r<(y+1)*loop+loopin
    if x==y:
        return ans[r-y*loop]-ans[l-x*loop]
    #以降はx<y
    tmp1=ans[l-x*loop]-ans[loopin]
    tmp2=(ans[loopout]-ans[loopin])*(y-x)
    tmp3=ans[r-y*loop]-ans[loopin]
    #print(l,r,x,y,tmp1,tmp2,tmp3)
    return tmp1+tmp2+tmp3
print(solve(0,N))
Buggy python submission (verdict: Time Limit Exceeded):
class fenwick_tree():
    n=1
    data=[0 for i in range(n)]
    def __init__(self,N):
        self.n=N
        self.data=[0 for i in range(N)]
    def add(self,p,x):
        assert 0<=p<self.n,"0<=p<n,p={0},n={1}".format(p,self.n)
        p+=1
        while(p<=self.n):
            self.data[p-1]+=x
            p+=p& -p
    def sum(self,l,r):
        assert (0<=l and l<=r and r<=self.n),"0<=l<=r<=n,l={0},r={1},n={2}".format(l,r,self.n)
        return self.sum0(r)-self.sum0(l)
    def sum0(self,r):
        s=0
        while(r>0):
            s+=self.data[r-1]
            r-=r&-r
        return s

N,Q=map(int,input().split())
a=[int(i) for i in input().split()]
FT=fenwick_tree(N)
for i in range(N):
    FT.add(i,a[i])
for i in range(Q):
    t,a,b=map(int,input().split())
    if t==0:
        FT.add(a,b)
    else:
        print(FT.sum(a,b))


Fixed submission:
class fenwick_tree():
    n=1
    data=[0 for i in range(n)]
    def __init__(self,N):
        self.n=N
        self.data=[0 for i in range(N)]
    def add(self,p,x):
        assert 0<=p<self.n,"0<=p<n,p={0},n={1}".format(p,self.n)
        p+=1
        while(p<=self.n):
            self.data[p-1]+=x
            p+=p& -p
    def sum(self,l,r):
        assert (0<=l and l<=r and r<=self.n),"0<=l<=r<=n,l={0},r={1},n={2}".format(l,r,self.n)
        return self.sum0(r)-self.sum0(l)
    def sum0(self,r):
        s=0
        while(r>0):
            s+=self.data[r-1]
            r-=r&-r
        return s

N,Q=map(int,input().split())
a=[int(i) for i in input().split()]
FT=fenwick_tree(N)
for i in range(N):
    FT.add(i,a[i])
for i in range(Q):
    t,a,b=map(int,input().split())
    if t==0:
        FT.add(a,b)
    else:
        print(FT.sum(a,b))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N=int(input())
P=10**9+7
a=[int(i) for i in input().split()]
b=[0 for i in range(P)]
for i in range(N):
    b[a[i]]+=1
M=1<<19
c=np.zeros(M)
for i in range(P-1):
    c[i]=b[pow(2,i,P)]
X=[int(i+0.1) for i in np.real(np.fft.ifft(np.fft.fft(c)*np.fft.fft(c)))]
ans=0
for k in range(M):
    ans+=X[k]*pow(2,k,P)
for i in range(N):
    ans-=(a[i]*a[i])%P
print((ans//2)%P)


Fixed submission:
N=int(input())
a=[int(i) for i in input().split()]
mod=10**9+7
S=sum(a)%mod
T=sum([i*i for i in a])%mod
print((pow(2,mod-2,mod)*(S*S-T))%mod)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
Ch-=1;Cw-=1;Dh-=1;Dw-=1
C=(Ch,Cw)
D=(Dh,Dw)
S=[list(input()) for i in range(H)]
dist=[[10**15 for j in range(W)] for i in range(H)]
dist[Ch][Cw]=0
q=deque([C])
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while(len(q)>0):
    x,y=q.popleft()
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=nx<H and 0<=ny<W:
            if S[nx][ny]=="#":
                continue
            if dist[nx][ny]>dist[x][y]:
                dist[nx][ny]=dist[x][y]
                q.appendleft((nx,ny))
    for i in range(-2,3):
        for j in range(-2,3):
            nx=x+i
            ny=y+j
            if 0<=nx<H and 0<=ny<W:
                if S[nx][ny]=="#":
                    continue
                if dist[nx][ny]>dist[x][y]+1:
                    dist[nx][ny]=dist[x][y]+1
                    q.append((nx,ny))
if dist[Dh][Dw]==10**15:
    print(-1)
else:
    print(dist[Dh][Dw])


Fixed submission:
from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
Ch-=1;Cw-=1;Dh-=1;Dw-=1
C=(Ch,Cw)
D=(Dh,Dw)
S=[list(input()) for i in range(H)]
dist=[[10**15 for j in range(W)] for i in range(H)]
dist[Ch][Cw]=0
q=deque([C])
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while(len(q)>0):
    x,y=q.popleft()
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=nx<H and 0<=ny<W:
            if S[nx][ny]=="#":
                continue
            if dist[nx][ny]>dist[x][y]:
                dist[nx][ny]=dist[x][y]
                q.appendleft((nx,ny))
    for i in range(-2,3):
        for j in range(-2,3):
            nx=x+i
            ny=y+j
            if 0<=nx<H and 0<=ny<W:
                if S[nx][ny]=="#":
                    continue
                if dist[nx][ny]>dist[x][y]+1:
                    dist[nx][ny]=dist[x][y]+1
                    q.append((nx,ny))
if dist[Dh][Dw]==10**15:
    print(-1)
else:
    print(dist[Dh][Dw])
Buggy python submission (verdict: Runtime Error):
#https://qiita.com/sage-git/items/90c342fd2127ec39b874
import numpy as np
M=int(input())
P=200003
a=[int(i) for i in input().split()]
b=[0 for i in range(P)]
for i in range(M):
    b[a[i]]+=1
c=[0 for i in range(P-1)]
tmp=1
for i in range(P-1):
    c[i]=b[tmp]
    tmp=tmp*2
    tmp%=P
N = P-1
n0 = 2**int(np.ceil(np.log2(2*N - 1)))

A = np.zeros(n0)
B = np.zeros(n0)
for i in range(N):
    A[i],B[i]=c[i],c[i]

C = np.fft.ifft( np.fft.fft(A)*np.fft.fft(B) )

ret = [int(ci) for ci in np.real(C[:2*N - 1] + 0.5)]
ans=0
for k in range(2*N-1):
    ans+=ret[k]*pow(2,k,P)
for i in range(M):
    ans-=(a[i]*a[i])%P
print(ans//2)


Fixed submission:
#https://qiita.com/sage-git/items/90c342fd2127ec39b874
import numpy as np
M=int(input())
P=200003
a=[int(i) for i in input().split()]
b=[0 for i in range(P)]
for i in range(M):
    b[a[i]]+=1
c=[0 for i in range(P-1)]
tmp=1
for i in range(P-1):
    c[i]=b[tmp]
    tmp=tmp*2
    tmp%=P
N = P-1
n0 = 2**int(np.ceil(np.log2(2*N - 1)))

A = np.zeros(n0)
B = np.zeros(n0)
for i in range(N):
    A[i],B[i]=c[i],c[i]

C = np.fft.ifft( np.fft.fft(A)*np.fft.fft(B) )

ret = [int(ci) for ci in np.real(C[:2*N - 1] + 0.5)]
ans=0
for k in range(2*N-1):
    ans+=ret[k]*pow(2,k,P)
for i in range(M):
    ans-=(a[i]*a[i])%P
print(ans//2)
Buggy python submission (verdict: Runtime Error):
def popcount(n):
    return str(bin(n)).count('1')
def f(n):
    if n==0:
        return 0
    else:
        return f(n%popcount(n))+1
N=int(input())
X=input()
K=X.count("1")
#k桁目がone,zeroのとき
ONE=0#K-1
ZERO=0#K+1
tmp1=1
tmp0=1
for i in range(N):
    if X[-i-1]=="1":
        ONE+=tmp1
        ONE%=(K-1)
        ZERO+=tmp0
        ZERO%=(K+1)
    tmp1*=2
    tmp1%=(K-1)
    tmp0*=2
    tmp0%=(K+1)
for i in range(N):
    nextnumber=-1
    if X[i]=="1":
        nextnumber=(ONE-pow(2,N-i-1,K-1))%(K-1)
    else:
        nextnumber=(ZERO+pow(2,N-i-1,K+1))%(K+1)
    print(f(nextnumber)+1)


Fixed submission:
def popcount(n):
    return str(bin(n)).count('1')
def f(n):
    if n==0:
        return 0
    else:
        return f(n%popcount(n))+1
N=int(input())
X=input()
K=X.count("1")
#k桁目がone,zeroのとき
ONE=0#K-1
ZERO=0#K+1
tmp1=1
tmp0=1
for i in range(N):
    if X[-i-1]=="1":
        if K>1:
            ONE+=tmp1
            ONE%=(K-1)
        ZERO+=tmp0
        ZERO%=(K+1)
    if K>1:
        tmp1*=2
        tmp1%=(K-1)
    tmp0*=2
    tmp0%=(K+1)
for i in range(N):
    nextnumber=-1
    if X[i]=="1":
        if K==1:
            print(0)
            continue
        else:
            nextnumber=(ONE-pow(2,N-i-1,K-1))%(K-1)
    else:
        nextnumber=(ZERO+pow(2,N-i-1,K+1))%(K+1)
    print(f(nextnumber)+1)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
ans=0
for i in range(1,N+1):
    for j in range(i,N+1,i):
        ans+=j
print(ans)


Fixed submission:
N=int(input())
#sum[k:1 to N]floor(N/K)
ans=0
j=1
while(j*(j*1)<=N):
    b=1+(N//j)
    a=1+(N//(j+1))
    tmp=((N//a)*((N//a)+1))//2
    tmpa=(a*(a-1))//2
    tmpb=(b*(b-1))//2
    ans+=(tmpb-tmpa)*tmp
    j+=1
for i in range(1,a):
    ans+=i*((N//i)*((N//i)+1))//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
K=int(input())
S=input()
mod=10**9+7
def inv(x):
    return pow(x,mod-2,mod)
N=len(S)
ans=0
tmp1=1
tmp2=1
for i in range(0,K+1):
    ans=ans+(tmp1*tmp2)
    ans%=mod
    tmp1=tmp1*25
    tmp1%=mod
    tmp2=tmp2*(inv(i+1)*(N+K-i))
    tmp2%=mod
    #print(tmp1,tmp2)
print(ans)

Fixed submission:
K=int(input())
S=input()
mod=10**9+7
def inv(x):
    return pow(x,mod-2,mod)
N=len(S)
ans=0
tmp1=1
tmp2=1
for i in range(0,K+1):
    ans=ans+(tmp1*tmp2)
    ans%=mod
    tmp1=tmp1*25
    tmp1%=mod
    tmp2=tmp2*(inv(i+1)*(N+K-i))
    tmp2%=mod
    #print(tmp1,tmp2)
print(ans)