Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import Fraction as F
mod=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
ret=1
cnt=0
for x in a:
	if x<0:
		b.append((-x,0))
	else:
		b.append((x,1))
b.sort(reverse=True)
p=-1
m=-1
for i in range(k):
	ret*=b[i][0]
	ret%=mod
	if b[i][1]==0:
		cnt+=1
		m=i
	else:
		p=i
if cnt%2==0:
	print(ret)
	exit()
ret1=-1
ret2=-1
f1=f2=0
if p!=-1:
	ret1=ret*pow(b[p][0],mod-2,mod)%mod
	for i in range(k,n):
		if b[i][1]==0:
			ret1*=b[i][0]
			ret1%=mod
			f1=1
			val1=F(b[i][0],b[p][0])
			break
if m!=-1:
	ret2=ret*pow(b[m][0],mod-2,mod)%mod
	for i in range(k,n):
		if b[i][1]==1:
			ret2*=b[i][0]
			ret2%=mod
			f2=1
			val2=F(b[i][0],b[m][0])
			break
if f1==0:
	ret1=-1
if f2==0:
	ret2=-1
if ret1==ret2==-1:
	ret=-1
	for i in range(k):
		ret*=b[-i-1][0]
	print(ret%mod)
elif ret1==-1:
	print(ret2)
elif ret2==-1:
	print(ret1)
else:
	if val1>val2:
		print(ret1)
	else:
		print(ret2)

Fixed submission:
from fractions import Fraction as F
mod=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
ret=1
cnt=0
for x in a:
	if x<0:
		b.append((-x,0))
	else:
		b.append((x,1))
b.sort(reverse=True)
p=-1
m=-1
for i in range(k):
	ret*=b[i][0]
	ret%=mod
	if b[i][1]==0:
		cnt+=1
		m=i
	else:
		p=i
if cnt%2==0:
	print(ret)
	exit()
ret1=-1
ret2=-1
f1=f2=0
if p!=-1:
	ret1=ret*pow(b[p][0],mod-2,mod)%mod
	for i in range(k,n):
		if b[i][1]==0:
			ret1*=b[i][0]
			ret1%=mod
			f1=1
			val1=F(b[i][0],b[p][0])
			break
if m!=-1:
	ret2=ret*pow(b[m][0],mod-2,mod)%mod
	for i in range(k,n):
		if b[i][1]==1:
			ret2*=b[i][0]
			ret2%=mod
			f2=1
			val2=F(b[i][0],b[m][0])
			break
if f1==0:
	ret1=-1
if f2==0:
	ret2=-1
if ret1==ret2==-1:
	ret=-1
	for i in range(k):
		ret*=b[-i-1][0]
		ret%=mod
	print(ret%mod)
elif ret1==-1:
	print(ret2)
elif ret2==-1:
	print(ret1)
else:
	if val1>val2:
		print(ret1)
	else:
		print(ret2)
Buggy python submission (verdict: Time Limit Exceeded):
from random import randint
from time import time
t1=time()

d=int(input())
c=list(map(int,input().split()))
s=[]
for i in range(d):
	r=list(map(int,input().split()))
	s.append(r)

def score(T):
	last=[0]*26
	happy=0
	for i in range(d):
		last[T[i]-1]=i+1
		happy+=s[i][T[i]-1]
		for j in range(26):
			happy-=(i+1-last[j])*c[j]
	return happy

t=[]
for i in range(d):
	t.append(i%26+1)

t2=time()
while t2-t1<1.9:
	tt=t.copy()
	tt[randint(1,d)-1]=randint(1,26)
	if score(tt)>score(t):
		t=tt.copy()
	t2=time()
for x in t:
	print(x)

Fixed submission:
d=int(input())
c=list(map(int,input().split()))
s=[]
for i in range(d):
	r=list(map(int,input().split()))
	s.append(r)
for i in range(d):
	print(i%26+1)

Buggy python submission (verdict: Runtime Error):
for i in range(d):
	print(i%26+1)

Fixed submission:
d=int(input())
c=list(map(int,input().split()))
s=[]
for i in range(d):
	r=list(map(int,input().split()))
	s.append(r)
for i in range(d):
	print(i%26+1)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
	mod=10**9+7
	k=int(input())
	s=input()
	n=len(s)
	fac=[1]
	for i in range(k+n+1):
		fac.append(fac[-1]*(i+1)%mod)
	def c(x,y):
		r=fac[y]*fac[x-y]%mod
		return fac[x]*pow(r,mod-2,mod)%mod
	ans=0
	for i in range(n,k+n+1):#iはSnの位置
		r=c(i-1,n-1)*pow(25,i-n,mod)*pow(26,n+k-i,mod)%mod
		ans+=r
		ans%=mod
	print(ans)
if __name__ == '__main__':
	main()

Fixed submission:
def main():
	mod=10**9+7
	k=int(input())
	s=input()
	n=len(s)
	fac=[1]
	for i in range(k+n+1):
		fac.append(fac[-1]*(i+1)%mod)
	def c(x,y):
		r=fac[y]*fac[x-y]%mod
		return fac[x]*pow(r,mod-2,mod)%mod
	ans=0
	for i in range(n,k+n+1):#iはSnの位置
		r=c(i-1,n-1)*pow(25,i-n,mod)*pow(26,n+k-i,mod)%mod
		ans+=r
		ans%=mod
	print(ans)
if __name__ == '__main__':
	main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
	a,b,c,d=map(int,input().split())
	mod=998244353
	dp=[[0 for _ in range(d)]for _ in range(c)]
	dp[a-1][b-1]=1
	for i in range(a-1,c):
		for j in range(b-1,d):
			if i!=a-1:
				dp[i][j]+=dp[i-1][j]*(j+1)%mod
			if j!=b-1:
				dp[i][j]+=dp[i][j-1]*(i+1)%mod
			if i!=a-1 and j!=b-1:
				dp[i][j]-=dp[i-1][j-1]*i*j%mod
			dp[i][j]%=mod
	print(dp[-1][-1])

if __name__ == '__main__':
	main()

Fixed submission:
def main():
	a,b,c,d=map(int,input().split())
	mod=998244353
	dp=[[0 for _ in range(d)]for _ in range(c)]
	dp[a-1][b-1]=1
	for i in range(a-1,c):
		for j in range(b-1,d):
			if i!=a-1:
				dp[i][j]+=dp[i-1][j]*(j+1)%mod
			if j!=b-1:
				dp[i][j]+=dp[i][j-1]*(i+1)%mod
			if i!=a-1 and j!=b-1:
				dp[i][j]-=dp[i-1][j-1]*i*j%mod
			dp[i][j]%=mod
	print(dp[-1][-1])

if __name__ == '__main__':
	main()
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
if n==0:
	if a[0]==1:
		print(2/0)
		exit()
	else:
		while True:
			print(98236874184)
M=[1]
now=2
for i in range(n):
	M.append(now)
	now-=a[i+1]
	if now<=10**29:
		now*=2
now=a[-1]
for i in range(n):
	M[-i-1]=min(now,M[-i-1])
	now=min(now,M[-i-1])
	now+=a[-i-2]
if a[0]!=0:
	print(-1)
	exit()
for i in range(n+1):
	if M[i]<=0:
		print(-1)
		exit()
print(sum(M))


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
if n==0:
	if a[0]==1:
		print(1)
		exit()
	else:
		print(-1)
		exit()
M=[1]
now=2
r=sum(a)
for i in range(n):
	M.append(now)
	now-=a[i+1]
	if now<0:
		print(-1)
		exit()
	elif now<r:
		now*=2
now=a[-1]
for i in range(n):
	M[-i-1]=min(now,M[-i-1])
	now=min(now,M[-i-1])
	now+=a[-i-2]
if a[0]!=0:
	print(-1)
	exit()
for i in range(n+1):
	if M[i]<=0:
		print(-1)
		exit()
print(sum(M))
Buggy python submission (verdict: Time Limit Exceeded):
t=int(input())
def f(x):
	if x<=1:
		return D*x
	ret=D*x

	if x%2==0:
		ret=min(ret,f(x//2)+A)
	else:
		ret=min(ret,f(x//2)+A+D,f(x//2+1)+A+D)
	
	if x%3==0:
		ret=min(ret,f(x//3)+B)
	elif x%3==1:
		ret=min(ret,f(x//3)+B+D)
	else:
		ret=min(ret,f(x//3+1)+B+D)

	if x%5<=2:
		ret=min(ret,f(x//5)+C+D*(x%5))
	else:
		ret=min(ret,f(x//5+1)+C+D*(5-x%5))
	return ret
for _ in range(t):
	n,A,B,C,D=map(int,input().split())
	print(f(n))



Fixed submission:
memo=dict()
t=int(input())
def f(x):
	if x in memo:
		return memo[x]
	if x<=1:
		return D*x
	ret=D*x

	if x%2==0:
		ret=min(ret,f(x//2)+A)
	else:
		ret=min(ret,f(x//2)+A+D,f(x//2+1)+A+D)
	
	if x%3==0:
		ret=min(ret,f(x//3)+B)
	elif x%3==1:
		ret=min(ret,f(x//3)+B+D)
	else:
		ret=min(ret,f(x//3+1)+B+D)

	if x%5<=2:
		ret=min(ret,f(x//5)+C+D*(x%5))
	else:
		ret=min(ret,f(x//5+1)+C+D*(5-x%5))
	memo[x]=ret
	return ret
for _ in range(t):
	memo=dict()
	n,A,B,C,D=map(int,input().split())
	print(f(n))
Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
n=int(input())
cnt=[]
for i in range(n):
	s=input().rstrip()
	l=s.count("(")
	r=s.count(")")
	minus=0
	now=0
	for j in range(len(s)):
		if s[j]=="(":
			now+=1
		else:
			now-=1
			minus=min(minus,now)
	cnt.append((l,r,s,minus))
cnt.sort(key=lambda x:x[1]-x[0])
plus=[]
minus=[]
for x in cnt:
	if x[0]-x[1]>=0:
		plus.append(x)
	else:
		minus.append(x)
plus.sort(key=lambda x:-x[3])
minus.sort(key=lambda x:-(x[0]-x[1])-x[3])
l=r=0
for x in plus:
	for i in range(len(x[2])):
		if x[2][i]=="(":
			l+=1
		else:
			r+=1
		if l<r:
			print("No")
			exit()
for x in minus:
	for i in range(len(x[2])):
		if x[2][i]=="(":
			l+=1
		else:
			r+=1
		if l<r:
			print("No")
			exit()
if l==r:
	print("Yes")
else:
	print("No")


Fixed submission:
mod=998244353
n,m,k=map(int,input().split())
fac=[1]
for i in range(n):
	fac.append(fac[-1]*(i+1)%mod)
ans=0
for x in range(k+1):
	rev=pow(fac[x]*fac[n-1-x]%mod,mod-2,mod)
	r=fac[n-1]*rev%mod*m*pow(m-1,n-x-1,mod)%mod
	ans+=r
	ans%=mod
print(ans)
Buggy python submission (verdict: Runtime Error):
n,m,q=map(int,input().split())
abcd=[]
for _ in range(q):
	a,b,c,d=map(int,input().split())
	abcd.append((a,b,c,d))
ans=0
p=[]
sys.setrecursionlimit(10**6)
def dfs(x):
	if len(x)==n:
		p.append(x)
	else:
		for i in range(m-x[-1]+1):
			dfs(x+[x[-1]+i])
dfs([1])
# import itertools
# p=itertools.combinations_with_replacement(range(1,m+1),n)
for x in p:
	r=0
	for i in range(q):
		if x[abcd[i][1]-1]-x[abcd[i][0]-1]==abcd[i][2]:
			r+=abcd[i][3]
	ans=max(ans,r)
print(ans)

Fixed submission:
n,m,q=map(int,input().split())
abcd=[]
for _ in range(q):
	a,b,c,d=map(int,input().split())
	abcd.append((a,b,c,d))
ans=0
import itertools
p=itertools.combinations_with_replacement(range(1,m+1),n)
for x in p:
	r=0
	for i in range(q):
		if x[abcd[i][1]-1]-x[abcd[i][0]-1]==abcd[i][2]:
			r+=abcd[i][3]
	ans=max(ans,r)
print(ans)

Buggy python submission (verdict: Runtime Error):
n,m,q=map(int,input().split())
abcd=[]
for _ in range(q):
	a,b,c,d=map(int,input().split())
	abcd.append((a,b,c,d))
ans=0
p=[]
sys.setrecursionlimit(10**6)
def dfs(x):
	if len(x)==n:
		p.append(x)
	else:
		for i in range(n-x[-1]+1):
			dfs(x+[x[-1]+i])
dfs([1])
# import itertools
# p=itertools.combinations_with_replacement(range(1,m+1),n)
for x in p:
	r=0
	for i in range(q):
		if x[abcd[i][1]-1]-x[abcd[i][0]-1]==abcd[i][2]:
			r+=abcd[i][3]
	ans=max(ans,r)
print(ans)

Fixed submission:
n,m,q=map(int,input().split())
abcd=[]
for _ in range(q):
	a,b,c,d=map(int,input().split())
	abcd.append((a,b,c,d))
ans=0
import itertools
p=itertools.combinations_with_replacement(range(1,m+1),n)
for x in p:
	r=0
	for i in range(q):
		if x[abcd[i][1]-1]-x[abcd[i][0]-1]==abcd[i][2]:
			r+=abcd[i][3]
	ans=max(ans,r)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,a,b=map(int,input().split())
mod=10**9+7
ans=pow(2,n,mod)-1+mod*2
def c(x,y):
	p=1
	for i in range(x-y+1,x+1):
		p*=i
		p%=mod
	q=1
	for i in range(2,y+1):
		q*=i
		p%=mod
	return pow(q,mod-2,mod)*p%mod
r=ans-c(n,a)-c(n,b)
print(r%mod)

Fixed submission:
n,a,b=map(int,input().split())
mod=10**9+7
ans=pow(2,n,mod)-1+mod*2
def c(x,y):
	p=1
	for i in range(x-y+1,x+1):
		p*=i
		p%=mod
	for i in range(2,y+1):
		p*=pow(i,mod-2,mod)
		p%=mod
	return p
r=ans-c(n,a)-c(n,b)
print(r%mod)
Buggy python submission (verdict: Time Limit Exceeded):
h,n=map(int,input().split())
ab=[]
p=0
for i in range(n):
	a,b=map(int,input().split())
	p=max(p,a)
	ab.append([a,b])
dp=[[10**9]*(p+1+h) for _ in range(n+1)]
for i in range(n+1):
	dp[i][0]=0

for i in range(n):
	for j in range(p+h):
		if j+1-ab[i][0]>=0:
			dp[i+1][j+1]=min(dp[i][j+1],dp[i+1][j+1-ab[i][0]]+ab[i][1])
		else:
			dp[i+1][j+1]=dp[i][j+1]
ans=10**10
for i in range(h,h+p):
	ans=min(dp[n][i],ans)
print(ans)

Fixed submission:
h,n=map(int,input().split())
ab=[]
p=0
for i in range(n):
	a,b=map(int,input().split())
	p=max(p,a)
	ab.append([a,b])
dp=[[10**9]*(p+1+h) for _ in range(n+1)]
for i in range(n+1):
	dp[i][0]=0

for i in range(n):
	for j in range(p+h):
		if j+1-ab[i][0]>=0:
			dp[i+1][j+1]=min(dp[i][j+1],dp[i+1][j+1-ab[i][0]]+ab[i][1])
		else:
			dp[i+1][j+1]=dp[i][j+1]
ans=10**10
for i in range(h,h+p):
	ans=min(dp[n][i],ans)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
ab=[]
h,n=map(int,input().split())
dp=[10**9]*(h+10001)
dp[0]=0
for i in range(n):
	x,y=map(int,input().split())
	ab.append([x,y])
for i in range(1,h+10001):
	for j in range(n):
		if i>=ab[j][0]:
			dp[i]=min(dp[i],dp[i-ab[j][0]]+ab[j][1])
ans=min(dp[h:])
print(ans)

Fixed submission:
h,n=map(int,input().split())
ab=[]
p=0
for i in range(n):
	a,b=map(int,input().split())
	p=max(p,a)
	ab.append([a,b])
dp=[[10**9]*(p+1+h) for _ in range(n+1)]
for i in range(n+1):
	dp[i][0]=0

for i in range(n):
	for j in range(p+h):
		if j+1-ab[i][0]>=0:
			dp[i+1][j+1]=min(dp[i][j+1],dp[i+1][j+1-ab[i][0]]+ab[i][1])
		else:
			dp[i+1][j+1]=dp[i][j+1]
ans=10**10
for i in range(h,h+p):
	ans=min(dp[n][i],ans)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
def c(i,j):
	cnt=0
	for k in range(n):
		p=str(k+1)
		if p[0]==str(i) and p[-1]==str(j):
			cnt+=1
	return cnt
ans=0
for i in range(10):
	for j in range(10):
		ans+=c(i,j)*c(j,i)
print(ans)

Fixed submission:
n=int(input())
c=[[0]*10 for _ in range(10)]
for i in range(n):
	s=str(i+1)
	c[int(s[0])][int(s[-1])]+=1
ans=0
for i in range(10):
	for j in range(10):
		ans+=c[i][j]*c[j][i]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import copy
n=int(input())
a=list(map(int,input().split()))
b=copy.copy(a)
mod=10**9+7
lcm=[0]*max(a)
for i in range(n):
	for j in range(2,int(a[i]**0.5)+1):
		cnt=0
		while a[i]%j==0:
			a[i]//=j
			cnt+=1
		lcm[j-1]=max(lcm[j-1],cnt)
	if a[i]!=1:
		lcm[a[i]-1]=max(lcm[a[i]-1],1)
an=1
for i in range(len(lcm)):
	an*=pow(i+1,lcm[i],mod)
	an%=mod
ans=0
for i in range(n):
	ans+=an*pow(b[i],mod-2,mod)
	ans%=mod
print(ans)


Fixed submission:
import copy
n=int(input())
a=list(map(int,input().split()))
b=copy.copy(a)
mod=10**9+7
lcm=[0]*max(a)
for i in range(n):
	for j in range(2,int(a[i]**0.5)+1):
		cnt=0
		while a[i]%j==0:
			a[i]//=j
			cnt+=1
		lcm[j-1]=max(lcm[j-1],cnt)
	if a[i]!=1:
		lcm[a[i]-1]=max(lcm[a[i]-1],1)
an=1
for i in range(len(lcm)):
	an*=pow(i+1,lcm[i],mod)
	an%=mod
ans=0
for i in range(n):
	ans+=an*pow(b[i],mod-2,mod)
	ans%=mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
ans=0
mod=10**9+7
lc=a[0]
from fractions import gcd
for i in range(n-1):
	lc=lc*a[i+1]//gcd(lc,a[i+1])
for i in range(n):
	ans+=lc//a[i]
	ans%=mod
print(ans)

Fixed submission:
import copy
n=int(input())
a=list(map(int,input().split()))
b=copy.copy(a)
mod=10**9+7
lcm=[0]*max(a)
for i in range(n):
	for j in range(2,int(a[i]**0.5)+1):
		cnt=0
		while a[i]%j==0:
			a[i]//=j
			cnt+=1
		lcm[j-1]=max(lcm[j-1],cnt)
	if a[i]!=1:
		lcm[a[i]-1]=max(lcm[a[i]-1],1)
an=1
for i in range(len(lcm)):
	an*=pow(i+1,lcm[i],mod)
	an%=mod
ans=0
for i in range(n):
	ans+=an*pow(b[i],mod-2,mod)
	ans%=mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
ans=0
mod=10**9+7
lc=a[0]
from fractions import gcd
for i in range(n-1):
	lc=lc*a[i+1]//gcd(lc,a[i+1])
for i in range(n):
	ans+=lc//a[i]
	ans%=mod
print(ans)

Fixed submission:
import copy
n=int(input())
a=list(map(int,input().split()))
b=copy.copy(a)
mod=10**9+7
lcm=[0]*max(a)
for i in range(n):
	for j in range(2,int(a[i]**0.5)+1):
		cnt=0
		while a[i]%j==0:
			a[i]//=j
			cnt+=1
		lcm[j-1]=max(lcm[j-1],cnt)
	if a[i]!=1:
		lcm[a[i]-1]=max(lcm[a[i]-1],1)
an=1
for i in range(len(lcm)):
	an*=pow(i+1,lcm[i],mod)
	an%=mod
ans=0
for i in range(n):
	ans+=an*pow(b[i],mod-2,mod)
	ans%=mod
print(ans)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=list(map(int,input().split()))
from math import gcd
for i in range(n):
	a[i]//=2
from copy import copy
b=copy(a)
while True:
	i=0
	for i in range(n):
		if b[i]%2==0:
			b[i]//=2
		else:
			break
	if i==0:
		break
	else:
		print(0)
		exit()
a_gcd=a[0]
for i in range(1,n):
	a_gcd=a_gcd*a[i]//gcd(a_gcd,a[i])
print((m+a_gcd)//(a_gcd*2))

Fixed submission:
n,m=map(int,input().split())
a=list(map(int,input().split()))
from fractions import gcd
for i in range(n):
	a[i]//=2
from copy import copy
b=copy(a)
c=[]

for i in range(n):
	cnt=0
	while b[i]%2==0:
		cnt+=1
		b[i]//=2
	c.append(cnt)
for i in range(n-1):
	if c[i]!=c[i+1]:
		print(0)
		exit()

a_gcd=a[0]
for i in range(1,n):
	a_gcd=a_gcd*a[i]//gcd(a_gcd,a[i])
print((m+a_gcd)//(a_gcd*2))

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=list(map(int,input().split()))
A=a[0]
B=a[0]//2
from math import gcd
for i in range(n):
	A=A*a[i]//gcd(A,a[i])
	B=B*(a[i]//2)//gcd(B,a[i]//2)
	B//=A
m-=B
print(m//A+1)

Fixed submission:
n,m=map(int,input().split())
a=list(map(int,input().split()))
from fractions import gcd
for i in range(n):
	a[i]//=2
from copy import copy
b=copy(a)
c=[]

for i in range(n):
	cnt=0
	while b[i]%2==0:
		cnt+=1
		b[i]//=2
	c.append(cnt)
for i in range(n-1):
	if c[i]!=c[i+1]:
		print(0)
		exit()

a_gcd=a[0]
for i in range(1,n):
	a_gcd=a_gcd*a[i]//gcd(a_gcd,a[i])
print((m+a_gcd)//(a_gcd*2))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
cnt=[]
for i in range(60):
	p=0
	for j in range(n):
		if a[j]%2==1:
			p+=1
		a[j]//=2
	cnt.append(p)
ans=0
for i in range(60):
	ans+=(n-cnt[i])*cnt[i]*(2**i)
	ans%=10**9+7
print(ans)

Fixed submission:
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
cnt=[]
q=set()
for i in range(n):
	q.add(i)
for i in range(60):
	p=0
	l=[]
	for j in q:
		if a[j]%2==1:
			p+=1
		a[j]//=2
		if a[j]==0:
			l.append(j)
	for j in range(len(l)):
		q.remove(l[j])
	cnt.append(p)
ans=0
for i in range(60):
	ans+=(n-cnt[i])*cnt[i]*(2**i)
	ans%=mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=input()
ans=0
for i in range(1000):
	i=str(i)
	i=(3-len(i))*"0"+i
	r=0
	for j in range(n):
		if s[j]==i[r]:
			r+=1
		if r==3:
			break
	if r==3:
		ans+=1
print(ans)

Fixed submission:
n=int(input())
s=input()
ans=0
for i in range(1000):
	i=str(i)
	i=(3-len(i))*"0"+i
	r=0
	for j in range(n):
		if s[j]==i[r]:
			r+=1
		if r==3:
			break
	if r==3:
		ans+=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import time
t1=time.time()
n=int(input())
kind=[0]*n
aa=[]
bb=[]
for _ in range(n-1):
	a,b=map(int,input().split())
	aa.append(a)
	bb.append(b)
	kind[a-1]+=1
	kind[b-1]+=1
print(max(kind))
p=[[set()]for _ in range(n)]
for i in range(n-1):
	t2=time.time()
	if t2-t1<=0.5:
		for j in range(max(kind),0,-1):
			if j not in p[aa[i]-1][0] and j not in p[bb[i]-1][0]:
				p[aa[i]-1][0].add(j)
				p[bb[i]-1][0].add(j)
				print(j)
				break
	else:
		for j in range(1,max(kind)+1):
			if j not in p[aa[i]-1][0] and j not in p[bb[i]-1][0]:
				p[aa[i]-1][0].add(j)
				p[bb[i]-1][0].add(j)
				print(j)
				break




Fixed submission:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**5*2)
n=int(input())
child=[[]for _ in range(n)]
color=[-1]*(n-1)
#adj は(子供,辺番号)
for i in range(n-1):
	a,b=map(int,input().split())
	child[a-1].append((b-1,i))
#x=現在見ている頂点
#r=その頂点の親とその頂点の間のnodeの色
def f(now,parent_node):
	color_num=1
	for i,j in child[now]:
		if color_num==parent_node:
			color_num+=1
		color[j]=color_num 
		f(i,color_num)
		color_num+=1
f(0,0)
print(max(color))
for x in color:
	print(x)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
kind=[0]*n
aa=[]
bb=[]
for _ in range(n-1):
	a,b=map(int,input().split())
	aa.append(a)
	bb.append(b)
	kind[a-1]+=1
	kind[b-1]+=1
print(max(kind))
p=[[set()]for _ in range(n)]
for i in range(n-1):
	flag=False
	for j in range(1,max(kind)+1):
		if flag==True:
			break
		if j not in p[aa[i]-1][0] and j not in p[bb[i]-1][0]:
			p[aa[i]-1][0].add(j)
			p[bb[i]-1][0].add(j)
			flag=True
			print(j)



Fixed submission:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**5*2)
n=int(input())
child=[[]for _ in range(n)]
color=[-1]*(n-1)
#adj は(子供,辺番号)
for i in range(n-1):
	a,b=map(int,input().split())
	child[a-1].append((b-1,i))
#x=現在見ている頂点
#r=その頂点の親とその頂点の間のnodeの色
def f(now,parent_node):
	color_num=1
	for i,j in child[now]:
		if color_num==parent_node:
			color_num+=1
		color[j]=color_num 
		f(i,color_num)
		color_num+=1
f(0,0)
print(max(color))
for x in color:
	print(x)
Buggy python submission (verdict: Runtime Error):
p=1
cnt=1
h,w,k=map(int,input().split())
for i in range(h):
	s=input()
	if s.count("#")==1:
		for j in range(w):
			a.append(p)
		p+=1
		for _ in range(cnt):
			print(*a)
		cnt=1
	elif s.count("#")==0:
		cnt+=1
	else:
		a=[]
		itigo=0
		for j in range(w):
			if s[j]=="#" and itigo==True:
				p+=1
				a.append(p)
			elif s[j]=="#":
				itigo=True
				a.append(p)
			else:
				a.append(p)
		for _ in range(cnt):
			print(*a)
		cnt=1
		p+=1
for i in range(cnt-1):
	print(*a)







Fixed submission:
p=1
cnt=1
h,w,k=map(int,input().split())
for i in range(h):
	s=input()
	if s.count("#")==1:
		a=[]
		for j in range(w):
			a.append(p)
		p+=1
		for _ in range(cnt):
			print(*a)
		cnt=1
	elif s.count("#")==0:
		cnt+=1
	else:
		a=[]
		itigo=0
		for j in range(w):
			if s[j]=="#" and itigo==True:
				p+=1
				a.append(p)
			elif s[j]=="#":
				itigo=True
				a.append(p)
			else:
				a.append(p)
		for _ in range(cnt):
			print(*a)
		cnt=1
		p+=1
for i in range(cnt-1):
	print(*a)
Buggy python submission (verdict: Time Limit Exceeded):
n,w=map(int,input().split())
ab=[]
w-=1
take=[]
dp=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
	a,b=map(int,input().split())
	ab.append([a,b])
	for j in range(w):
		if j+1-a>=0:
			dp[i+1][j+1]=max(dp[i][j+1],dp[i][j+1-a]+b)
		else:
			dp[i+1][j+1]=dp[i][j+1]
k=w
take=[]
for i in range(n):
	if dp[n-i-1][w]!=dp[n-i][w]:
		w-=ab[n-i-1][0]
		take.append(n-i-1)
take=set(take)
ans=0
for i in range(n):
	if i not in take:
		ans=max(ans,ab[i][1])
print(dp[-1][-1]+ans)




Fixed submission:
n,w=map(int,input().split())
ab=[]
w-=1
take=[]
dp=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
	a,b=map(int,input().split())
	ab.append([a,b])
	for j in range(w):
		if j+1-a>=0:
			dp[i+1][j+1]=max(dp[i][j+1],dp[i][j+1-a]+b)
		else:
			dp[i+1][j+1]=dp[i][j+1]
k=w
take=[]
for i in range(n):
	if dp[n-i-1][w]!=dp[n-i][w]:
		w-=ab[n-i-1][0]
		take.append(n-i-1)
take=set(take)
ans=0
for i in range(n):
	if i not in take:
		ans=max(ans,ab[i][1])
print(dp[-1][-1]+ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
d=list(map(int,input().split()))
mod=998244353
d.sort()

if n==1:
	if d[0]==0:
		print(1)
		exit()
	else:
		print(0)
		exit()
elif n==2:
	if d==[0,1]:
		print(1)
		exit()
	else:
		print(0)
		exit()
if d[0]!=0 or d[1]==0:
	print(0)
	exit()
for i in range(n-1):
	if d[i+1]>d[i]+1:
		print(0)
		exit()
p=[]
cnt=1
for i in range(1,n-1):
	if d[i]==d[i+1]:
		cnt+=1
	elif d[i+1]>=d[i]+1:
		p.append(cnt)
		cnt=1
p.append(cnt)
ans=1
for i in range(len(p)-1):
	ans*=p[i]**p[i+1]
	ans%=mod
print(ans,2/0)

Fixed submission:
from collections import Counter
mod=998244353
n=int(input())
d=list(map(int,input().split()))
q=Counter(d)
if q[0]!=1 or d[0]!=0:
	print(0)
	exit()
ans=1
for i in range(1,max(d)+1):
    ans*=pow(q[i-1],q[i],mod)
    ans%=mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
f.sort()
a.sort()
a.reverse()
l=0
r=10**12+1
import math
while r-l>1:
	mid=(l+r)/2
	cnt=0
	for i in range(n):
		if a[i]*f[i]>mid:
			cnt+=a[i]-mid//f[i]
	if cnt<=k:
		r=mid
	else:
		l=mid
print(int(r))



Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
f.sort()
a.sort()
a.reverse()
l=0
r=10**12+1
import math
while r-l>1:
	mid=(l+r)/2
	cnt=0
	for i in range(n):
		if a[i]*f[i]>mid:
			cnt+=a[i]-mid//f[i]
	if cnt<=k:
		r=mid
	else:
		l=mid
print(int(r))
Buggy python submission (verdict: Time Limit Exceeded):
def warshall_floyd(d):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j]=min(d[i][j],d[i][k]+d[k][j])
	return d
n,m,l=map(int,input().split())
d=[[10**10 for _ in range(n)]for _ in range(n)]
for i in range(n):
	d[i][i]=0
for i in range(m):
	a,b,c=map(int,input().split())
	d[a-1][b-1]=c
	d[b-1][a-1]=c
p=[[10**5 for _ in range(n)]for _ in range(n)]
d=warshall_floyd(d)
for i in range(n):
	for j in range(n):
		if d[i][j]<=l:
			p[i][j]=1
p=warshall_floyd(p)
q=int(input())
for i in range(q):
	s,t=map(int,input().split())
	if p[s-1][t-1]==10**5:
		print(-1)
		continue
	print(p[s-1][t-1]-1)



Fixed submission:
def warshall_floyd(d):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j]=min(d[i][j],d[i][k]+d[k][j])
	return d
n,m,l=map(int,input().split())
d=[[10**10 for _ in range(n)]for _ in range(n)]
for i in range(n):
	d[i][i]=0
for i in range(m):
	a,b,c=map(int,input().split())
	d[a-1][b-1]=c
	d[b-1][a-1]=c
p=[[10**5 for _ in range(n)]for _ in range(n)]
d=warshall_floyd(d)
for i in range(n):
	for j in range(n):
		if d[i][j]<=l:
			p[i][j]=1
p=warshall_floyd(p)
q=int(input())
for i in range(q):
	s,t=map(int,input().split())
	if p[s-1][t-1]==10**5:
		print(-1)
		continue
	print(p[s-1][t-1]-1)