Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda: sys.stdin.readline().rstrip()
m=2**150-1
n=int(input())
ss=[input()[::-1]for _ in range(n)]
ss.sort(key=len)
d={}
ans=0
for s in ss:
  a=ord(s[-1])-97
  r=1
  h=0
  y=[0]*26
  for t in s[:-1]:
    b=ord(t)-97
    if h in d:
      for i in range(26):y[i]+=d[h][i]
    ans+=y[b]
    y[b]=0
    h=(h*71+b+135)&m
  ans+=y[a]
  if h not in d:d[h]=[0]*26
  d[h][a]+=1
print(ans)

Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip()
m=2**150-1
n=int(input())
ss=[input()[::-1]for _ in range(n)]
ss.sort(key=len)
d={}
ans=0
for s in ss:
  a=ord(s[-1])-97
  r=1
  h=0
  y=[0]*26
  for t in s[:-1]:
    b=ord(t)-97
    if h in d:
      for i in range(26):y[i]+=d[h][i]
    ans+=y[b]
    y[b]=0
    h=(h*71+b+135)&m
  ans+=y[a]
  if h not in d:d[h]=[0]*26
  d[h][a]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from random import randint
mod=(1<<150)-1#1370757747362922367
rr=randint(2,mod-2)
n=int(input())
ss=[input()[::-1]for _ in range(n)]
ss.sort(key=len)
d={}
ans=0
for s in ss:
  a=ord(s[-1])-97
  r=1
  h=0
  y=[0]*26
  for t in s[:-1]:
    b=ord(t)-97
    if h in d:
      for i in range(26):y[i]+=d[h][i]
    ans+=y[b]
    y[b]=0
    h=(h*71+b+135)&mod
    #h=(h+b*r)%mod
    #r=r*rr%mod
  ans+=y[a]
  if h not in d:d[h]=[0]*26
  d[h][a]+=1
print(ans)

Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip()
m=2**150-1
n=int(input())
ss=[input()[::-1]for _ in range(n)]
ss.sort(key=len)
d={}
ans=0
for s in ss:
  a=ord(s[-1])-97
  r=1
  h=0
  y=[0]*26
  for t in s[:-1]:
    b=ord(t)-97
    if h in d:
      for i in range(26):y[i]+=d[h][i]
    ans+=y[b]
    y[b]=0
    h=(h*71+b+135)&m
  ans+=y[a]
  if h not in d:d[h]=[0]*26
  d[h][a]+=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
k=int(input())
if k%2==0:exit(print(-1))
ans=0
x=k
for i in range(10**9):
  while x%10!=7:x+=k
  x//=10
  if x==0:exit(print(i+1))

Fixed submission:
import time
start=time.time()
k=int(input())
if k%2==0:exit(print(-1))
ans=0
x=k
for i in range(10**9):
  while x%10!=7:
    x+=k
    if time.time()-start>=1.9:exit(print(-1))
  x//=10
  if x==0:exit(print(i+1))
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[1]
for i in range(k):b[0]*=a[i]
for i in range(k,n):
  b.append(b[-1]*a[i]//a[i-k])
for i in range(len(b)-1):
  if b[i]<b[i+1]:print('Yes')
  else:print('No')

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(k,n):
  if a[i-k]<a[i]:print('Yes')
  else:print('No')
Buggy python submission (verdict: Runtime Error):
# BIT使ってC問題ちゃんとやろうとしたけど1時間かけて無を生成したので諦める。ぷえwwwww
from random import randint
d=int(input())
c=list(map(int,input().split()))
s=[list(map(int,input().split()))for _ in range(d)]
for i in range(d):s.append(s[i][:])
for i in range(d):s.append(s[i][:])
def xyz():
  start=randint(0,d-1)
  ans=[0]*d
  score=0
  for i in range(start,start+d,26):
    dd=set()
    uu=set()
    h=[]
    for j in range(i,i+26):
      for k in range(26):
        h.append([s[j][k],j,k])
    h.sort(reverse=1)
    for t,j,k in h:
      if j in dd or k in uu:continue
      score+=t
      ans[j]=k
      dd.add(j)
      uu.add(k)
  return [score,ans]
score,ans=xyz()
for i in range(40):
  ss,aa=xyz()
  if ss>score:
    score,ans=ss,aa
for i in ans:print(i+1)

Fixed submission:
d=int(input())
c=list(map(int,input().split()))
s=[list(map(int,input().split()))for _ in range(d)]
for i in range(d):print(i%26+1)
Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
d=int(input())
c=list(map(int,input().split()))
s=[list(map(int,input().split()))for _ in range(d)]
t=[int(input())for _ in range(d)]
m=int(input())
dq=[list(map(int,input().split()))for _ in range(m)]
x=[[0]for _ in range(26)]
ans=0
for i in range(d):
  v=t[i]-1
  ans+=s[i][v]-c[v]*(i-x[v][-1]+1)*(i-x[v][-1])//2
  x[v].append(i+1)
for i in range(26):
  ans-=c[i]*(d+1-x[i][-1])*(d-x[i][-1])//2
  x[i].append(d+1)
print(ans)

Fixed submission:
d=int(input())
c=list(map(int,input().split()))
s=[list(map(int,input().split()))for _ in range(d)]
t=[int(input())-1 for _ in range(d)]
x=[0]*26
ans=0
for i in range(d):
  v=t[i]
  ans+=s[i][v]
  for j in range(26):
    if j==v:x[j]=0
    else:x[j]+=1
    ans-=c[j]*x[j]
  print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
from bisect import bisect_left,insort_left
from numba import njit

@njit
def main():
  d=int(input())
  c=list(map(int,input().split()))
  s=[list(map(int,input().split()))for _ in range(d)]
  t=[int(input())for _ in range(d)]
  m=int(input())
  dq=[list(map(int,input().split()))for _ in range(m)]
  x=[[0]for _ in range(26)]
  ans=0
  for i in range(d):
    v=t[i]-1
    ans+=s[i][v]-c[v]*(i-x[v][-1]+1)*(i-x[v][-1])//2
    x[v].append(i+1)
  for i in range(26):
    ans-=c[i]*(d+1-x[i][-1])*(d-x[i][-1])//2
    x[i].append(d+1)
  for dd,q in dq:
    p=t[dd-1]
    t[dd-1]=q
    ans-=s[dd-1][p-1]
    ans+=s[dd-1][q-1]
    pi=bisect_left(x[p-1],dd)
    qi=bisect_left(x[q-1],dd)
    pl=dd-x[p-1][pi-1]
    pr=x[p-1][pi+1]-dd
    ql=dd-x[q-1][qi-1]
    qr=x[q-1][qi]-dd
    del x[p-1][pi]
    x[q-1].insert(qi,dd)
    ans-=c[p-1]*pl*pr
    ans+=c[q-1]*ql*qr
    print(ans)
if __name__ == "__main__":
  main()

Fixed submission:
d=int(input())
c=list(map(int,input().split()))
s=[list(map(int,input().split()))for _ in range(d)]
t=[int(input())for _ in range(d)]
m=int(input())
dq=[list(map(int,input().split()))for _ in range(m)]
x=[[0]for _ in range(26)]
ans=0
for i in range(d):
  x[t[i]-1].append(i+1)
  ans+=s[i][t[i]-1]
  for j in range(26):ans-=((i+1)-x[j][-1])*c[j]
for i in range(26):
  x[i].append(d+1)
for dd,q in dq:
  p=t[dd-1]
  t[dd-1]=q
  ans-=s[dd-1][p-1]
  ans+=s[dd-1][q-1]
  pi=qi=0
  while x[p-1][pi]!=dd:pi+=1
  while x[q-1][qi]<dd:qi+=1
  pl=dd-x[p-1][pi-1]
  pr=x[p-1][pi+1]-dd
  ql=dd-x[q-1][qi-1]
  qr=x[q-1][qi]-dd
  del x[p-1][pi]
  x[q-1].insert(qi,dd)
  ans-=c[p-1]*pl*pr
  ans+=c[q-1]*ql*qr
  print(ans)
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())
c=[0]*(n+1)
for i in range(1,n+1):
  for j in range(i,n+1,i):c[j]+=1
ans=0
for i in range(1,n+1):ans+=i*c[i]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(1,max(m,n)+1):f.append(f[i-1]*i%mod)
def comb(n,r):return f[n]*pow(f[r],mod-2,mod)*pow(f[n-r],mod-2,mod)%mod
def pern(n,r):return f[n]*pow(f[n-r],mod-2,mod)%mod
a=[0]*(n+1)
a[n]=1
for i in range(n-1,-1,-1):
    a[i]=(comb(n,n-i)*pern(m-i,n-i)-a[i+1])%mod
print(a[0]*pern(m,n)%mod)


Fixed submission:
n,m=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(1,max(m,n)+1):f.append(f[i-1]*i%mod)
def comb(n,r):return f[n]*pow(f[r],mod-2,mod)*pow(f[n-r],mod-2,mod)%mod
def pern(n,r):return f[n]*pow(f[n-r],mod-2,mod)%mod
a=[0]*(n+1)
a[n]=1
for i in range(n-1,-1,-1):
    a[i]=(comb(n,n-i)*pern(m-i,n-i)-a[i+1])%mod
print(a[0]*pern(m,n)%mod)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
ans=[0]*n
def f(x):
  c=[x[i-1]^x[i]for i in range(1,n)]
  k=[x[1:].count(1)%2]
  for i in c:
    k.append(k[-1]^i)
  return k
for i in range(31):
  t=1<<i
  x=[]
  for j in a:
    if t&j:x.append(1)
    else:x.append(0)
  m=f(x)
  for j in range(n):ans[j]+=t*m[j]
print(*ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
ans=[0]*n
def f(x):
  c=[x[i-1]^x[i]for i in range(1,n)]
  k=[x[1:].count(1)%2]
  for i in c:
    k.append(k[-1]^i)
  return k
for i in range(31):
  t=1<<i
  x=[]
  for j in a:
    if t&j:x.append(1)
    else:x.append(0)
  m=f(x)
  for j in range(n):ans[j]+=t*m[j]
print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
mod=10**9+7
k=int(input())
s=input()
n=len(s)
c=1
t=1
ans=0
m=10**20
for i in range(k+1):
  ans+=c*t
  if ans>m:ans%=mod
  c*=(n+k-i)*pow(i+1,mod-2,mod)
  if c>m:c%=mod
  t*=25
  if t>m:t%=mod
print(ans%mod)


Fixed submission:
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
k=int(input())
s=input()
n=len(s)
ans=0
for i in range(k,-1,-1):
  ans+=comb(n+k,i)*pow(25,i,mod)
  ans%=mod
print(ans%mod)

Buggy python submission (verdict: Time Limit Exceeded):
mod=10**9+7
k=int(input())
s=input()
n=len(s)
c=1
t=1
ans=0
for i in range(k+1):
  ans+=c*t
  ans%=mod
  c*=(n+k-i)*pow(i+1,mod-2,mod)
  c%=mod
  t*=25
  t%=mod
print(ans)


Fixed submission:
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
k=int(input())
s=input()
n=len(s)
ans=0
for i in range(k,-1,-1):
  ans+=comb(n+k,i)*pow(25,i,mod)
  ans%=mod
print(ans%mod)

Buggy python submission (verdict: Runtime Error):
k=int(input())
s=input()
n=len(s)
c=1
t=1
ans=0
for i in range(k+1):
  ans+=c*t
  ans%=mod
  c*=(n+k-i)*pow(i+1,mod-2,mod)
  c%=mod
  t*=25
  t%=mod
print(ans)


Fixed submission:
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
k=int(input())
s=input()
n=len(s)
ans=0
for i in range(k,-1,-1):
  ans+=comb(n+k,i)*pow(25,i,mod)
  ans%=mod
print(ans%mod)
Buggy python submission (verdict: Time Limit Exceeded):
a,b,c,d=map(int,input().split())
mod=998244353
dp=[(d+2)*[0]for _ in range(c+2)]
dp[a][b]=1
for i in range(a,c+1):
    for j in range(b,d+1):
        dp[i][j]%=mod
        dp[i+1][j]+=dp[i][j]*j
        dp[i][j+1]+=dp[i][j]*i
        dp[i+1][j+1]-=dp[i][j]*i*j
print(dp[c][d])


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

Buggy python submission (verdict: Time Limit Exceeded):
a,b,c,d=map(int,input().split())
mod=998244353
dp=[(d+1)*[0]for _ in range(c+1)]
for i in range(a,c+1):
  for j in range(b,d+1):
    if i==a and j==b:
      dp[i][j]=1
      continue
    if i==a:
      dp[i][j]=dp[i][j-1]*i%mod
      continue
    if j==b:
      dp[i][j]=dp[i-1][j]*j%mod
      continue
    dp[i][j]=(dp[i-1][j]*j+dp[i][j-1]*i-dp[i-1][j-1]*(i-1)*(j-1))%mod
print(dp[c][d])


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

Buggy python submission (verdict: Runtime Error):
#wrong sample.
a,b,c,d=map(int,input().split())
mod=998244353
f=[1]
for i in range(10000):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
dp=[(d+1)*[0]for _ in range(c+1)]
dp[a][b]=1
def dfs(x,y):
  if dp[x][y]!=0:return dp[x][y]
  if x!=a and y!=b:
    ans=(dfs(x-1,y-1)*comb(x+y-1,2))%mod
    if (x-a)+(y-b)-1>=2:
      ans=(ans+comb(x-a+y-b-1,2))%mod
  elif x!=a:
    ans=(dfs(x-1,y)*y)%mod
  elif y!=b:
    ans=(dfs(x,y-1)*x)%mod
  else:
    ans=1
  dp[x][y]=ans
  return ans
print(dfs(c,d))
#for i in dp:print(i)

Fixed submission:
a,b,c,d=map(int,input().split())
mod=998244353
dp=[(d+1)*[0]for _ in range(c+1)]
for i in range(a,c+1):
  for j in range(b,d+1):
    if i==a and j==b:
      dp[i][j]=1
      continue
    if i==a:
      dp[i][j]=dp[i][j-1]*i%mod
      continue
    if j==b:
      dp[i][j]=dp[i-1][j]*j%mod
      continue
    dp[i][j]=(dp[i-1][j]*j+dp[i][j-1]*i-dp[i-1][j-1]*(i-1)*(j-1))%mod
print(dp[c][d])
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(k):
  b=[0]*(n+1)
  for j in range(n):
    b[max(0,j-a[j])]+=1
    b[min(n,j+a[j]+1)]-=1
  for j in range(n):
    b[j+1]+=b[j]
  a=b[:-1]
  if a==[n]*n:exit(print(*a))
print(*a)

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(k):
  b=[0]*(n+1)
  for j in range(n):
    b[max(0,j-a[j])]+=1
    b[min(n,j+a[j]+1)]-=1
  for j in range(n):
    b[j+1]+=b[j]
  a=b[:-1]
  if a==[n]*n:exit(print(*a))
print(*a)

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(k):
  b=[0]*(n+1)
  for j in range(n):
    b[max(0,j-a[j])]+=1
    b[min(n,j+a[j]+1)]-=1
  for i in range(n):
    b[i+1]+=b[i]
  a=b[:-1]
  if a==[n]*n:exit(print(*a))
print(*a)

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(k):
  b=[0]*(n+1)
  for j in range(n):
    b[max(0,j-a[j])]+=1
    b[min(n,j+a[j]+1)]-=1
  for j in range(n):
    b[j+1]+=b[j]
  a=b[:-1]
  if a==[n]*n:exit(print(*a))
print(*a)
Buggy python submission (verdict: Time Limit Exceeded):
t=int(input())
for _ in range(t):
  n=int(input())
  a=list(map(int,input().split()))
  s=input()
  if "1" not in s:
    print(0)
    continue
  r=s.rfind("1")
  o=[]
  so=set()
  z=[]
  sz=set()
  for i in range(n):
    if s[i]=="0" and i>r:
      for j in z:
        if a[i]^j not in sz:
          z.append(a[i]^j)
          sz.add(a[i]^j)
      if a[i] not in sz:
        z.append(a[i])
        sz.add(a[i])
    elif s[i]=="1":
      for j in o:
        if a[i]^j not in so:
          o.append(a[i]^j)
          so.add(a[i]^j)
      if a[i] not in so:
        o.append(a[i])
        so.add(a[i])
  if sz<=so:print(0)
  else:print(1)

Fixed submission:
for _ in range(int(input())):
  n=int(input())
  a=list(map(int,input().split()))
  s=input()
  b=[]
  ans=0
  for i in range(n-1,-1,-1):
    for j in b:
      a[i]=min(a[i],a[i]^j)
    if a[i]!=0:
      if s[i]=="0":
        b.append(a[i])
      else:
        ans=1
  print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input()).split())
if 0 in a:exit(print(0))
ans=1
for i in a:
  ans*=i
  if ans>10**18:exit(print(-1))
print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
ans=1
if 0 in a:exit(print(0))
for i in a:
  ans*=i
  if ans>10**18:
    print(-1)
    exit()
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
ans=1
for i in a:
  ans*=i
if ans>10**18:print(-1)
else:print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
ans=1
if 0 in a:exit(print(0))
for i in a:
  ans*=i
  if ans>10**18:
    print(-1)
    exit()
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,s=map(int,input().split())
dp=[0]*(s+1)
mod=998244353
inv=pow(2,mod-2,mod)
dp[0]=pow(2,n,mod)
for i in list(map(int,input().split())):
  for j in range(s,i-1,-1):
    dp[j]=(dp[j]+dp[j-i]*inv)%mod
print(dp[s])

Fixed submission:
n,s=map(int,input().split())
dp=[0]*(s+1)
mod=998244353
inv=pow(2,mod-2,mod)
dp[0]=pow(2,n,mod)
for i in list(map(int,input().split())):
  for j in range(s,i-1,-1):
    dp[j]=(dp[j]+dp[j-i]*inv)%mod
print(dp[s])

Buggy python submission (verdict: Time Limit Exceeded):
n,s,*a=map(int,open(0).read().split());d=[0]*-~s;m=998244353;v=pow(2,m-2,m);d[0]=pow(2,n,m)
for i in a:
  for j in range(s,i-1,-1):d[j]+=(d[j-i]*v)%m
print(d[s]%m)

Fixed submission:
n,s=map(int,input().split())
dp=[0]*(s+1)
mod=998244353
inv=pow(2,mod-2,mod)
dp[0]=pow(2,n,mod)
for i in list(map(int,input().split())):
  for j in range(s,i-1,-1):
    dp[j]=(dp[j]+dp[j-i]*inv)%mod
print(dp[s])

Buggy python submission (verdict: Runtime Error):
n,s,*a=map(int,open().read().split());d=[0]*-~s;m=998244353;v=pow(2,m-2,m);d[0]=pow(2,n,m)
for i in a:
  for j in range(s,i-1,-1):d[j]+=(d[j-i]*v)%m
print(d[s])

Fixed submission:
n,s=map(int,input().split())
dp=[0]*(s+1)
mod=998244353
inv=pow(2,mod-2,mod)
dp[0]=pow(2,n,mod)
for i in list(map(int,input().split())):
  for j in range(s,i-1,-1):
    dp[j]=(dp[j]+dp[j-i]*inv)%mod
print(dp[s])

Buggy python submission (verdict: Time Limit Exceeded):
n,s=map(int,input().split())
dp=[0]*(s+1)
mod=998244353
dp[0]=pow(2,n,mod)
for i in list(map(int,input().split())):
  for j in range(s,i-1,-1):
    dp[j]=(dp[j]+dp[j-i]*pow(2,mod-2,mod))%mod
print(dp[s])


Fixed submission:
n,s=map(int,input().split())
dp=[0]*(s+1)
mod=998244353
inv=pow(2,mod-2,mod)
dp[0]=pow(2,n,mod)
for i in list(map(int,input().split())):
  for j in range(s,i-1,-1):
    dp[j]=(dp[j]+dp[j-i]*inv)%mod
print(dp[s])

Buggy python submission (verdict: Time Limit Exceeded):
n,s=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(s+1)
mod=998244353
dp[0]=pow(2,n,mod)
for i in range(n):
  m=a[i]
  for j in range(s,m-1,-1):
    dp[j]+=dp[j-m]*pow(2,mod-2,mod)
    dp[j]%=mod
print(dp[s])

Fixed submission:
n,s=map(int,input().split())
dp=[0]*(s+1)
mod=998244353
inv=pow(2,mod-2,mod)
dp[0]=pow(2,n,mod)
for i in list(map(int,input().split())):
  for j in range(s,i-1,-1):
    dp[j]=(dp[j]+dp[j-i]*inv)%mod
print(dp[s])
Buggy python submission (verdict: Time Limit Exceeded):
n,m,k=map(int,input().split())
ans=0
mod=998244353
f=[1]
for i in range(n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
for kk in range(k+1):
  anss=m*pow(m-1,n-1-kk,mod)%mod
  anss=anss*comb(n-1,kk)%mod
  ans=(ans+anss)%mod
print(ans)

Fixed submission:
n,m,k=map(int,input().split())
ans=0
mod=998244353
f=[1]
for i in range(n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
for kk in range(k+1):
  anss=m*pow(m-1,n-1-kk,mod)%mod
  anss=anss*comb(n-1,kk)%mod
  ans=(ans+anss)%mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def f(s):
  m=0
  n=0
  for i in s:
    if i==")":n-=1
    else:n+=1
    m=min(m,n)
  return [m,n]
n=int(input())
s=[input()for _ in range(n)]
mab=[]
pab=[]
for i in range(n):
  ab=f(s[i])
  if sum(ab)>0:pab.append(ab)
  else:mab.append(ab)
pab.sort(reverse=1)
mab.sort(key=lambda x:x[0]-x[1])
#print(pab)
#print(mab)
ab=pab+mab
n=0
for a,b in ab:
  if n+a<0:exit(print("No"))
  n+=b
  if n<0:exit(print("No"))
if n==0:print('Yes')
else:print('No')

Fixed submission:
def f(s):
  m=0
  n=0
  for i in s:
    if i==")":n-=1
    else:n+=1
    m=min(m,n)
  return [m,n]
n=int(input())
s=[input()for _ in range(n)]
mab=[]
pab=[]
for i in range(n):
  ab=f(s[i])
  if sum(ab)>0:pab.append(ab)
  else:mab.append(ab)
pab.sort(reverse=1)
mab.sort(key=lambda x:x[0]-x[1])
#print(pab)
#print(mab)
ab=pab+mab
n=0
for a,b in ab:
  if n+a<0:exit(print("No"))
  n+=b
  if n<0:exit(print("No"))
if n==0:print('Yes')
else:print('No')
Buggy python submission (verdict: Runtime Error):
from itertools import*;n,m,q=map(int,input().split());l=[list(map(int,input().split()))for _ in[0]*q];print(max(sum(d for a in l if i[b-1]-i[a-1]==c)for i in itertools.combinations_with_replacement(range(m),n)))

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

Buggy python submission (verdict: Runtime Error):
import itertools;n,m,q,*l=map(int,open(0).read().split());print(max(sum(d for a in[l[j*4:j*4+4]for j in range(q)]if i[b-1]-i[a-1]==c)for i in itertools.combinations_with_replacement(range(m),n)))

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

Buggy python submission (verdict: Runtime Error):
import itertools;n,m,q,*l=map(int,open(0).read().split());print(max(sum(d for a,b,c,d in l[::4]if i[b-1]-i[a-1]==c)for i in itertools.combinations_with_replacement(range(m),n)))

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split()))for _ in range(q)]
def dfs(li):
  ans=0
  for a,b,c,d in abcd:
    if li[b-1]-li[a-1]==c:ans+=d
  for i in range(n-1):
    if li[i]<li[i+1]:
      li[i]+=1
      ans=max(ans,dfs(li))
      li[i]-=1
  if li[-1]!=m:
    li[-1]+=1
    ans=max(ans,dfs(li))
    li[-1]-=1
  return ans
print(dfs([1]*n))


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split()))for _ in range(q)]
def dfs(li):
  ans=0
  for a,b,c,d in abcd:
    if li[b-1]-li[a-1]==c:ans+=d
  for i in range(n-1):
    if li[i]<li[i+1]:
      li[i]+=1
      ans=max(ans,dfs(li))
      li[i]-=1
  if li[-1]!=m:
    li[-1]+=1
    ans=max(ans,dfs(li))
    li[-1]-=1
  return ans
print(dfs([1]*n))

Fixed submission:
import itertools
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split()))for _ in range(q)]
ans=0
for i in itertools.combinations_with_replacement(range(m),n):
  anss=0
  for a,b,c,d in abcd:
    if i[b-1]-i[a-1]==c:anss+=d
  ans=max(ans,anss)
print(ans)
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left,bisect_right
n=int(input())
a=list(map(int,input().split()))
edge=[[]for _ in range(n)]
for _ in range(n-1):
  u,v=map(int,input().split())
  u-=1
  v-=1
  edge[u].append(v)
  edge[v].append(u)
ans=[-1]*n
dp=[10**10]*n

#オイラーツアー
#n=頂点数、s=始点、edge=隣接リスト
#木構造を投げると訪問順listが帰ってくる、|ans|=2*n-1
#適宜書き換えて実装を楽にしましょう
def EulerTour(n,s,e):
  EulerTour_list=[]
  def EulerTour_dfs(i,root):
    EulerTour_list.append(i)
    ind=bisect_right(dp,a[i])
    bef=dp[ind]
    dp[ind]=a[i]
    ans[i]=bisect_left(dp,10**10)
    for j in e[i]:
      if j!=root:
        EulerTour_dfs(j,i)
    if root!=-1:
      EulerTour_list.append(root)
      dp[ind]=bef
  EulerTour_dfs(s,-1)
  return EulerTour_list

EulerTour(n,0,edge)
print(*ans)

Fixed submission:
#入力高速化 + 再帰回数制限解除
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)

from bisect import bisect_left,bisect_right
n=int(input())
a=list(map(int,input().split()))
edge=[[]for _ in range(n)]
for _ in range(n-1):
  u,v=map(int,input().split())
  u-=1
  v-=1
  edge[u].append(v)
  edge[v].append(u)
ans=[-1]*n
dp=[10**10]*n

#オイラーツアー
#n=頂点数、s=始点、edge=隣接リスト
#木構造を投げると訪問順listが帰ってくる、|ans|=2*n-1
#適宜書き換えて実装を楽にしましょう
def EulerTour(n,s,e):
  EulerTour_list=[]
  def EulerTour_dfs(i,root):
    EulerTour_list.append(i)
    ind=bisect_left(dp,a[i])
    bef=dp[ind]
    dp[ind]=a[i]
    ans[i]=bisect_left(dp,10**10)
    for j in e[i]:
      if j!=root:
        EulerTour_dfs(j,i)
    if root!=-1:
      EulerTour_list.append(root)
      dp[ind]=bef
  EulerTour_dfs(s,-1)
  return EulerTour_list

EulerTour(n,0,edge)
print(*ans)