Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
        m.append(-aa)
        if cntp+cntm<K:
            cntm+=1
    
    if aa==0:
        zero=True

ans=1

if cntm%2==1:
    if cntm+1<=len(m) and cntm+1<=K and cntp+1<=len(p) and cntp+1<=K:
        if p[cntp]*p[cntp-1]>m[cntm]*m[cntm-1]:
            cntp+=1
            cntm-=1
        else:
            cntp+=1
            cntm-=1
    elif cntm+1<=len(m) and cntm+1<=K:
        cntm+=1
        cntp-=1
    elif cntp+1<=len(p) and cntp+1<=K:
        cntp+=1
        cntm-=1
    else:
        if zero:
            print(0)
            exit(0)
        
        for i in range(K):
            ans*=a[N-i-1]
            ans=(ans+mod*mod)%mod
        
        print(ans)
        exit(0)

for i in range(cntm):
    ans*=m[i]
    ans%=mod
for i in range(cntp):
    ans*=p[i]
    ans%=mod

print(ans)

Fixed submission:
N,K=list(map(int,input().split()))
a=list(map(int,input().split()))
a.sort(key=lambda x:abs(x),reverse=True)

mod=10**9+7

p=[]
m=[]
zero=False
cntm=0
cntp=0

for aa in a:
    if aa>=0:
        p.append(aa)
        if cntp+cntm<K:
            cntp+=1
    elif aa<0:
        m.append(-aa)
        if cntp+cntm<K:
            cntm+=1
    
    if aa==0:
        zero=True

ans=1

if cntm%2==1:
    if cntm+1<=len(m) and cntm+1<=K and cntp+1<=len(p) and cntp+1<=K:
        if p[cntp]*p[cntp-1]>m[cntm]*m[cntm-1]:
            cntp+=1
            cntm-=1
        else:
            cntm+=1
            cntp-=1
    elif cntm+1<=len(m) and cntm+1<=K:
        cntm+=1
        cntp-=1
    elif cntp+1<=len(p) and cntp+1<=K:
        cntp+=1
        cntm-=1
    else:
        if zero:
            print(0)
            exit(0)
        
        for i in range(K):
            ans*=a[N-i-1]
            ans=(ans+mod*mod)%mod
        
        print(ans)
        exit(0)

for i in range(cntm):
    ans*=m[i]
    ans%=mod
for i in range(cntp):
    ans*=p[i]
    ans%=mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())

is_prime = [True] * (N + 1)
is_prime[0] = False
is_prime[1] = False
min_prime=[i for i in range(N+1)]

for i in range(2, int(N**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, N + 1, i):
        is_prime[j] = False
        min_prime[j]=min_prime[i]

ans=0

for i in range(1,N+1):
    j=i
    dic={}
    while j>1:
        if min_prime[j] in dic:
            dic[min_prime[j]]+=1
        else:
            dic[min_prime[j]]=1
        
        j//=min_prime[j]
    
    cnt=1
    for d in dic.values():
        cnt*=(d+1)
    
    ans+=i*cnt

print(ans)

Fixed submission:
N=int(input())

ans=0
for i in range(1,N+1):
    ans+=(N//i+1)*i*(N//i)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
a=list(map(int,input().split()))
ans=[['']*30 for _ in range(N)]

if sum(a)==0:
    print(' '.join(['0']*N))
    exit(0)

i=29

while True:
    curbit=[aa%2 for aa in a]

    s=sum(curbit)

    if s==0:
        break

    if s%2==0:
        for j in range(N):
            ans[j][i]=str(curbit[j])
    else:
        for j in range(N):
            ans[j][i]=str(0 if curbit[j] else 1)



    a=[aa//2 for aa in a]
    i-=1

print(' '.join([str(int(''.join(aa),2)) for aa in ans]))

Fixed submission:
N=int(input())
a=list(map(int,input().split()))
ans=[[0]*30 for _ in range(N)]

if sum(a)==0:
    print(' '.join(['0']*N))
    exit(0)

i=29

while i>=0:
    curbit=[aa%2 for aa in a]

    s=sum(curbit)

    if s%2==0:
        for j in range(N):
            ans[j][i]=curbit[j]
    else:
        for j in range(N):
            ans[j][i]=0 if curbit[j] else 1



    a=[aa//2 for aa in a]
    
    i-=1

print(' '.join([str(int(''.join([str(aaa) for aaa in aa]),2)) for aa in ans]))

Buggy python submission (verdict: Runtime Error):
N=int(input())
a=list(map(int,input().split()))
ans=[['']*30 for _ in range(N)]
i=29

while True:
    curbit=[aa%2 for aa in a]

    s=sum(curbit)
    if s==0:
        break

    if s%2==0:
        for j in range(N):
            ans[j][i]=str(curbit[j])
    else:
        for j in range(N):
            ans[j][i]=str(0 if curbit[j] else 1)


    a=[aa//2 for aa in a]
    i-=1

print(' '.join([str(int(''.join(aa),2)) for aa in ans]))

Fixed submission:
N=int(input())
a=list(map(int,input().split()))
ans=[[0]*30 for _ in range(N)]

if sum(a)==0:
    print(' '.join(['0']*N))
    exit(0)

i=29

while i>=0:
    curbit=[aa%2 for aa in a]

    s=sum(curbit)

    if s%2==0:
        for j in range(N):
            ans[j][i]=curbit[j]
    else:
        for j in range(N):
            ans[j][i]=0 if curbit[j] else 1



    a=[aa//2 for aa in a]
    
    i-=1

print(' '.join([str(int(''.join([str(aaa) for aaa in aa]),2)) for aa in ans]))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

N=int(input())
A=list(map(int,input().split()))
nmax=10**6
iscop=[True]*(nmax+1)
cnt=[0]*(nmax+1)

for a in A:
    cnt[a]+=1
    if iscop[a]==False:
        continue

    for j in range(2,nmax//a+1):
        iscop[j*a]=False
ans=0
for a in A:
    if cnt[a]<2 and iscop[a]:
        ans+=1

print(ans)

Fixed submission:
from collections import Counter

N=int(input())
A=Counter(list(map(int,input().split())))
nmax=10**6
iscop=[True]*(nmax+1)

for k in A.keys():
    if iscop[k]==False:
        continue

    for j in range(2,nmax//k+1):
        iscop[k*j]=False
ans=0
for k,v in A.items():
    if v<2 and iscop[k]:
        ans+=1

print(ans)

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

N=int(input())
A=sorted(list(map(int,input().split())))
nmax=10**6
iscop=[True]*(nmax+1)
cnt=[0]*(nmax+1)

for a in A:
    cnt[a]+=1
    if iscop[a]==False:
        continue

    for j in range(2,nmax//a+1):
        iscop[j*a]=False
ans=0
for a in A:
    if cnt[a]<2 and iscop[a]:
        ans+=1

print(ans)

Fixed submission:
from collections import Counter

N=int(input())
A=Counter(list(map(int,input().split())))
nmax=10**6
iscop=[True]*(nmax+1)

for k in A.keys():
    if iscop[k]==False:
        continue

    for j in range(2,nmax//k+1):
        iscop[k*j]=False
ans=0
for k,v in A.items():
    if v<2 and iscop[k]:
        ans+=1

print(ans)

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

N=int(input())
A=sorted(list(map(int,input().split())))
nmax=10**6
iscop=[True]*(nmax+1)

for a in A:
    if iscop[a]==False:
        continue

    for j in range(2,nmax//a+1):
        iscop[j*a]=False

cnt=Counter(A)
ans=0
for k,v in cnt.items():
    if iscop[k] and v<2:
        ans+=1

print(ans)

Fixed submission:
from collections import Counter

N=int(input())
A=Counter(list(map(int,input().split())))
nmax=10**6
iscop=[True]*(nmax+1)

for k in A.keys():
    if iscop[k]==False:
        continue

    for j in range(2,nmax//k+1):
        iscop[k*j]=False
ans=0
for k,v in A.items():
    if v<2 and iscop[k]:
        ans+=1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,M,K=list(map(int,input().split()))

mod=998244353

comb=1
pw=(M*pow(M-1,N-1,mod))%mod
ans=pw*comb

invmodk=[0]*(K+2)
invmodk[1]=1
invmodm=pow(M-1,mod-2,mod)
for k in range(2,K+1):
    invmodk[k]=invmodk[mod%k]*(mod-mod//k)%mod

for k in range(1,K+1):
    pw=(pw*invmodm)%mod
    comb*=(N-k)*invmodk[k]
    ans=(ans+pw*comb)%mod

print(ans)

Fixed submission:
N,M,K=list(map(int,input().split()))

mod=998244353

com=1
ans=0

for i in range(K+1):
    ans+=M*com*pow(M-1,N-1-i,mod)
    ans%=mod
    com*=(N-1-i)*pow(i+1,mod-2,mod)
    com%=mod

print(ans)

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

mod=998244353

comb=1
pw=(M*pow(M-1,N-1,mod))%mod
ans=pw*comb

invmodk=[0]*(K+1)
invmodk[1]=1
invmodm=pow(M-1,mod-2,mod)
for k in range(2,K+1):
    invmodk[k]=invmodk[mod%k]*(mod-mod//k)%mod

for k in range(1,K+1):
    pw=(pw*invmodm)%mod
    comb*=(N-k)*invmodk[k]
    ans=(ans+pw*comb)%mod

print(ans)

Fixed submission:
N,M,K=list(map(int,input().split()))

mod=998244353

com=1
ans=0

for i in range(K+1):
    ans+=M*com*pow(M-1,N-1-i,mod)
    ans%=mod
    com*=(N-1-i)*pow(i+1,mod-2,mod)
    com%=mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,M,K=list(map(int,input().split()))

mod=998244353

comb=1
pw=(M*pow(M-1,N-1,mod))%mod
ans=pw*comb

invmodk=[0,1]
invmodm=pow(M-1,mod-2,mod)
for k in range(2,K+1):
    invmodk.append(invmodk[mod%k]*(mod-mod//k)%mod)

for k in range(1,K+1):
    pw=(pw*invmodm)%mod
    comb*=(N-k)*invmodk[k]
    ans=(ans+pw*comb)%mod

print(ans)

Fixed submission:
N,M,K=list(map(int,input().split()))

mod=998244353

com=1
ans=0

for i in range(K+1):
    ans+=M*com*pow(M-1,N-1-i,mod)
    ans%=mod
    com*=(N-1-i)*pow(i+1,mod-2,mod)
    com%=mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,M,K=list(map(int,input().split()))

mod=998244353

def invmod(x):
    return pow(x,mod-2,mod)

comb=1
pw=(M*pow(M-1,N-1,mod))%mod
ans=pw*comb
invmodm=invmod(M-1)

for k in range(1,K+1):
    pw*=invmodm
    comb*=(N-k)*invmod(k)
    ans=(ans+pw*comb)%mod

print(ans)

Fixed submission:
N,M,K=list(map(int,input().split()))

mod=998244353

com=1
ans=0

for i in range(K+1):
    ans+=M*com*pow(M-1,N-1-i,mod)
    ans%=mod
    com*=(N-1-i)*pow(i+1,mod-2,mod)
    com%=mod

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

dp=[[0]*2019 for _ in range(2)]
dig=[int(c) for c in sys.stdin.readline().strip()]
tab=[[0]*2019 for _ in range(10)]

for x in range(10):
    for i in range(2019):
        tab[x][i]=(i*10+x)%2019

p=0
cnt=0
for x in dig:
    np=(p+1)&1
    for i in range(2019):
        dp[np][tab[x][i]]=dp[p][i]
    dp[np][x]+=1
    p=np
    cnt+=dp[p][0]

print(cnt)

Fixed submission:
from collections import Counter
S=input()[::-1]

X=[0]
md=2019

for i,s in enumerate(S):
    X.append((X[-1]+int(s)*pow(10,i,md))%md)

C=Counter(X)
ans=0
for v in C.values():
    ans+=v*(v-1)//2

print(ans)

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

dp=[[0]*2019 for _ in range(2)]
dig=[int(c) for c in sys.stdin.readline().strip()]

p=0
cnt=0
for x in dig:
    np=(p+1)&1
    for i in range(2019):
        dp[np][(i*10+x)%2019]=dp[p][i]
    dp[np][x]+=1
    p=np
    cnt+=dp[p][0]

print(cnt)

Fixed submission:
from collections import Counter
S=input()[::-1]

X=[0]
md=2019

for i,s in enumerate(S):
    X.append((X[-1]+int(s)*pow(10,i,md))%md)

C=Counter(X)
ans=0
for v in C.values():
    ans+=v*(v-1)//2

print(ans)

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

dp=[[0]*2019 for _ in range(2)]

p=0
cnt=0
for c in sys.stdin.readline().strip():
    x=int(c)

    for i in range(2019):
        dp[(p+1)&1][(i*10+x)%2019]=dp[p][i]
    dp[(p+1)&1][x]+=1
    p=(p+1)&1
    cnt+=dp[p][0]

print(cnt)

Fixed submission:
from collections import Counter
S=input()[::-1]

X=[0]
md=2019

for i,s in enumerate(S):
    X.append((X[-1]+int(s)*pow(10,i,md))%md)

C=Counter(X)
ans=0
for v in C.values():
    ans+=v*(v-1)//2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
dp=[[0]*2019 for _ in range(2)]

p=0
cnt=0
for c in input():
    x=int(c)

    for i in range(2019):
        dp[(p+1)&1][(i*10+x)%2019]=dp[p][i]
    dp[(p+1)&1][x]+=1
    p=(p+1)&1
    cnt+=dp[p][0]

print(cnt)

Fixed submission:
from collections import Counter
S=input()[::-1]

X=[0]
md=2019

for i,s in enumerate(S):
    X.append((X[-1]+int(s)*pow(10,i,md))%md)

C=Counter(X)
ans=0
for v in C.values():
    ans+=v*(v-1)//2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
dp=[[0]*2019 for _ in range(2)]

p=0
cnt=0
for c in input():
    x=int(c)

    for i in range(2019):
        dp[(p+1)&1][(i*10+x)%2019]=dp[p][i]
    dp[(p+1)&1][x]+=1
    p=(p+1)&1
    cnt+=dp[p][0]

print(cnt)

Fixed submission:
from collections import Counter
S=input()[::-1]

X=[0]
md=2019

for i,s in enumerate(S):
    X.append((X[-1]+int(s)*pow(10,i,md))%md)

C=Counter(X)
ans=0
for v in C.values():
    ans+=v*(v-1)//2

print(ans)
Buggy python submission (verdict: Runtime Error):
import numpy as np

R=int(input())

print(2*np.pi*R)

Fixed submission:
import numpy as np

R=int(input())

print(2*np.pi*R)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

n,p=list(map(int,input().split()))
s=[int(x) for x in sys.stdin.readline().strip()]
reslst=[0]*p

cnt=0

if p==2:
    for i in range(n):
        if s[i]%2==0:
            cnt+=i+1
elif p==5:
    for i in range(n):
        if s[i]==5 or s[i]==0:
            cnt+=i+1
else:
    x=0
    for i in range(n-1,-1,-1):
        x=s[i]*(10**(n-1-i))+x
        reslst[x%p]+=1
    reslst[0]+=1

    for i in range(p):
        j=reslst[i]

        cnt+=j*(j-1)//2

print(cnt)

Fixed submission:
import sys

n,p=list(map(int,input().split()))
s=sys.stdin.readline().strip()
reslst=[0]*p

cnt=0

if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            cnt+=i+1
elif p==5:
    for i in range(n):
        if s[i]=='5' or s[i]=='0':
            cnt+=i+1
else:
    reslst[0]+=1
    tmp=1
    now=0
    for i in [int(x) for x in s[::-1]]:
        now+=i*tmp
        now%=p
        reslst[now]+=1
        tmp=(tmp*10)%p
    
    for i in range(p):
        cnt+=reslst[i]*(reslst[i]-1)//2

print(cnt)

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

n,p=list(map(int,input().split()))
s=sys.stdin.readline().strip()
reslst=[0]*p

cnt=0

if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            cnt+=i+1
elif p==5:
    for i in range(n):
        if s[i]=='5' or s[i]=='0':
            cnt+=i+1
else:
    for i in range(n-1,-1,-1):
        x=int(s[i:])
        reslst[x%p]+=1
    reslst[0]+=1

    for i in range(p):
        j=reslst[i]

        cnt+=j*(j-1)//2

print(cnt)

Fixed submission:
import sys

n,p=list(map(int,input().split()))
s=sys.stdin.readline().strip()
reslst=[0]*p

cnt=0

if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            cnt+=i+1
elif p==5:
    for i in range(n):
        if s[i]=='5' or s[i]=='0':
            cnt+=i+1
else:
    reslst[0]+=1
    tmp=1
    now=0
    for i in [int(x) for x in s[::-1]]:
        now+=i*tmp
        now%=p
        reslst[now]+=1
        tmp=(tmp*10)%p
    
    for i in range(p):
        cnt+=reslst[i]*(reslst[i]-1)//2

print(cnt)

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

n,p=list(map(int,input().split()))
s=sys.stdin.readline().strip()
reslst=[0]*p

cnt=0

if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            cnt+=i+1
elif p==5:
    for i in range(n):
        if s[i]=='5' or s[i]=='0':
            cnt+=i+1
else:
    for i in range(n-1,-1,-1):
        x=int(s[i:])
        reslst[x%p]+=1
    reslst[0]+=1

    for i in range(p):
        j=reslst[i]

        cnt+=j*(j-1)//2

print(cnt)

Fixed submission:
import sys

n,p=list(map(int,input().split()))
s=sys.stdin.readline().strip()
reslst=[0]*p

cnt=0

if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            cnt+=i+1
elif p==5:
    for i in range(n):
        if s[i]=='5' or s[i]=='0':
            cnt+=i+1
else:
    reslst[0]+=1
    tmp=1
    now=0
    for i in [int(x) for x in s[::-1]]:
        now+=i*tmp
        now%=p
        reslst[now]+=1
        tmp=(tmp*10)%p
    
    for i in range(p):
        cnt+=reslst[i]*(reslst[i]-1)//2

print(cnt)
Buggy python submission (verdict: Runtime Error):
import sys
import heapq
import copy
import numpy as np
from collections import deque

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

ret=0
if n>=10:
    ret=r
else:
    ret=r+100*(10-n)

print(ret)

Fixed submission:
import sys
import heapq
import copy
import numpy as np
from collections import deque

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

ret=0
if n>=10:
    ret=r
else:
    ret=r+100*(10-n)

print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from itertools import combinations

H,W=list(map(int,input().split()))
S=[input() for _ in range(H)]
pts=[[j,i] for i in range(W) for j in range(H)]
d=[[-1,0],[1,0],[0,1],[0,-1]]
ret=0

for s,g in combinations(pts,2):
    if S[s[0]][s[1]]=='#' or S[g[0]][g[1]]=='#':
        continue

    q=deque([s+[0]])
    while len(q)>0:
        h,w,cnt=deque.popleft(q)

        if g[0]==h and g[1]==w:
            ret=max(ret,cnt)
            break

        for dw,dh in d:
            if 0<=w+dw<W and 0<=h+dh<H and S[h+dh][w+dw]=='.':
                deque.append(q,[h+dh,w+dw,cnt+1])

print(ret)

Fixed submission:
from collections import deque

H,W=list(map(int,input().split()))
S=[input() for _ in range(H)]

start=[[j,i] for i in range(W) for j in range(H)]
res=0

for pt in start:
    v=[[0]*W for _ in range(H)]
    if S[pt[0]][pt[1]]=='#':
        continue
    q=deque([pt+[0]])
    dist=0

    while len(q)>0:
        h,w,cnt=q.popleft()
        
        if v[h][w]==1:
            continue
        else:
            v[h][w]=1

        dist=max(dist,cnt)

        for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
            nh=h+dh
            nw=w+dw
            if 0>nh or nh>=H or 0>nw or nw>=W or S[nh][nw]=='#':
                continue
            q.append([nh,nw,cnt+1])
    
    res=max(res,dist)

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from itertools import combinations

H,W=list(map(int,input().split()))
S=[input() for _ in range(H)]
pts=[[j,i] for i in range(W) for j in range(H)]
d=[[-1,0],[1,0],[0,1],[0,-1]]
ret=0

for s,g in combinations(pts,2):
    if S[s[0]][s[1]]=='#' or S[g[0]][g[1]]=='#':
        continue

    q=deque([s+[0]])
    while len(q)>0:
        h,w,cnt=q.popleft()

        if g[0]==h and g[1]==w:
            ret=max(ret,cnt)
            break

        for dw,dh in d:
            if 0<=w+dw<W and 0<=h+dh<H and S[h+dh][w+dw]=='.':
                q.append([h+dh,w+dw,cnt+1])

print(ret)

Fixed submission:
from collections import deque

H,W=list(map(int,input().split()))
S=[input() for _ in range(H)]

start=[[j,i] for i in range(W) for j in range(H)]
res=0

for pt in start:
    v=[[0]*W for _ in range(H)]
    if S[pt[0]][pt[1]]=='#':
        continue
    q=deque([pt+[0]])
    dist=0

    while len(q)>0:
        h,w,cnt=q.popleft()
        
        if v[h][w]==1:
            continue
        else:
            v[h][w]=1

        dist=max(dist,cnt)

        for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
            nh=h+dh
            nw=w+dw
            if 0>nh or nh>=H or 0>nw or nw>=W or S[nh][nw]=='#':
                continue
            q.append([nh,nw,cnt+1])
    
    res=max(res,dist)

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

n=int(input())
alst=list(map(int,sys.stdin.readline().strip().split()))

cumsum=[[0]*(n+1) for i in range(60)]

md=10**9+7

for i in range(1,n+1):
    a=alst[i-1]
    dig=0
    while dig<60:
        bit=a%2
        cumsum[dig][i]=cumsum[dig][i-1]+bit
        dig+=1
        a//=2

ans=0
ceff=1

for d in range(60):
    ret=0
    for i in range(1,n):
        ret+=(cumsum[d][i]-cumsum[d][i-1])*(n-i-cumsum[d][n]+cumsum[d][i])
        ret+=(1-cumsum[d][i]+cumsum[d][i-1])*(cumsum[d][n]-cumsum[d][i])
    ans=(ans+ceff*ret)%md
    ceff=(2*ceff)%md

print(ans)



Fixed submission:
import sys

n=int(input())
alst=list(map(int,sys.stdin.readline().strip().split()))

cumsum=[[0]*(n+1) for i in range(60)]

md=10**9+7

for i in range(1,n+1):
    a=alst[i-1]
    dig=0
    while dig<60:
        bit=a%2
        cumsum[dig][i]=cumsum[dig][i-1]+bit
        dig+=1
        a//=2

ans=0
ceff=1

for d in range(60):
    ret=0
    for i in range(1,n):
        ret+=(cumsum[d][i]-cumsum[d][i-1])*(n-i-cumsum[d][n]+cumsum[d][i])
        ret+=(1-cumsum[d][i]+cumsum[d][i-1])*(cumsum[d][n]-cumsum[d][i])
    ans=(ans+ceff*ret)%md
    ceff=(2*ceff)%md

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

n=int(input())
g=[[] for i in range(n+1)]
clst=[-1]*(n-1)

for i in range(n-1):
    a,b=list(map(int,input().split()))

    g[a].append([b,i])
    g[b].append([a,i])


q=deque([[1,0]])
k=0

while len(q)>0:
    u,c=deque.popleft(q)

    clrs=list(range(1,c))+list(range(c+1,len(g[u])+1))
    cnt=0

    for v,i in g[u]:
        if clst[i]==c:
            continue
        clst[i]=clrs[cnt]
        deque.append(q,[v,clst[i]])
        cnt+=1


    if len(clrs)>0:
        k=max(k,clrs[-1])

print(k)

for i in range(n-1):
    print(clst[i])


Fixed submission:
from collections import deque

n=int(input())
g=[[] for i in range(n+1)]
clst=[-1]*(n-1)

for i in range(n-1):
    a,b=list(map(int,input().split()))

    g[a].append([b,i])
    g[b].append([a,i])


q=deque([[1,0]])
k=0

while len(q)>0:
    u,c=deque.popleft(q)

    clr=1

    for v,i in g[u]:
        if clst[i]==c:
            continue
        if clr==c:
            clr+=1
        
        clst[i]=clr
        deque.append(q,[v,clr])

        clr+=1


    k=max(k,clr-1)

print(k)

for i in range(n-1):
    print(clst[i])

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

n=int(input())
g=[[] for i in range(n+1)]
clst=[-1]*(n-1)

for i in range(n-1):
    a,b=list(map(int,input().split()))

    g[a].append([b,i])
    g[b].append([a,i])


q=[(1,0)]
k=0

while len(q)>0:
    u,c=heapq.heappop(q)

    clrs=list(range(1,c))+list(range(c+1,len(g[u])+1))
    cnt=0

    for v,i in g[u]:
        if clst[i]==c:
            continue
        clst[i]=clrs[cnt]
        heapq.heappush(q,(v,clst[i]))
        cnt+=1


    if len(clrs)>0:
        k=max(k,clrs[-1])

print(k)

for i in range(n-1):
    print(clst[i])


Fixed submission:
from collections import deque

n=int(input())
g=[[] for i in range(n+1)]
clst=[-1]*(n-1)

for i in range(n-1):
    a,b=list(map(int,input().split()))

    g[a].append([b,i])
    g[b].append([a,i])


q=deque([[1,0]])
k=0

while len(q)>0:
    u,c=deque.popleft(q)

    clr=1

    for v,i in g[u]:
        if clst[i]==c:
            continue
        if clr==c:
            clr+=1
        
        clst[i]=clr
        deque.append(q,[v,clr])

        clr+=1


    k=max(k,clr-1)

print(k)

for i in range(n-1):
    print(clst[i])
Buggy python submission (verdict: Runtime Error):
n,t=list(map(int,input().split()))
ab=sorted([list(map(int,input().split())) for _ in range(n)],key=lambda x: 10000*x[1]+x[0])

a,b=ab.pop()
ans2=b
t-=1

dp=[[-10**10]*3001 for _ in range(n+1)]
dp[0][0]=0

bmax=0
for i in range(n-1):
    for j in range(t+1):
        dp[i+1][j]=max(dp[i][j],dp[i][j-ab[i][0]]+ab[i][1] if j>=ab[i][0] else 0)
        bmax=max(bmax,dp[i+1][j])

ans2+=bmax

print(max(ans,ans2))

Fixed submission:
n,t=list(map(int,input().split()))
ab=sorted([list(map(int,input().split())) for _ in range(n)],key=lambda x:x[0])

dp=[[-10**10]*(t+1) for _ in range(n+1)]
dp[0][0]=0
dp[1][0]=0
ans=ab[0][1]
for i in range(1,n):
    for j in range(t):
        dp[i+1][j]=max(dp[i][j],dp[i][j-ab[i-1][0]]+ab[i-1][1] if j>=ab[i-1][0] else -10**10)
        ans=max(ans,dp[i+1][j]+ab[i][1])

print(ans)
Buggy python submission (verdict: Runtime Error):
import numpy as np

a,b,x=list(map(int,input().split()))
area=x/a

if area<=a*b/2.0:
    h=2*area/b
    print(90-np.degrees(np.arctan(h/b)))
else:
    h=2*b-2*area/a
    print(np.degrees(np.arctan(h/a)))

Fixed submission:
import numpy as np

a,b,x=list(map(int,input().split()))
area=x/a

if area<=a*b/2.0:
    h=2*area/b
    print(90-np.degrees(np.arctan(h/b)))
else:
    h=2*b-2*area/a
    print(np.degrees(np.arctan(h/a)))
Buggy python submission (verdict: Runtime Error):
import math

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

maxn=10**6
prime=[1]*(maxn+1)
prime[0]=0
prime[1]=0

for i in range(2,maxn+1):
    if prime[i]==0:
        continue

    for j in range(2,maxn//i+1):
        prime[i*j]=0

C=math.gcd(A,B)
cnt=1

for i in range(2,maxn+1):
    if prime[i]==0:
        continue

    if C%i==0:
        while C%i==0:
            C//=i
        cnt+=1

if C>1:
    cnt+=1

print(cnt)

Fixed submission:
import fractions

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

maxn=10**6
prime=[1]*(maxn+1)
prime[0]=0
prime[1]=0

for i in range(2,maxn+1):
    if prime[i]==0:
        continue

    for j in range(2,maxn//i+1):
        prime[i*j]=0

C=fractions.gcd(A,B)
cnt=1

for i in range(2,maxn+1):
    if prime[i]==0:
        continue

    if C%i==0:
        while C%i==0:
            C//=i
        cnt+=1

if C>1:
    cnt+=1

print(cnt)