Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,l = inpl()
a = inpl()
aa = []
for i in range(1,n):
    aa.append([i,a[i-1] + a[i]])
# print(aa)
if n == 2: 
    if a[0] + a[1] < l:
        print('Impossible')
    else:
        print('Possible')
        print(1)
elif n == 3:
    if aa[0][1] < l and aa[1][1] < l:
            print('Impossible')
    else:
        aa.sort(key=lambda x:x[1])
        print('Possible')
        for i in range(n-1):
            print(aa[i][0])
else:
    for i in range(1,n-1):
        if aa[i-1][1] < l and aa[i][1] < l and aa[i+1][1] < l:
            print('Impossible')
            break
    else:
        aa.sort(key=lambda x:x[1])
        print('Possible')
        for i in range(n-1):
            print(aa[i][0])


Fixed submission:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,l = inpl()
a = inpl()
for i in range(1,n):
    if a[i] + a[i-1] >= l:
        print('Possible')
        for j in range(1,i):
            print(j)
        for k in range(i+1,n)[::-1]:
            print(k)
        print(i)
        break
else:
    print('Impossible')
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int, input().split())
mod=998244353
D=[0]*(2*N+2)
D[0]=1
A=[]
for i in range(K):
  L,R=map(int, input().split())
  A.append((L,R))
A=sorted(A)
#print(A)
for i in range(N-1):
  for a,b in A:
    if i+a<=N:
      for j in range(i+a,min(i+b+1,N)):
        D[j]+=D[i]
        D[j]%=mod
print(D[N-1])

Fixed submission:
mod=998244353
N,K=map(int, input().split())
A=[list(map(int, input().split())) for _ in range(K)]

S=[0 for _ in range(N+1)]
S[1]=1
for i in range(1,N):
  S[i+1]=S[i]
  for l,r in A:
    S[i+1]+=S[max(0,i-l+1)]-S[max(0,i-r)]
  S[i+1]%=mod
print((S[N]-S[N-1])%mod)

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int, input().split())
mod=998244353
D=[0]*(2*N+2)
D[0]=1
A=[]
for i in range(K):
  L,R=map(int, input().split())
  A.append((L,R))
A=sorted(A)
#print(A)
for i in range(N-1):
  for a,b in A:
    if i+a<=N:
      for j in range(i+a,min(i+b+1,N)):
        D[j]+=D[i]
        D[j]%=mod
print(D[N-1])

Fixed submission:
mod=998244353
N,K=map(int, input().split())
A=[list(map(int, input().split())) for _ in range(K)]

S=[0 for _ in range(N+1)]
S[1]=1
for i in range(1,N):
  S[i+1]=S[i]
  for l,r in A:
    S[i+1]+=S[max(0,i-l+1)]-S[max(0,i-r)]
  S[i+1]%=mod
print((S[N]-S[N-1])%mod)
Buggy python submission (verdict: Time Limit Exceeded):
N,X,M=map(int, input().split())
A=[X]
for i in range(1,M+1):
  d=pow(A[i-1],2,M)
  if d in A:
    break
  A.append(d)
c=A.index(d)
e=len(A)
cy=e-c
ans=0
if N<=e:
  for i in range(N):
    ans+=A[i]
  print(ans)
else:
  m=sum(A[:c])
  n=sum(A[c:e])
  #print(m,n)
  f=(N-c)//cy
  ans=m+n*f+sum(A[c:c+((N-c)%cy)])
  print(ans)

Fixed submission:
N,X,M=map(int, input().split())
A=[X]
for i in range(1,M+1):
  d=pow(A[i-1],2,M)
  if d in A:
    break
  A.append(d)
c=A.index(d)
e=len(A)
cy=e-c
ans=0
if N<=e:
  for i in range(N):
    ans+=A[i]
  print(ans)
else:
  m=sum(A[:c])
  n=sum(A[c:e])
  #print(m,n)
  f=(N-c)//cy
  ans=m+n*f+sum(A[c:c+((N-c)%cy)])
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
mod=10**9+7
if N==1:
  print(0)
  exit()
dp=[[0,0,0,0]for i in range(N-1)]
dp[0]=[64,17,17,2]
for i in range(N-2):
  dp[i+1][3]=dp[i][1]+dp[i][2]+dp[i][3]*10
  dp[i+1][2]=dp[i][0]+dp[i][2]*9
  dp[i+1][1]=dp[i][0]+dp[i][1]*9
  dp[i+1][0]=dp[i][0]*8
  dp[i+1][3]%=mod
  dp[i+1][2]%=mod
  dp[i+1][1]%=mod
  dp[i+1][0]%=mod
print(dp[-1][-1])

Fixed submission:
N=int(input())
mod=10**9+7
if N==1:
  print(0)
  exit()
dp=[[0,0,0]for i in range(N-1)]
dp[0]=[64,34,2]
for i in range(N-2):
  dp[i+1][2]=dp[i][1]+dp[i][2]*10
  dp[i+1][1]=dp[i][0]*2+dp[i][1]*9
  dp[i+1][0]=dp[i][0]*8
  dp[i+1][2]%=mod
  dp[i+1][1]%=mod
  dp[i+1][0]%=mod
print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
D={}
for i in range(N):
  x,y=map(int, input().split())
  if x not in D:
    D[x]=[y,y]
  else:
    a,b=D[x][0],D[x][1]
    D[x][0]=min(a,y)
    D[x][1]=max(b,y)
d=len(D)
if len(D)==1:
  for i in D:
    print(abs(D[i][0]-D[i][1]))
    exit()
ans=0
for i in D:
  for j in D:
    if i<=j:
      a,b,c,d=D[i][0],D[i][1],D[j][0],D[j][1]
      ans=max(ans,abs(d-a)+(j-i),abs(c-b)+(j-i))
print(ans)

Fixed submission:
N=int(input())
A,B=[],[]
for i in range(N):
  x,y=map(int, input().split())
  A.append(x+y)
  B.append(x-y)
  
A=sorted(A)
B=sorted(B)
print(max(abs(A[0]-A[-1]),abs(B[0]-B[-1])))
Buggy python submission (verdict: Runtime Error):
N,K=map(int, input().split())
P=list(map(int, input().split()))
C=list(map(int, input().split()))

F=[0]*N
I=[0]*N
CN=[0]*N

for i in range(N):
  around=0
  cnt=0
  A=[]
  if F[i]==0:
    F[i]=1
    around+=1
    cnt+=C[i]
    nex=P[i]-1
    A.append(i)
    while F[nex]==0:
      A.append(nex)
      F[nex]=1
      around+=1
      cnt+=C[nex]
      nex=P[nex]-1
    for j in A:
      I[j]=around
      CN[j]=cnt
#print(F)
#print(I)
#print(CN)
ans=-(10**9)*2
for i in range(N):
  cnt=C[i]
  #動かす回数が一周に満たない時
  if K+1<I[i]:
    d=0
    nex=i
    for j in range(K+1):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
  #動かす回数が一周を超えるとき
  elif CN[i]<0:
    d=0
    nex=i
    for j in range(I[i]):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
  else:
    d=0
    nex=i
    for j in range(I[i]):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
    acnt=cnt
    bcnt=C[i]
    syuukai=(K+1)//I[i]
    nokori=(K+1)%I[i]
    syuukai-=1
    nokori+=I[i]
    b+=syuukai*CN[i]
    d=0
    nex=i
    for j in range(nokori-1):
      d+=C[nex]
      nex=P[nex]-1
      bcnt=max(d,bcnt)
    cnt=max(acnt,bcnt)
  ans=max(ans,cnt)
print(ans)

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

F=[0]*N
I=[0]*N
CN=[0]*N

for i in range(N):
  around=0
  cnt=0
  A=[]
  if F[i]==0:
    F[i]=1
    around+=1
    cnt+=C[i]
    nex=P[i]-1
    A.append(i)
    while F[nex]==0:
      A.append(nex)
      F[nex]=1
      around+=1
      cnt+=C[nex]
      nex=P[nex]-1
    for j in A:
      I[j]=around
      CN[j]=cnt
ans=-(10**9)*2
for i in range(N):
  #動かす回数が一周に満たない時
  if K<=I[i]:
    d=C[i]
    cnt=d
    nex=P[i]-1
    for j in range(K-1):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
  #動かす回数が一周を超えるとき
  elif CN[i]<=0:
    d=C[i]
    cnt=d
    nex=P[i]-1
    for j in range(I[i]-1):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
  else:
    syuukai=K//I[i]
    nokori=K%I[i]
    syuukai-=1
    nokori+=I[i]
    d=C[i]
    cnt=d
    nex=P[i]-1
    for j in range(nokori-1):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
    cnt+=syuukai*CN[i]
  ans=max(ans,cnt)
print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
D={}
from decimal import Decimal
A=[Decimal(input()) for _ in range(N)]
A=[int(i*10**9) for i in A]
for i in range(N):
  x=A[i]
  y=x
  tcnt,fcnt=0,0
  while x%2==0 and tcnt<18:
    tcnt+=1
    x=x//2
  while y%5==0 and fcnt<18:
    fcnt+=1
    y=y//5
  A[fcnt][tcnt]+=1

cnt=0
for i in range(19):
  for j in range(19):
    for k in range(19):
      for l in range(19):
        if i+k>=18 and j+l>=18:
          if i!=k and j!=l:
            d=A[i][j]
            e=A[k][l]
            p=d*e
          elif i==k and j==l:
            d=A[i][j]
            p=d*(d-1)
          else:
            d=A[i][j]
            e=A[k][l]
            p=d*e
          cnt+=p
print(cnt//2)

Fixed submission:
N=int(input())
D={}
from decimal import Decimal
A=[Decimal(input()) for _ in range(N)]
A=[int(i*10**9) for i in A]
for i in range(N):
  x=A[i]
  y=x
  tcnt,fcnt=0,0
  while x%2==0 and tcnt<18:
    tcnt+=1
    x//=2
  while y%5==0 and fcnt<18:
    fcnt+=1
    y//=5
  if (tcnt,fcnt) not in D:
    D[((tcnt,fcnt))]=1
  else:
    D[((tcnt,fcnt))]+=1

ans=0
for t1,f1 in D:
  for t2,f2 in D:
    if t1+t2>=18 and f1+f2>=18:
      if t1==t2 and f1==f2:
        ans+=D[(t1,f1)]*(D[(t1,f1)]-1)
      else:
        ans+=D[(t1,f1)]*D[(t2,f2)]
print(ans//2)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int, input().split())
A=list(map(int, input().split()))
s=1
for i in range(K):
  s*=A[i]
l,r=0,K
for i in range(N-K):
  ne=s*A[r]//A[l]
  if ne>s:
    print('Yes')
  else:
    print('No')
  l+=1
  r+=1
  s=ne

Fixed submission:
N,K=map(int, input().split())
A=list(map(int, input().split()))
l,r=0,K
for i in range(N-K):
  s,ne=A[l],A[r]
  if ne>s:
    print('Yes')
  else:
    print('No')
  l+=1
  r+=1

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int, input().split())
A=list(map(int, input().split()))
s=1
for i in range(K):
  s*=A[i]
l,r=0,K
for i in range(N-K):
  ne=s*A[r]//A[l]
  if ne>s:
    print('Yes')
  else:
    print('No')
  l+=1
  r+=1
  s=ne

Fixed submission:
N,K=map(int, input().split())
A=list(map(int, input().split()))
l,r=0,K
for i in range(N-K):
  s,ne=A[l],A[r]
  if ne>s:
    print('Yes')
  else:
    print('No')
  l+=1
  r+=1
Buggy python submission (verdict: Runtime Error):
N,K=map(int, input().split())
A=list(map(int, input().split()))
D,E=[],[]
zcnt,scnt,fcnt=0,0,0
for i in A:
  if i==0:
    zcnt+=1
    D.append(0)
  elif i>0:
    D.append(i)
    scnt+=1
  else:
    E.append(i)
    fcnt+=1
mod=10**9+7
ans=1
if K==N:
  for i in A:
    ans*=i
    ans%=mod
  print(ans)
  exit()
if K%2==1 and max(A)<0:
  A=sorted(A)[::-1]
  for i in range(K):
    ans*=A[i]
    ans%=mod
  print(ans)
  exit()
if K>scnt+fcnt:
  print(0)
  exit()
D,E=sorted(D)[::-1],sorted(E)
#print(D,E)
ans=1
a,b=0,0
for i in range(K//2):
  if len(D)>=2 and len(E)>=2:
    d,e=D[a]*D[a+1],E[b]*E[b+1]
    if d>e:
      ans*=d
      a+=2
      ans%=mod
    else:
      ans*=e
      b+=2    
      ans%=mod
  elif len(D)>=2 and len(E)<2:
    d=D[a]*D[a+1]
    ans*=d
    a+=2
    ans%=mod
  elif len(D)<2 and len(E)>=2:
    e=E[b]*E[b+1]
    ans*=e
    b+=2
    ans%=mod

if K%2==1:
  Z=[]
  if a!=scnt:
    Z.append(D[a])
  if b!=fcnt:
    Z.append(E[-1])
  if 0 in A:
    Z.append(0)
  ans*=max(Z)
  ans%=mod
print(ans)

Fixed submission:
N,K=map(int, input().split())
A=list(map(int, input().split()))
D,E=[],[]
zcnt,scnt,fcnt=0,0,0
for i in A:
  if i==0:
    zcnt+=1
    D.append(0)
  elif i>0:
    D.append(i)
    scnt+=1
  else:
    E.append(i)
    fcnt+=1
mod=10**9+7
ans=1
#全て使う場合は問答無用でかける
if K==N:
  for i in A:
    ans*=i
    ans%=mod
  print(ans)
  exit()
#マイナスを奇数個絶対かける→確実に答えはマイナス
if K%2==1 and max(A)<0:
  A=sorted(A)[::-1]
  for i in range(K):
    ans*=A[i]
    ans%=mod
  print(ans)
  exit()
#絶対0をかけなきゃいけない
if K>scnt+fcnt:
  print(0)
  exit()
D,E=sorted(D)[::-1],sorted(E)
#print(D,E)
ans=1
cnt=0
a,b=0,0
while K-cnt>1:
  if a+1<=len(D)-1 and b+1<=len(E)-1:
    d,e=D[a]*D[a+1],E[b]*E[b+1]
    if d>e:
      ans*=D[a]
      a+=1
      cnt+=1
      ans%=mod
    else:
      ans*=e
      b+=2    
      ans%=mod
      cnt+=2
  elif a+1<=len(D)-1:
    d=D[a]*D[a+1]
    ans*=D[a]
    a+=1
    cnt+=1
    ans%=mod
  elif b+1<=len(E)-1:
    e=E[b]*E[b+1]
    ans*=e
    b+=2
    cnt+=2
    ans%=mod

if K-cnt==1:
  Z=[]
  if a!=scnt:
    Z.append(D[a])
  if b!=fcnt:
    Z.append(E[-1])
  if 0 in A:
    Z.append(0)
  ans*=max(Z)
  ans%=mod
print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int, input().split()))
Q=int(input())
B=[list(map(int, input().split())) for _ in range(Q)]
D={}
ma=0
for i in A:
  ma+=i
  if i not in D:
    D[i]=1
  else:
    D[i]+=1
    
for b,c in B:
  if b in D:
    f=D[b]
    t=D[c]
    D[c]=f+t
    D[b]=0
    ma+=(c-b)*f
    print(ma)

Fixed submission:
N=int(input())
A=list(map(int, input().split()))
Q=int(input())
B=[list(map(int, input().split())) for _ in range(Q)]
D={}
ma=0
for i in A:
  ma+=i
  if i not in D:
    D[i]=1
  else:
    D[i]+=1
    
for b,c in B:
  if b in D:
    f=D[b]
    if c in D:
      t=D[c]
    else:
      t=0
    
    D[c]=f+t
    D[b]=0
    ma+=(c-b)*f
  print(ma)
Buggy python submission (verdict: Runtime Error):
K=int(input())
s=input()
S=len(s)
mod=10**9+7
MAX_N=10**6+10
fact=[1]
fact_inv=[0]*(MAX_N+4)
for i in range(MAX_N+3):
  fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
  fact_inv[i]=fact_inv[i+1]*(i+1)%mod

def mod_comb_k(n,k,mod):
  return fact[n]*fact_inv[k]%mod*fact_inv[n-k] %mod

cnt=0
for i in range(K+1):
  a=(pow(26,i,mod)*pow(25,K-i,mod))*(mod_comb_k(K+S-i-1,S-1,mod))
  a%=mod
  cnt+=a
  cnt%=mod
print(cnt)

Fixed submission:
K=int(input())
s=input()
S=len(s)
mod=10**9+7
MAX_N=10**7
fact=[1]
fact_inv=[0]*(MAX_N+4)
for i in range(MAX_N+3):
  fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
  fact_inv[i]=fact_inv[i+1]*(i+1)%mod

def mod_comb_k(n,k,mod):
  return fact[n]*fact_inv[k]%mod*fact_inv[n-k] %mod

cnt=0
for i in range(K+1):
  a=(pow(26,i,mod)*pow(25,K-i,mod))*(mod_comb_k(K+S-i-1,S-1,mod))
  a%=mod
  cnt+=a
  cnt%=mod
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
K=int(input())
s=input()
S=len(s)
mod=10**9+7
MAX_N=10**7
fact=[1]
fact_inv=[0]*(MAX_N+4)
for i in range(MAX_N+3):
  fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
  fact_inv[i]=fact_inv[i+1]*(i+1)%mod

def mod_comb_k(n,k,mod):
  return fact[n]*fact_inv[k]%mod*fact_inv[n-k] %mod

cnt=0
for i in range(K+1):
  a=(pow(26,i,mod)*pow(25,K-i,mod))*(mod_comb_k(K+S-i-1,S-1,mod))
  a%=mod
  cnt+=a
  cnt%=mod
print(cnt)

Fixed submission:
K=int(input())
s=input()
S=len(s)
mod=10**9+7
MAX_N=10**7
fact=[1]
fact_inv=[0]*(MAX_N+4)
for i in range(MAX_N+3):
  fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
  fact_inv[i]=fact_inv[i+1]*(i+1)%mod

def mod_comb_k(n,k,mod):
  return fact[n]*fact_inv[k]%mod*fact_inv[n-k] %mod

cnt=0
for i in range(K+1):
  a=(pow(26,i,mod)*pow(25,K-i,mod))*(mod_comb_k(K+S-i-1,S-1,mod))
  a%=mod
  cnt+=a
  cnt%=mod
print(cnt)

Buggy python submission (verdict: Runtime Error):
K=int(input())
s=input()
S=len(s)
mod=10**9+7
MAX_N=10**6
fact=[1]
fact_inv=[0]*(MAX_N+4)
for i in range(MAX_N+3):
  fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
  fact_inv[i]=fact_inv[i+1]*(i+1)%mod

def mod_comb_k(n,k,mod):
  return fact[n]*fact_inv[k]%mod*fact_inv[n-k] %mod

cnt=0
for i in range(K+1):
  a=(pow(26,i,mod)*pow(25,K-i,mod))*(mod_comb_k(K+S-i-1,S-1,mod))
  a%=mod
  cnt+=a
  cnt%=mod
print(cnt)

Fixed submission:
K=int(input())
s=input()
S=len(s)
mod=10**9+7
MAX_N=10**7
fact=[1]
fact_inv=[0]*(MAX_N+4)
for i in range(MAX_N+3):
  fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
  fact_inv[i]=fact_inv[i+1]*(i+1)%mod

def mod_comb_k(n,k,mod):
  return fact[n]*fact_inv[k]%mod*fact_inv[n-k] %mod

cnt=0
for i in range(K+1):
  a=(pow(26,i,mod)*pow(25,K-i,mod))*(mod_comb_k(K+S-i-1,S-1,mod))
  a%=mod
  cnt+=a
  cnt%=mod
print(cnt)
Buggy python submission (verdict: Runtime Error):
X=int(input())
import math
print(360*X//math.gcd(360,X)

Fixed submission:
X=int(input())
import math
a=360*X//math.gcd(360,X)
print(a//X)
Buggy python submission (verdict: Time Limit Exceeded):
a,b,c,d=map(int, input().split())
mod=998244353
if a==c and b==d:
  print(1)
  exit()
else:
  dp=[[0]*(d+1) 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
      else:
        dp[i][j]=dp[i][j-1]*i+dp[i-1][j]*j-dp[i-1][j-1]*(i-1)*(j-1)
        dp[i][j]%=mod
print(dp[c][d])

Fixed submission:
a,b,c,d=map(int, input().split())
mod=998244353
if a==c and b==d:
  print(1)
  exit()
else:
  dp=[[0]*(d+1) 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
      else:
        dp[i][j]=dp[i][j-1]*i+dp[i-1][j]*j-dp[i-1][j-1]*(i-1)*(j-1)
        dp[i][j]%=mod
print(dp[c][d])
Buggy python submission (verdict: Runtime Error):
a,b=input().split()
r=''
x=0
for i in b:
  if i=='.':
    r=r
  elif i!='0':
    x=1
    r=r+i
  elif x==1 and i=='0':
    r=r+i
A=int(a)
B=int(r)
print(A*B//100)
    

Fixed submission:
a,b=input().split()
r=''
x=0
for i in b:
  if i=='.':
    r=r
  elif i!='0':
    x=1
    r=r+i
  elif x==1 and i=='0':
    r=r+i
if len(r)==0:
  r='0'
A=int(a)
B=int(r)
print(A*B//100)
Buggy python submission (verdict: Runtime Error):
T=int(input())
for i in range(T):
  N,a,b,c,d=map(int, input().split())
  memo={}
  memo[0]=0
  memo[1]=d
  
  def f(n):
    if n in memo:
      return memo[n]
    e2,e3,e5=n%2,n%3,n%5
    dd=min(d*n,d*2+a+f((n-e2)//2),d*2+a+f((n+e2)//2),d*e3+b+f((n-e3)//3),d*(3-e3)+b+f((n+3-e3)//3),d*e5+c+f((n-e5)//5),d*(5-e5)+c+f((n+5-e5)//5))
    memo[n]=dd
    return dd
  print(f(n))

Fixed submission:
T=int(input())
for i in range(T):
  N,a,b,c,d=map(int, input().split())
  memo={}
  memo[0]=0
  memo[1]=d
  
  def f(n):
    if n in memo:
      return memo[n]
    e2,e3,e5=n%2,n%3,n%5
    dd=min(d*n,d*e2+a+f((n-e2)//2),d*e2+a+f((n+e2)//2),d*e3+b+f((n-e3)//3),d*(3-e3)+b+f((n+3-e3)//3),d*e5+c+f((n-e5)//5),d*(5-e5)+c+f((n+5-e5)//5))
    memo[n]=dd
    return dd
  print(f(N))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int, input().split()))
D={}
E={}
for i in range(N):
  a=i+A[i]
  b=i-A[i]
  D.setdefault(a,0)
  E.setdefault(b,0)
  D[a]+=1
  E[b]+=1
ans=0
for i in D.keys():
  for j in E.keys():
    if i==j:
      ans+=D[i]*E[i]
print(ans)

Fixed submission:
N=int(input())
A=list(map(int, input().split()))
D={}
E={}
for i in range(N):
  a=i+A[i]
  b=i-A[i]
  D.setdefault(a,0)
  E.setdefault(b,0)
  D[a]+=1
  E[b]+=1
ans=0
for i in D:
  if i in E:
    ans+=D[i]*E[i]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int, input().split()))
D={}
E={}
for i in range(N):
  a=i+A[i]
  b=i-A[i]
  D.setdefault(a,0)
  E.setdefault(b,0)
  D[a]+=1
  E[b]+=1
ans=0
for i in D.keys():
  for j in E.keys():
    if i==j:
      ans+=D[i]*E[i]
print(ans)

Fixed submission:
N=int(input())
A=list(map(int, input().split()))
D={}
E={}
for i in range(N):
  a=i+A[i]
  b=i-A[i]
  D.setdefault(a,0)
  E.setdefault(b,0)
  D[a]+=1
  E[b]+=1
ans=0
for i in D:
  if i in E:
    ans+=D[i]*E[i]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
n=0
ans=0
A=[0]*2019
A[0]=1
for i in range(len(s)):
  n=(n+int(s[-1-i])*(10**i)%2019)%2019
  #print(i,n)
  A[n]+=1
for i in A:
  ans+=i*(i-1)//2
print(ans)

Fixed submission:
s=input()
n=0
ans=0
A=[0]*2019
A[0]=1
for i,j in enumerate(reversed(s)):
  n=(n+int(j)*pow(10,i,2019))%2019
  #print(i,n)
  A[n]+=1
for i in A:
  ans+=i*(i-1)//2
print(ans)

Buggy python submission (verdict: Runtime Error):
S=input()
N=len(S)
if N<5:
  print(0)
  exit()
A={}
ans=0
for i in range(N-4+1):
  a=int(S[i:])%2019
  A.setdefault(a,0)
  A[a]+=1
  if A[a]>0:
    ans+=A[a]-1
print(ans+A[0])

Fixed submission:
s=input()
n=0
ans=0
A=[0]*2019
A[0]=1
for i,j in enumerate(reversed(s)):
  n=(n+int(j)*pow(10,i,2019))%2019
  #print(i,n)
  A[n]+=1
for i in A:
  ans+=i*(i-1)//2
print(ans)

Buggy python submission (verdict: Runtime Error):
S=input()
N=len(S)
if N<5:
  print(0)
  exit()
A={}
for i in range(N-4+1):
  a=int(S[i:])%2019
  A.setdefault(a,0)
  A[a]+=1

ans=0
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

for i in A.values():
  if i>1:
    ans+=cmb(i,2)
ans+=A[0]
print(ans)

Fixed submission:
s=input()
n=0
ans=0
A=[0]*2019
A[0]=1
for i,j in enumerate(reversed(s)):
  n=(n+int(j)*pow(10,i,2019))%2019
  #print(i,n)
  A[n]+=1
for i in A:
  ans+=i*(i-1)//2
print(ans)

Buggy python submission (verdict: Runtime Error):
S=input()
N=len(S)
if N<5:
  print(0)
  exit()
A={}
for i in range(N-4+1):
  a=int(S[i:])%2019
  A.setdefault(a,0)
  A[a]+=1

ans=0
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

for i in A.values():
  if i>1:
    ans+=cmb(i,2)
ans+=A[0]
print(ans)

Fixed submission:
s=input()
n=0
ans=0
A=[0]*2019
A[0]=1
for i,j in enumerate(reversed(s)):
  n=(n+int(j)*pow(10,i,2019))%2019
  #print(i,n)
  A[n]+=1
for i in A:
  ans+=i*(i-1)//2
print(ans)

Buggy python submission (verdict: Runtime Error):
S=input()
N=len(S)
if N<5:
  print(0)
  exit()
A={}
for i in range(N-4+1):
  a=int(S[i:])%2019
  A.setdefault(a,0)
  A[a]+=1

ans=0
import math
def comb(n,r):
  return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))
for i in A.values():
  if i>1:
    ans+=comb(i,2)
ans+=A[0]
print(ans)
  

Fixed submission:
s=input()
n=0
ans=0
A=[0]*2019
A[0]=1
for i,j in enumerate(reversed(s)):
  n=(n+int(j)*pow(10,i,2019))%2019
  #print(i,n)
  A[n]+=1
for i in A:
  ans+=i*(i-1)//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int, input().split()))
A=sorted([(a,p) for p, a in enumerate(A)],reverse=True)

dp=[[0]*(N+1) for _ in range(N+1)]
for i,(a,p) in enumerate(A):
  for j in range(i+1):
    #左詰
    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+(p-j)*a)
    #右詰
    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+((N-1-(i-j))-p)*a)
print(max(dp[-1]))

Fixed submission:
N=int(input())
A=list(map(int, input().split()))
A=sorted([(a,p) for p, a in enumerate(A)])[::-1]

dp=[[0]*(N+1) for _ in range(N+1)]
for i,(a,p) in enumerate(A):
  for j in range(i+1):
    #左詰
    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+(p-j)*a)
    #右詰
    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+((N-1-(i-j))-p)*a)
print(max(dp[-1]))

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int, input().split()))
A=sorted([(a,p) for p, a in enumerate(A)])[::-1]

dp=[[0]*(N+1) for _ in range(N+1)]
for i,(a,p) in enumerate(A):
  for j in range(i+1):
    #左詰
    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+(p-j)*a)
    #右詰
    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+((N-1-(i-j))-p)*a)
print(max(dp[-1]))

Fixed submission:
N=int(input())
A=list(map(int, input().split()))
A=sorted([(a,p) for p, a in enumerate(A)])[::-1]

dp=[[0]*(N+1) for _ in range(N+1)]
for i,(a,p) in enumerate(A):
  for j in range(i+1):
    #左詰
    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+(p-j)*a)
    #右詰
    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+((N-1-(i-j))-p)*a)
print(max(dp[-1]))
Buggy python submission (verdict: Time Limit Exceeded):
K=int(input())
import math
t=0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      a=math.gcd(i,j)
      b=math.gcd(a,k)
      t+=b
print(t)

Fixed submission:
K=int(input())
import math

if K==1:
  print(1)
  exit()
elif K==2:
  print(9)
  exit()
else:
  t=0
  for i in range(1,K-1):
    for j in range(i+1,K):
      for k in range(j+1,K+1):
        a=math.gcd(i,j)
        b=math.gcd(a,k)
        t+=b
  tw=0
  for i in range(1,K):
    for j in range(i+1,K+1):
      c=math.gcd(i,j)
      tw+=c
  
  on=0
  for i in range(1,K+1):
    on+=i
  print(t*6+tw*6+on)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=input()
R=[]
G=[]
B=[]
for i in range(N):
  if S[i]=='R':
    R.append(i)
  elif S[i]=='G':
    G.append(i)
  else:
    B.append(i)

cnt=0
for i in R:
  for j in G:
    for k in B:
      a=max(i,j,k)
      b=min(i,j,k)
      c=i+j+k-a-b
      if a-c!=c-b:
        cnt+=1
print(cnt)

Fixed submission:
N=int(input())
S=input()
R=[]
G=[]
B=[]
for i in range(N):
  if S[i]=='R':
    R.append(i)
  elif S[i]=='G':
    G.append(i)
  else:
    B.append(i)

cnt=len(R)*len(G)*len(B)
for i in R:
  for j in G:
    if (i+j)%2==0 and S[(i+j)//2]=='B':
      cnt-=1
for i in R:
  for j in B:
    if (i+j)%2==0 and S[(i+j)//2]=='G':
      cnt-=1
for i in B:
  for j in G:
    if (i+j)%2==0 and S[(i+j)//2]=='R':
      cnt-=1      
print(cnt)