Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n,k,*a,=map(int,open(0).read().split())
def f(li):
	b=[0]*(n+1)
	for i,x in enumerate(li):
		b[max(0,i-x)]+=1
		b[min(i+x+1,n)]-=1
	for i in range(n):
		b[i+1]+=b[i]
	return b[:-1]
for _ in range(k):
	a=f(a)
	if a==[n]*n:
		print(*a)
		exit()
print(*a)

Fixed submission:
n,k,*a,=map(int,open(0).read().split())
def f(li):
	b=[0]*(n+1)
	for i,x in enumerate(li):
		b[max(0,i-x)]+=1
		b[min(i+x+1,n)]-=1
	for i in range(n):
		b[i+1]+=b[i]
	return b[:-1]
for _ in range(k):
	a=f(a)
	if a==[n]*n:
		print(*a)
		exit()
print(*a)
Buggy python submission (verdict: Runtime Error):
import numpy as np
n,s,*a=map(int,open(0).read().split())
mod=998244353
d=np.zeros(s+1,dtype=np.int64)
d[0]=1
for x in a:
	p=d*2
	p[x:]+=d[:s-x+1]
	p%=mod
	d=p
print(d[-1])

Fixed submission:
n,s,*a=map(int,open(0).read().split())
mod=998244353
d=[0]*(s+1)
d[0]=1
for x in a:
	p=[0]*(s+1)
	for i in range(s+1):
		p[i]+=d[i]*2
		if i+x<=s:
			p[i+x]+=d[i]
		p[i]%=mod
	d=p
print(d[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,s,*a=map(int,open(0).read().split())
mod=998244353
d=[0]*(s+1)
d[0]=1
for x in a:
	p=[0]*(s+1)
	for i in range(s+1):
		p[i]+=d[i]*2
		if i+x<=s:
			p[i+x]+=d[i]
		p[i]%=mod
	d=p
print(d[-1])

Fixed submission:
n,s,*a=map(int,open(0).read().split())
mod=998244353
d=[0]*(s+1)
d[0]=1
for x in a:
	p=[0]*(s+1)
	for i in range(s+1):
		p[i]+=d[i]*2
		if i+x<=s:
			p[i+x]+=d[i]
		p[i]%=mod
	d=p
print(d[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,k,*a=map(int,open(0).read().split())
a=[x-1 for x in a]
dist=[0]*n
cur=0
while True:
	nxt=a[cur]
	if k==1:
		print(nxt+1)
		break
	if dist[nxt]:
		k=(k-dist[nxt])%(dist[cur]-dist[nxt]+1)+dist[nxt]
		k-=1
		dist=[0]*n
		cur=nxt
	else:
		k-=1
		dist[nxt]=dist[cur]+1
		cur=nxt

Fixed submission:
n,k,*a=map(int,open(0).read().split())
a=[x-1 for x in a]
dist=[0]*n
cur=0
while True:
	nxt=a[cur]
	if k==0:
		print(cur+1)
		break
	if dist[nxt]:
		k=(k-dist[nxt])%(dist[cur]-dist[nxt]+1)+dist[nxt]
		k-=1
		dist=[0]*n
		cur=nxt
	else:
		k-=1
		dist[nxt]=dist[cur]+1
		cur=nxt

Buggy python submission (verdict: Time Limit Exceeded):
n,k,*a=map(int,open(0).read().split())
a=[x-1 for x in a]
dist=[0]*n
cur=0
while True:
	nxt=a[cur]
	if k==1:
		print(nxt+1)
		break
	if dist[nxt]:
		k=(k-dist[nxt])%(dist[cur]-dist[nxt]+1)+dist[nxt]
		k-=1
		dist=[0]*n
		cur=nxt
	else:
		k-=1
		dist[nxt]=dist[cur]+1
		cur=nxt

Fixed submission:
n,k,*a=map(int,open(0).read().split())
a=[x-1 for x in a]
dist=[0]*n
cur=0
while True:
	nxt=a[cur]
	if k==0:
		print(cur+1)
		break
	if dist[nxt]:
		k=(k-dist[nxt])%(dist[cur]-dist[nxt]+1)+dist[nxt]
		k-=1
		dist=[0]*n
		cur=nxt
	else:
		k-=1
		dist[nxt]=dist[cur]+1
		cur=nxt
Buggy python submission (verdict: Runtime Error):
from heapq import *
import sys
input = sys.stdin.buffer.readline
n, m, s = map(int, input().split())
lim = 2510
di = [[float("inf")] * lim for _ in range(n)]
di[0][s] = 0
con = [[] for _ in range(n)]
for _ in range(m):
	u, v, a, b = map(int, input().split())
	con[u - 1].append((v - 1, a, b))
	con[v - 1].append((u - 1, a, b))
q = [(0, s, 0)]
cd = [list(map(int, input().split())) for _ in range(n)]
while q:
	time, have, cur = heappop(q)
	if di[cur][have] < time:
		continue
	c, d = cd[cur]
	if have + c < lim and di[cur][have + c] > time + d:
		di[cur][have + c] = time + d
		heappush(q, (time + d, have + c, cur))
	for nxt, dh, dt in con[cur]:
		if have >= dh and di[nxt][have - dh] > time + dt:
			di[nxt][have - dh] = time + dt
			heappush(q, (time + dt, have - dh, nxt))
for p in di[1:]:
	print(min(p))


Fixed submission:
from heapq import *
import sys
input = sys.stdin.buffer.readline
n, m, s = map(int, input().split())
lim = 2510
di = [[float("inf")] * lim for _ in range(n)]
di[0][min(s,lim-1)] = 0
con = [[] for _ in range(n)]
for _ in range(m):
	u, v, a, b = map(int, input().split())
	con[u - 1].append((v - 1, a, b))
	con[v - 1].append((u - 1, a, b))
q = [(0, min(s,lim-1), 0)]
cd = [list(map(int, input().split())) for _ in range(n)]
while q:
	time, have, cur = heappop(q)
	if di[cur][have] < time:
		continue
	c, d = cd[cur]
	if have + c < lim and di[cur][have + c] > time + d:
		di[cur][have + c] = time + d
		heappush(q, (time + d, have + c, cur))
	for nxt, dh, dt in con[cur]:
		if have >= dh and di[nxt][have - dh] > time + dt:
			di[nxt][have - dh] = time + dt
			heappush(q, (time + dt, have - dh, nxt))
for p in di[1:]:
	print(min(p))
Buggy python submission (verdict: Time Limit Exceeded):
n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1)for _ in range(n+1)]
for t,(c,k) in enumerate(sorted((c,k) for k,c in enumerate(a))[::-1]):
	for i in range(t+1):
		j=t-i
		if dp[i+1][j]<=(s:=dp[i][j]+c*abs(i-k)):dp[i+1][j]=s
		if dp[i][j+1]<=(s:=dp[i][j]+c*abs(n-1-k-j)):dp[i][j+1]=s
print(max(dp[i][~i]for i in range(n+1)))

Fixed submission:
n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1)for _ in range(n+1)]
for t,(c,k) in enumerate(sorted((c,k) for k,c in enumerate(a))[::-1]):
	for i in range(t+1):
		j=t-i
		if dp[i+1][j]<dp[i][j]+c*abs(i-k):dp[i+1][j]=dp[i][j]+c*abs(i-k)
		if dp[i][j+1]<dp[i][j]+c*abs(n-1-k-j):dp[i][j+1]=dp[i][j]+c*abs(n-1-k-j)
print(max(dp[i][~i]for i in range(n+1)))
Buggy python submission (verdict: Runtime Error):
a,b,c,d,e,f=input().split()
if c==d and e==f:
  print("Yes")
else:
  print("No")

Fixed submission:
a,b,c,d,e,f=input()
if c==d and e==f:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
n, *L = map(int, open(0).read().split())
mod = 10 ** 9 + 7
con = [[] for _ in range(n + 1)]
sz = [1] * (n + 1)
par = [0] * (n + 1)

for s, t in zip(*[iter(L)] * 2):
	con[s] += t,
	con[t] += s,


def prepare(m, mod=10 ** 9 + 7):
	fac = [1] * (m + 1)
	inv = [1] * (m + 1)
	for i in range(1, m + 1):
		fac[i] = fac[i - 1] * i % mod
	inv[-1] = pow(fac[-1], mod - 2, mod)
	for i in range(m - 1, -1, -1):
		inv[i] = inv[i + 1] * (i + 1) % mod
	return fac, inv


fac, inv = prepare(n)


def dfs1(cur, pre):
	par[cur] = pre
	for nxt in con[cur]:
		if nxt != pre:
			dfs1(nxt, cur)
			sz[cur] += sz[nxt]
			dp1[cur] *= dp1[nxt] * inv[sz[nxt]] % mod
			dp1[cur] %= mod
	dp1[cur] *= fac[sz[cur] - 1]
	dp1[cur] %= mod


def dfs2(cur, pre):
	dp2[cur] *= dp1[cur] * inv[sz[cur] - 1] % mod
	dp2[cur] %= mod
	dp2[cur] *= fac[n - 1]
	dp2[cur] %= mod
	for nxt in con[cur]:
		if nxt != pre:
			dp2[nxt] = fac[sz[nxt]] * pow(n - sz[nxt], mod - 2, mod) * pow(dp1[nxt], mod - 2, mod) * dp2[cur] * inv[n - 1] % mod
			dfs2(nxt, cur)


dp1 = [1] * (n + 1)
dfs1(1, 0)
dp2 = [1] * (n + 1)
dfs2(1, 0)

print(*dp2[1:], sep="\n")


Fixed submission:
import sys
sys.setrecursionlimit(1234567890)

n, *L = map(int, open(0).read().split())
mod = 10 ** 9 + 7
con = [[] for _ in range(n + 1)]
sz = [1] * (n + 1)
par = [0] * (n + 1)

for s, t in zip(*[iter(L)] * 2):
	con[s] += t,
	con[t] += s,


def prepare(m, mod=10 ** 9 + 7):
	fac = [1] * (m + 1)
	inv = [1] * (m + 1)
	for i in range(1, m + 1):
		fac[i] = fac[i - 1] * i % mod
	inv[-1] = pow(fac[-1], mod - 2, mod)
	for i in range(m - 1, -1, -1):
		inv[i] = inv[i + 1] * (i + 1) % mod
	return fac, inv


fac, inv = prepare(n)


def dfs1(cur, pre):
	par[cur] = pre
	for nxt in con[cur]:
		if nxt != pre:
			dfs1(nxt, cur)
			sz[cur] += sz[nxt]
			dp1[cur] *= dp1[nxt] * inv[sz[nxt]] % mod
			dp1[cur] %= mod
	dp1[cur] *= fac[sz[cur] - 1]
	dp1[cur] %= mod


def dfs2(cur, pre):
	dp2[cur] *= dp1[cur] * inv[sz[cur] - 1] % mod
	dp2[cur] %= mod
	dp2[cur] *= fac[n - 1]
	dp2[cur] %= mod
	for nxt in con[cur]:
		if nxt != pre:
			dp2[nxt] = fac[sz[nxt]] * pow(n - sz[nxt], mod - 2, mod) * pow(dp1[nxt], mod - 2, mod) * dp2[cur] * inv[n - 1] % mod
			dfs2(nxt, cur)


dp1 = [1] * (n + 1)
dfs1(1, 0)
dp2 = [1] * (n + 1)
dfs2(1, 0)

print(*dp2[1:], sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
n,s,*a=map(int,open(0).read().split())
ans=0
mod=998244353
dp=[0]*(s+1)
for i in range(n):
	dp[0]+=1
	if a[i]>s:
		continue
	ans+=dp[s-a[i]]*(n-i)
	ans%=mod
	for j in range(s,a[i]-1,-1):
		dp[j]+=dp[j-a[i]]
		dp[j]%=mod
print(ans)

Fixed submission:
n,s,*a=map(int,open(0).read().split())
ans=0
mod=998244353
dp=[0]*(s+1)
for i in range(n):
	dp[0]+=1
	if a[i]>s:
		continue
	ans+=dp[s-a[i]]*(n-i)
	ans%=mod
	for j in range(s,a[i]-1,-1):
		dp[j]+=dp[j-a[i]]
		dp[j]%=mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,s,*a=map(int,open(0).read().split())
ans=0
mod=998244353
for i in range(n):
	d={a[i]:1}
	if a[i]==s:
		ans+=(i+1)*(n-i)
		ans%=mod
	for j,x in enumerate(a[i+1:],i+1):
		if s-x in d:
			ans+=(i+1)*(n-j)*d[s-x]
			ans%=mod
		for y in sorted(list(d.keys()))[::-1]:
			if x+y<=s:
				d[x+y]=d.get(x+y,0)+d[y]
				d[x+y]%=mod
print(ans)

Fixed submission:
n,s,*a=map(int,open(0).read().split())
ans=0
mod=998244353
dp=[0]*(s+1)
for i in range(n):
	dp[0]+=1
	if a[i]>s:
		continue
	ans+=dp[s-a[i]]*(n-i)
	ans%=mod
	for j in range(s,a[i]-1,-1):
		dp[j]+=dp[j-a[i]]
		dp[j]%=mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,s,*a=map(int,open(0).read().split())
ans=0
mod=998244353
for i in range(n):
	d={a[i]:1}
	if a[i]==s:
		ans+=(i+1)*(n-i)
		ans%=mod
	for j,x in enumerate(a[i+1:],i+1):
		if s-x in d:
			ans+=(i+1)*(n-j)*d[s-x]
			ans%=mod
		for y in sorted(list(d.keys()))[::-1]:
			if x+y<=s:
				d[x+y]=d.get(x+y,0)+d[y]
print(ans)

Fixed submission:
n,s,*a=map(int,open(0).read().split())
ans=0
mod=998244353
dp=[0]*(s+1)
for i in range(n):
	dp[0]+=1
	if a[i]>s:
		continue
	ans+=dp[s-a[i]]*(n-i)
	ans%=mod
	for j in range(s,a[i]-1,-1):
		dp[j]+=dp[j-a[i]]
		dp[j]%=mod
print(ans)
Buggy python submission (verdict: Runtime Error):
n,a,b=map(int,input().split())
print(n//(a+b)*a+min(a,n//%(a+b)))

Fixed submission:
n,a,b=map(int,input().split())
print(n//(a+b)*a+min(a,n%(a+b)))
Buggy python submission (verdict: Runtime Error):
n=input()
k=int(input())
dp=[[[0]*(k+2) for _ in range(2)] for _ in range(len(n)+1)]
dp[0][0][0]=1
for i,c in enumerate(n):
	for f in range(2):
		for j in range(k+1):
			for l in range(10 if f else int(c)+1):
				dp[i+1][f or l<c][j+(l>0)]+=dp[i][f][j]
print(dp[-1][0][k]+dp[-1][1][k])

Fixed submission:
n=input()
k=int(input())
dp=[[[0]*(k+2) for _ in range(2)] for _ in range(len(n)+1)]
dp[0][0][0]=1
for i,c in enumerate(n):
	c=int(c)
	for f in range(2):
		for j in range(k+1):
			for l in range(10*f or c+1):
				dp[i+1][f or l<c][j+(l>0)]+=dp[i][f][j]
print(dp[-1][0][k]+dp[-1][1][k])
Buggy python submission (verdict: Time Limit Exceeded):
h,n,*L=map(int,open(0).read().split())
dp=[0]+[9e9]*h
ov=9e9
for a,b in zip(*[iter(L)]*2):
	for i in range(h):
		if a+i>h:
			ov=min(min(dp[i:])+b,ov)
			break
		t=dp[i]+b
		if t<dp[i+a]:
			dp[i+a]=t
print(min(ov,dp[h]))

Fixed submission:
h,n,*L=map(int,open(0).read().split())
dp=[float('inf')]*(h+10100)
dp[0]=0
for a,b in zip(*[iter(L)]*2):
    for i in range(h):
        t=dp[i]+b
        if t<dp[i+a]:
            dp[i+a]=dp[i]+b
print(min(dp[h:]))

Buggy python submission (verdict: Time Limit Exceeded):
h,n,*L=map(int,open(0).read().split())
dp=[0]+[9e9]*h
for a,b in zip(*[iter(L)]*2):
	for i in range(h):
		dp[min(i+a,h)]=min(dp[min(i+a,h)],dp[i]+b)
print(dp[h])

Fixed submission:
h,n,*L=map(int,open(0).read().split())
dp=[float('inf')]*(h+10100)
dp[0]=0
for a,b in zip(*[iter(L)]*2):
    for i in range(h):
        t=dp[i]+b
        if t<dp[i+a]:
            dp[i+a]=dp[i]+b
print(min(dp[h:]))

Buggy python submission (verdict: Time Limit Exceeded):
h,n,*L=map(int,open(0).read().split())
dp=[float('inf')]*(h+10100)
dp[0]=0
for a,b in zip(*[iter(L)]*2):
    for i in range(h):
        t=dp[i]+b
        if t<dp[i+a]:
            dp[i+a]=dp[i]+b
print(min(dp[h:]))

Fixed submission:
h,n,*L=map(int,open(0).read().split())
dp=[float('inf')]*(h+10100)
dp[0]=0
for a,b in zip(*[iter(L)]*2):
    for i in range(h):
        t=dp[i]+b
        if t<dp[i+a]:
            dp[i+a]=dp[i]+b
print(min(dp[h:]))
Buggy python submission (verdict: Runtime Error):
n=int(input())
l=[[0]*10for _ in range(10)]
for x in range(1,n+1):l[a=int(str(x)[0])][b=int(str(x)[-1])]+=1
print(sum(l[i][j]*l[j][i]for i in range(10)for j in range(10)))

Fixed submission:
n=int(input())
l=[[0]*10for _ in range(10)]
for x in range(1,n+1):l[int(str(x)[0])][int(str(x)[-1])]+=1
print(sum(l[i][j]*l[j][i]for i in range(10)for j in range(10)))
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

n,*a=map(int,open(0).read().split())
mod=10**9+7
lcm=1
for x in a:
    lcm=lcm*x//gcd(lcm,x)
ans=0
for x in a:
    ans+=(lcm//x)%mod
    ans%=mod
print(ans)

Fixed submission:
def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)

def main():
	n, *a = map(int, open(0).read().split())
	mod = 10 ** 9 + 7
	lcm = 1
	for x in a:
		lcm = lcm * x // gcd(lcm, x)
	lcm %= mod
	ans = sum(pow(x, mod - 2, mod) for x in a) % mod
	print(ans * lcm % mod)

if __name__ == "__main__":
	main()

Buggy python submission (verdict: Time Limit Exceeded):
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

n,*a=map(int,open(0).read().split())
mod=10**9+7
lcm=1
for x in a:
    lcm=lcm*x//gcd(lcm,x)
ans=0
for x in a:
    ans+=(lcm//x)%mod
    ans%=mod
print(ans)

Fixed submission:
def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)

def main():
	n, *a = map(int, open(0).read().split())
	mod = 10 ** 9 + 7
	lcm = 1
	for x in a:
		lcm = lcm * x // gcd(lcm, x)
	lcm %= mod
	ans = sum(pow(x, mod - 2, mod) for x in a) % mod
	print(ans * lcm % mod)

if __name__ == "__main__":
	main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.buffer.readline
from itertools import combinations
from math import sqrt

n=int(input())
P=[tuple(map(int,input().split())) for _ in range(n)]

def R(*L):
	a,b,c=[sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)for p1,p2 in zip(L,L[1:]+L)]
	s=(a+b+c)/2
	return sqrt(s*(s-a)*(s-b)*(s-c))*4/(a*b*c)

ans=max(sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)for p1,p2 in combinations(P,2))
if n>2:
	ans_=max(R(*L) for L in combinations(P,3))
	ans=max(ans,ans_)
print(ans/2)

Fixed submission:
import sys
input = sys.stdin.buffer.readline
from itertools import combinations
from math import hypot
n=int(input())
P=[tuple(map(int,input().split())) for _ in range(n)]
ans=1e9
for p1,p2 in combinations(P,2):
	X,Y=(p1[0]+p2[0])/2,(p1[1]+p2[1])/2
	r=0
	for x,y in P:
		t=hypot(X-x,Y-y)
		if r<t:r=t
	if ans>r:ans=r
if n>2:
	ans_=1e9
	for p1,p2,p3 in combinations(P,3):
		a=hypot(p2[0]-p3[0],p2[1]-p3[1])
		b=hypot(p3[0]-p1[0],p3[1]-p1[1])
		c=hypot(p1[0]-p2[0],p1[1]-p2[1])
		if (a+b+c)-2*max(a,b,c)<1e-8:continue
		s,t,u=(-a*a+b*b+c*c)*a*a,(a*a-b*b+c*c)*b*b,(a*a+b*b-c*c)*c*c
		X=(s*p1[0]+t*p2[0]+u*p3[0])/(s+t+u)
		Y=(s*p1[1]+t*p2[1]+u*p3[1])/(s+t+u)
		r=0
		for x,y in P:
			t=hypot(X-x,Y-y)
			if r<t:r=t
		if ans_>r:ans_=r
	# print(ans_)
	ans=min(ans,ans_)
print(ans)

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.buffer.readline
from itertools import combinations
from math import sqrt

n=int(input())
P=[tuple(map(int,input().split())) for _ in range(n)]
P+=[P[0]]

def R(*L):
	a,b,c=[sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)for p1,p2 in zip(L,L[1:]+L)]
	s=(a+b+c)/2
	return sqrt(s*(s-a)*(s-b)*(s-c))

ans=max(sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)for p1,p2 in combinations(P,2))
ans_=max(R(*L) for L in combinations(P,3))
print(max(ans,ans_)/2)

Fixed submission:
import sys
input = sys.stdin.buffer.readline
from itertools import combinations
from math import hypot
n=int(input())
P=[tuple(map(int,input().split())) for _ in range(n)]
ans=1e9
for p1,p2 in combinations(P,2):
	X,Y=(p1[0]+p2[0])/2,(p1[1]+p2[1])/2
	r=0
	for x,y in P:
		t=hypot(X-x,Y-y)
		if r<t:r=t
	if ans>r:ans=r
if n>2:
	ans_=1e9
	for p1,p2,p3 in combinations(P,3):
		a=hypot(p2[0]-p3[0],p2[1]-p3[1])
		b=hypot(p3[0]-p1[0],p3[1]-p1[1])
		c=hypot(p1[0]-p2[0],p1[1]-p2[1])
		if (a+b+c)-2*max(a,b,c)<1e-8:continue
		s,t,u=(-a*a+b*b+c*c)*a*a,(a*a-b*b+c*c)*b*b,(a*a+b*b-c*c)*c*c
		X=(s*p1[0]+t*p2[0]+u*p3[0])/(s+t+u)
		Y=(s*p1[1]+t*p2[1]+u*p3[1])/(s+t+u)
		r=0
		for x,y in P:
			t=hypot(X-x,Y-y)
			if r<t:r=t
		if ans_>r:ans_=r
	# print(ans_)
	ans=min(ans,ans_)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
	n, *a = map(int, open(0).read().split())
	mod = 10 ** 9 + 7
	l = [[x >> k & 1 for k in range(61)] for x in a]
	ll = [sum(t) for t in zip(*l)]
	ans = sum(s * (n - s) * (1 << i) % mod for i, s in enumerate(ll))
	print(ans % mod)

if __name__ == "__main__":
	main()

Fixed submission:
n, *a = map(int, open(0).read().split())
ans = 0
mod = 10 ** 9 + 7
for k in range(61):
	m = 1 << k
	c = 0
	for x in a:
		if m & x:
			c += 1
	ans += (c) * (n - c) * m
	ans %= mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, *a = map(int, open(0).read().split())
ans = 0
mod = 10 ** 9 + 7
for k in range(61):
	m = 1 << k
	c = 0
	for x in a:
		if m & x:
			c += 1
	ans += (c) * (n - c) * m
	ans %= mod
print(ans)


Fixed submission:
n, *a = map(int, open(0).read().split())
ans = 0
mod = 10 ** 9 + 7
for k in range(61):
	m = 1 << k
	c = 0
	for x in a:
		if m & x:
			c += 1
	ans += (c) * (n - c) * m
	ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
def main():
	n, m = map(int, input().split())
	rev = input()[::-1]
	ans = []
	cur = 0
	while cur < n:
		for i in range(cur + 1, cur + m + 1):
			if i==n:
				nxt = i
				break
			if rev[i]=="0":
				nxt = i
		if cur==nxt:
			print(-1)
			exit()
		ans += [nxt - cur]
		cur = nxt
		if cur==n:
			break
	print(" ".join(map(str, ans[::-1])))


if __name__=="__main__":
	main()


Fixed submission:
n,m=map(int,input().split())
su=input()
rev=su[::-1]
if "1"*m in su:
	print(-1)
	exit()
dist_f_n=[float('inf')]*(n+1)
dist_f_n[0]=0
for i in range(1,m+1):
	if rev[i]=="0":
		dist_f_n[i]=1
		last=i
		if i==n:
			break
while last<n:
	for i in range(last+1,last+m+1):
		if rev[i]=="0":
			dist_f_n[i]=dist_f_n[last]+1
			_last=i
			if i==n:
				break
	last=_last
cur=dist_f_n[-1]
_i=0
ans=[]
for i,x in enumerate(dist_f_n[::-1]):
	if x==cur-1:
		ans.append(i-_i)
		cur-=1
		_i=i
print(" ".join(map(str,ans)))
Buggy python submission (verdict: Runtime Error):
n,*L=map(int,open(0).read().split());r=range(0,2*n,2);print(sum(((L[i]-L[j])**2+(L[i+1]-L[j+1])**2)**.5for i in r for j in r))/n)

Fixed submission:
from itertools import permutations
n = int(input())
div = 1
s = 0
for i in range(1, n + 1):
	div *= i
L = [list(map(int, input().split())) for _ in range(n)]
for x in permutations(range(n), n):
	s += sum(((L[i][0] - L[j][0]) ** 2 + (L[i][1] - L[j][1]) ** 2) ** .5 for i, j in zip(x, x[1:]))
print(s / div)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
	n, k = map(int, input().split())
	*a, = map(int, input().split())
	*f, = map(int, input().split())
	a.sort()
	f.sort(reverse=1)
	prod = [(y, x * y) for x, y in zip(a, f)]
	l = -1
	r = 10 ** 12
	while r - l > 1:
		m = (l + r) // 2
		s = sum(max(0, 0 - (m - p) // y) for y, p in prod)
		if s <= k:
			r = m
		else:
			l = m
	print(r)


if __name__ == "__main__":
	main()

Fixed submission:
def main():
	n, k = map(int, input().split())
	*a, = map(int, input().split())
	*f, = map(int, input().split())
	a.sort()
	f.sort(reverse=1)
	prod = [(y, x * y) for x, y in zip(a, f)]
	l = -1
	r = 10 ** 12
	while r - l > 1:
		m = (l + r) // 2
		s = sum(max(0, 0 - (m - p) // y) for y, p in prod)
		if s <= k:
			r = m
		else:
			l = m
	print(r)


if __name__ == "__main__":
	main()

Buggy python submission (verdict: Time Limit Exceeded):
from math import*
n,k=map(int,input().split())
*a,=map(int,input().split())
*f,=map(int,input().split())
ref=sorted([(x*y,y) for x,y in zip(sorted(a),sorted(f)[::-1])])[::-1]
l=-1
r=10**12
while r-l>1:
	m=(l+r)//2
	rest=k
	flg=1
	for z,y in ref:
		if m>=z:
			break
		if rest>=ceil((z-m)/y):
			rest-=ceil((z-m)/y)
		else:
			flg=0
			break
	if flg:
		r=m
	else:
		l=m
print(r)

Fixed submission:
def main():
	n, k = map(int, input().split())
	*a, = map(int, input().split())
	*f, = map(int, input().split())
	a.sort()
	f.sort(reverse=1)
	prod = [(y, x * y) for x, y in zip(a, f)]
	l = -1
	r = 10 ** 12
	while r - l > 1:
		m = (l + r) // 2
		s = sum(max(0, 0 - (m - p) // y) for y, p in prod)
		if s <= k:
			r = m
		else:
			l = m
	print(r)


if __name__ == "__main__":
	main()

Buggy python submission (verdict: Time Limit Exceeded):
from math import*
n,k=map(int,input().split())
*a,=map(int,input().split())
*f,=map(int,input().split())
ref=sorted([(x*y,y) for x,y in zip(sorted(a),sorted(f)[::-1])])[::-1]
l=-1
r=10**12
while r-l>1:
	m=(l+r)//2
	rest=k
	flg=1
	for z,y in ref:
		if m>=z:
			break
		if rest>=ceil((z-m)/y):
			rest-=ceil((z-m)/y)
		else:
			flg=0
			break
	if flg:
		r=m
	else:
		l=m
print(r)

Fixed submission:
def main():
	n, k = map(int, input().split())
	*a, = map(int, input().split())
	*f, = map(int, input().split())
	a.sort()
	f.sort(reverse=1)
	prod = [(y, x * y) for x, y in zip(a, f)]
	l = -1
	r = 10 ** 12
	while r - l > 1:
		m = (l + r) // 2
		s = sum(max(0, 0 - (m - p) // y) for y, p in prod)
		if s <= k:
			r = m
		else:
			l = m
	print(r)


if __name__ == "__main__":
	main()
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import*
from itertools import*
n,*L=map(int,open(0).read().split())
L.sort()
ans=0
for x,y in combinations(L,2):
	low=abs(x-y)
	high=x+y
	ans+=bisect_left(L,high)-bisect(L,low)
	if low<x<high:
		ans-=1
	if low<y<high:
		ans-=1
print(ans//3)

Fixed submission:
from bisect import*
from itertools import*
n,*L=map(int,open(0).read().split())
L.sort()
ans=0
for x,y in combinations(L,2):
	low=abs(x-y)
	high=x+y
	ans+=bisect_left(L,high)-bisect(L,low)
	if low<x<high:
		ans-=1
	if low<y<high:
		ans-=1
print(ans//3)
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import*;g=gcd(*map(int,input().split()));i=2;s={1}
while g>i:
	while g%i<1:g//=i;s|={i}
	i+=1
print(len(s)+(g>1))

Fixed submission:
def f(n):
  ret={1}
  for i in range(2,int(n**.5)+1):
    if n%i==0:
      ret.add(i)
      while n%i==0:
        n//=i
    else:pass
  if n:
    ret.add(n)
  return ret
a,b=map(int,input().split())
print(len(f(a)&f(b)))
Buggy python submission (verdict: Time Limit Exceeded):
def z_algorithm(s: str) -> list:
	n = len(s)
	Z = [0] * n
	Z[0] = n
	i, j = 1, 0
	while i < n:
		while i + j < n and s[j] == s[i + j]:
			j += 1
		Z[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < n and k + Z[k] < j:
			Z[i + k] = Z[k]
			k += 1
		i += k
		j -= k
	return Z


n = int(input())
s = input()
ans = 0
for i in range(n):
	z = z_algorithm(s[i:])
	t = max(min(j, z[j]) for j in range(n - i))
	ans = max(ans, t)
print(ans)


Fixed submission:
n=int(input())
s=input()
a=0
i=0
j=1
while j<n:
	if s[i:j] in s[j:]:
		a=max(a,len(s[i:j]))
		j+=1
	else:
		i+=1
	if i==j:
		i+=1
		j+=2
print(a)

Buggy python submission (verdict: Time Limit Exceeded):
def z_algorithm(s: str) -> list:
	n = len(s)
	Z = [0] * n
	Z[0] = n
	i, j = 1, 0
	while i < n:
		while i + j < n and s[j] == s[i + j]:
			j += 1
		Z[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < n and k + Z[k] < j:
			Z[i + k] = Z[k]
			k += 1
		i += k
		j -= k
	return Z


n = int(input())
s = input()
ans = 0
for i in range(n):
	z = z_algorithm(s[i:])
	t = max(min(j, z[j]) for j in range(n - i))
	ans = max(ans, t)
print(ans)

Fixed submission:
n=int(input())
s=input()
a=0
i=0
j=1
while j<n:
	if s[i:j] in s[j:]:
		a=max(a,len(s[i:j]))
		j+=1
	else:
		i+=1
	if i==j:
		i+=1
		j+=2
print(a)
Buggy python submission (verdict: Runtime Error):
a=1;c={"R":0,"G":0,"B":0}
for i in range(int(input())):
	a*=-~i
for i in input():
	s=sorted(c.values())
	c[i]+=1
	if c[i]>s[2]:
		pass
	elif c[i]>s[1]:
		a*=s[2]-s[1]
	else:
		a*=s[1]-s[0]
print(a%998244353)

Fixed submission:
s=input()
ans=0
t=c=""
for i in s:
	t+=i
	if c!=t:
		ans+=1
		c=t
		t=""
print(ans)

Buggy python submission (verdict: Runtime Error):
from bisect import bisect
from math import factorial
n = int(input())
R,B,G = [],[],[]
m,M,mid = [],[],[]
ans = factorial(n)
for i,j in enumerate(input()):
	if j=="R":
		R += [i]
	elif j=="B":
		B += [i]
	else:
		G += [i]
for r,b,g in zip(R,B,G):
	f,s,t = sorted([r,b,g])
	m += [f]
	M += [t]
	mid += [s]
for i,j in enumerate(mid):
	i = bisect(m,j) - i
	if i > 1:
		ans *= i
for i,j in enumerate(mid[::-1]):
	i = n - i - bisect(M,j)
	if i > 1:
		ans *= i
print(ans)

Fixed submission:
s=input()
ans=0
t=c=""
for i in s:
	t+=i
	if c!=t:
		ans+=1
		c=t
		t=""
print(ans)