Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
A=list(map(int,input().split()))

import heapq
heapq.heapify(A)

for i in range(M):
  b,c=map(int,input().split())
  for j in range(b):
    val=heapq.heappop(A)
    if val<c:
      heapq.heappush(A,c)
    else:
      heapq.heappush(A,val)
      break
print(sum(A))

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

Q=[None]*M
for i in range(M):
  b,c=map(int,input().split())
  Q[i]=[b,c]
  
Q=sorted(Q,key=lambda x:x[1])[::-1]

A=sorted(A)
ind=0
for i in range(len(Q)):
  b,c=Q[i]
  for p in range(b):
    if ind+p>=len(A):
      print(sum(A))
      exit(0)
    if A[ind+p]<c:
      A[ind+p]=c
    else:
      break
  ind+=b
else:
  print(sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=list(map(int,input().split()))
cs=[None]*m
for i in range(m):
  cs[i]=list(map(int,input().split()))

import heapq
heapq.heapify(a)
for q in cs:
  b=q[0]
  c=q[1]
  for i in range(b):
    v=heapq.heappop(a)
    if v>=c:
      heapq.heappush(a,v)
      break
    else:
      heapq.heappush(a,c)
print(sum(a))

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

Q=[None]*M
for i in range(M):
  b,c=map(int,input().split())
  Q[i]=[b,c]
  
Q=sorted(Q,key=lambda x:x[1])[::-1]

A=sorted(A)
ind=0
for i in range(len(Q)):
  b,c=Q[i]
  for p in range(b):
    if ind+p>=len(A):
      print(sum(A))
      exit(0)
    if A[ind+p]<c:
      A[ind+p]=c
    else:
      break
  ind+=b
else:
  print(sum(A))
Buggy python submission (verdict: Runtime Error):
s=input()
print("Heisei" if int(s[5:7])<5) else "TBD")

Fixed submission:
s=input()
y=int(s[:4])
print("Heisei" if y<2019 or (y==2019 and int(s[5:7])<5) else "TBD")
Buggy python submission (verdict: Runtime Error):
d=[0 for in range(4)]
for i in range(3):
  a,b=map(int,input().split())
  d[a-1]+=1
  d[b-1]+=1
print(("NO","YES")[d.count(1)==2 and d.count(2)==2])

Fixed submission:
d=[0 for i in range(4)]
for i in range(3):
  a,b=map(int,input().split())
  d[a-1]+=1
  d[b-1]+=1
print(("NO","YES")[d.count(1)==2 and d.count(2)==2])
Buggy python submission (verdict: Time Limit Exceeded):
s=int(input())
cur=set([s])
i=1
while True:
  i=i+1
  if s%2==0:
    s=s//2
  else:
    s=3*s+1
  if s in cur:
    print(i)
  else:
    cur.add(s)

Fixed submission:
s=int(input())
cur=set([s])
i=1
while True:
  i=i+1
  if s%2==0:
    s=s//2
  else:
    s=3*s+1
  if s in cur:
    print(i)
    break
  else:
    cur.add(s)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
H = list(map(int,readline().split()))

INF = 10 ** 10
dp = [INF] * N
dp[0] = 0

for i in range(N - 1):
  for j in range(1, K + 1):
    if i + j >= N:
      break
    if dp[i + j] > dp[i] + abs(H[i + j] - H[i]):
      dp[i + j] = dp[i] + abs(H[i + j] - H[i])
      
print(dp[N - 1])

Fixed submission:
N,K = map(int, input().split())
H = list(map(int, input().split()))
 
inf = 10**4*N
dp = [inf]*N
dp[0] = 0
for i,h in enumerate(H):
    if i == 0:
        continue
    m = max(0, i-K)
    dp[i] = min([dpj + abs(h - hj) for dpj, hj in zip(dp[m:i], H[m:i])])
print(dp[N-1])

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

INF=float('inf')
dp=[INF]*N
dp[0]=0

for i in range(N):
  for j in range(K+1):
    if i+j<len(h):
      dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))
      
print(dp[N-1])


Fixed submission:
N,K = map(int, input().split())
H = list(map(int, input().split()))
 
inf = 10**4*N
dp = [inf]*N
dp[0] = 0
for i,h in enumerate(H):
    if i == 0:
        continue
    m = max(0, i-K)
    dp[i] = min([dpj + abs(h - hj) for dpj, hj in zip(dp[m:i], H[m:i])])
print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,W=map(int,input().split())
mv=1
s=[None]*n
for i in range(n):
  s[i]=list(map(int,input().split()))
  mv+=s[i][1]
  
INF=10**9+5
dp=[INF]*mv
dp[0]=0
for i in range(len(s)):
  w=s[i][0]
  v=s[i][1]
  for j in range(len(dp)-v-1,-1,-1):
    if dp[j]+w<dp[j+v]:
      dp[j+v]=dp[j]+w
      
ans=0
for i in range(len(dp)):
  if dp[i]<=W:
    ans=i
    
print(ans)

Fixed submission:
n,W=map(int,input().split())
mv=1
s=[None]*n
for i in range(n):
  s[i]=list(map(int,input().split()))
  mv+=s[i][1]
  
INF=10**9+5
dp=[INF]*mv
dp[0]=0
for i in range(len(s)):
  w=s[i][0]
  v=s[i][1]
  for j in range(len(dp)-v-1,-1,-1):
    if dp[j]+w<dp[j+v]:
      dp[j+v]=dp[j]+w
      
ans=0
for i in range(len(dp)):
  if dp[i]<=W:
    ans=i
    
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,W=map(int,input().split())
mv=1
s=[None]*n
for i in range(n):
  s[i]=list(map(int,input().split()))
  mv+=s[i][1]
  
INF=10**9+5
dp=[INF]*mv
dp[0]=0
for i in range(len(s)):
  w=s[i][0]
  v=s[i][1]
  for j in range(len(dp)-1,-1,-1):
    if j+v<len(dp):
      dp[j+v]=min(dp[j+v],dp[j]+w)
      
ans=0
for i in range(len(dp)):
  if dp[i]<=W:
    ans=i
    
print(ans)

Fixed submission:
n,W=map(int,input().split())
mv=1
s=[None]*n
for i in range(n):
  s[i]=list(map(int,input().split()))
  mv+=s[i][1]
  
INF=10**9+5
dp=[INF]*mv
dp[0]=0
for i in range(len(s)):
  w=s[i][0]
  v=s[i][1]
  for j in range(len(dp)-v-1,-1,-1):
    if dp[j]+w<dp[j+v]:
      dp[j+v]=dp[j]+w
      
ans=0
for i in range(len(dp)):
  if dp[i]<=W:
    ans=i
    
print(ans)
Buggy python submission (verdict: Runtime Error):
h,w=map(int,input().split())
grid=[None]*h
for i in range(h):
  grid[i]=input()
  
dp=[[0 for i in range(w)] for j in range(h)]
DIV=10**9+7
import deque
que=deque()
que.append([0,0,1])
while que:
  node=que.pop()
  y=node[0]
  x=node[1]
  p=node[2]
  dp[y][x]+=p
  dp[y][x]%=DIV
  if y+1<h and grid[y+1][x]!="#":
    que.append([y+1,x,dp[y][x]])
  if x+1<w and grid[y][x+1]!="#":
    que.append([y,x+1,dp[y][x+1]])
  
print(dp[-1][-1])
  

Fixed submission:
h,w=map(int,input().split())
grid=[None]*h
for i in range(h):
  grid[i]=input()
  
dp=[[0 for i in range(w)] for j in range(h)]
DIV=10**9+7

for i in range(h):
  for j in range(w):
    if grid[i][j]=="#":
      dp[i][j]=0
    elif i==0 and j==0:
      dp[i][j]=1
    else:
      up=0
      left=0
      if i>0:
        up=dp[i-1][j]
      if j>0:
        left=dp[i][j-1]
      dp[i][j]=(up+left)%DIV
        
print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline

N = int(readline())
P = list(map(float,readline().split()))

# dp[i][j] = i枚投げて、表がj枚出ている確率
dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
  for j in range(N):
    dp[i + 1][j] += dp[i][j] * (1 - P[i])
    dp[i + 1][j + 1] += dp[i][j] * P[i]
    
ans = 0
for i in range(N + 1):
  if i > N // 2:
    ans += dp[-1][i]

print(ans)

Fixed submission:
n=int(input())
p=list(map(float,input().split()))
dp=[[0 for j in range(n+1)] for i in range(n+1)]

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline

# dp[i][j] = i個目までのコインで、表の個数がj個である確率
# dp[i][j] = dp[i - 1][j] * (1 - P[i]) + dp[i - 1][j - 1] * P[i]
# dp[0][0] = 1 # 0個目までのコインで、表の個数が0個である確率は1

N = int(readline())
P = list(map(float,readline().split()))

dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 1
for i in range(len(P)):
  for j in range(i + 2):
    if j - 1 >= 0:
      dp[i + 1][j] = dp[i][j] * (1 - P[i]) + dp[i][j - 1] * P[i]
    else:
      dp[i + 1][j] = dp[i][j] * (1 - P[i])
  
ans = 0
for i in range((N // 2) + 1, len(dp[-1])):
  ans += dp[-1][i]
  
print(ans)

Fixed submission:
n=int(input())
p=list(map(float,input().split()))
dp=[[0 for j in range(n+1)] for i in range(n+1)]

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

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=list(map(float,input().split()))
dp=[[0 for j in range(n+1)] for i in range(n+1)]

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


Fixed submission:
n=int(input())
p=list(map(float,input().split()))
dp=[[0 for j in range(n+1)] for i in range(n+1)]

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

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=list(map(float,input().split()))
dp=[[0 for j in range(n+1)] for i in range(n+1)]

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


Fixed submission:
n=int(input())
p=list(map(float,input().split()))
dp=[[0 for j in range(n+1)] for i in range(n+1)]

dp[0][0]=1
for i in range(n):
  for j in range(n):
    dp[i+1][j+1]+=dp[i][j]*p[i]
    dp[i+1][j]+=dp[i][j]*(1-p[i])
ans=0
for i in range(n,-1,-1):
  if i>n-i:
    ans+=dp[-1][i]
  else:
    break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
A = list(map(int,readline().split()))

# dp[i] = 石の残り数がiの時の勝敗
# i個の状態から遷移できる場所に負けが存在したら、それを相手に回すことが出来るため勝ち
# i個の状態から遷移できる場所に勝ちが存在したら、それを相手に回す必要はないので更新なし

dp = [False] * (K + 1)
for i in range(1, K + 1): # 石がi個の状態
  for j in range(len(A)): # それを相手に回す元が存在するかチェック
    if i - A[j] >= 0 and not dp[i -A[j]]:
      dp[i] = True

print(("Second","First")[dp[K]])  

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))

dp=[False]*(k+1+max(a))

for i in range(1+k):
  if not dp[i]:
    for x in a:
      dp[i+x]=True

print(("Second","First")[dp[k]])

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))

dp=[False]*(k+1)

for i in range(1,len(dp)):
  for x in a:
    if i-x>=0:
      dp[i]|=not dp[i-x]

print(("Second","First")[dp[k]])

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))

dp=[False]*(k+1+max(a))

for i in range(1+k):
  if not dp[i]:
    for x in a:
      dp[i+x]=True

print(("Second","First")[dp[k]])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
A = list(map(int,readline().split()))
DIV = 10 ** 9 + 7

dp = [[0] * (K + 1) for i in range(N + 1)]
sdp = [[0] * (K + 1) for i in range(N + 1)]

dp[0][0] = 1
for j in range(len(dp[0])):
  sdp[0][j] = 1
  
for i in range(1, N + 1):
  for j in range(K + 1):
    dp[i][j] = sdp[i - 1][j]
    if j - A[i - 1] - 1 >= 0:
      dp[i][j] -= sdp[i - 1][j - A[i - 1] - 1]
    dp[i][j] %= DIV
  sdp[i][0] = dp[i][0]
  for j in range(1, K + 1):
    sdp[i][j] = sdp[i][j - 1] + dp[i][j]
    sdp[i][j] %= DIV
    
print(dp[N][K])

Fixed submission:
import sys
readline = sys.stdin.readline

N,K = map(int, readline().split())
A = list(map(int,readline().split()))
DIV = 10 ** 9 + 7

# dp[i][j] : i人目までにj個配るときの場合の数
# 数式変形で以下
# dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - Ai-1 - 1]

dp = [[0] * (K + 1) for i in range(N + 1)]
for i in range(N + 1):
  dp[i][0] = 1 # 0個配る方法は常に1通り
  
for i in range(1, N + 1):
  for j in range(1, K + 1):
    if j - A[i - 1] - 1 >= 0:
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - A[i - 1] - 1]) % DIV
    else:
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % DIV
      
print(dp[N][K])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline

N,K = map(int, readline().split())
A = list(map(int,readline().split()))
DIV = 10 ** 9 + 7

# dp[i][j] : i人目までにj個配るときの場合の数
# 数式変形で以下
# dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - Ai-1 - 1]

dp = [[0] * (K + 1) for i in range(N + 1)]
for i in range(N + 1):
  dp[i][0] = 1 # 0個配る方法は常に1通り
  
for i in range(1, N + 1):
  for j in range(1, K + 1):
    if j - A[i - 1] - 1 >= 0:
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - A[i - 1] - 1]) % DIV
    else:
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % DIV
      
print(dp[N][K])

Fixed submission:
import sys
readline = sys.stdin.readline

N,K = map(int, readline().split())
A = list(map(int,readline().split()))
DIV = 10 ** 9 + 7

# dp[i][j] : i人目までにj個配るときの場合の数
# 数式変形で以下
# dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - Ai-1 - 1]

dp = [[0] * (K + 1) for i in range(N + 1)]
for i in range(N + 1):
  dp[i][0] = 1 # 0個配る方法は常に1通り
  
for i in range(1, N + 1):
  for j in range(1, K + 1):
    if j - A[i - 1] - 1 >= 0:
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - A[i - 1] - 1]) % DIV
    else:
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % DIV
      
print(dp[N][K])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline

# 区間DP
# dp[l][r] = 区間[l,r]のスライムを合体するときの最小コスト
# dp[l][r] = min(dp[l][m] + dp[m + 1][r]) + sum(l,r)

N = int(readline())
A = list(map(int,readline().split()))

A = [0] + A
for i in range(1,len(A)):
  A[i] += A[i - 1]

INF = 10 ** 10
dp = [[INF] * N for i in range(N)]
for i in range(N):
  dp[i][i] = 0

# 区間の長さが小さい順にループする(1～N)
for i in range(N): # 区間の長さ
  for l in range(N - i):
    r = l + i
    # lからrまでの区間で最小となるdp[l][m] + dp[m][r]の組み合わせを探す
    # lからrまでのAの累積和
    cums = A[r + 1] - A[l]
    for m in range(l,r):
      if dp[l][m] + dp[m + 1][r] + cums < dp[l][r]:
        dp[l][r] = dp[l][m] + dp[m + 1][r] + cums
        
print(dp[0][-1])

Fixed submission:
import sys
readline = sys.stdin.readline

# 区間DP
# dp[l][r] = 区間[l,r]のスライムを合体するときの最小コスト
# dp[l][r] = min(dp[l][m] + dp[m + 1][r]) + sum(l,r)

N = int(readline())
A = list(map(int,readline().split()))

A = [0] + A
for i in range(1,len(A)):
  A[i] += A[i - 1]

INF = 10 ** 18
dp = [[INF] * N for i in range(N)]
for i in range(N):
  dp[i][i] = 0

# 区間の長さが小さい順にループする(1～N)
for i in range(N): # 区間の長さ
  for l in range(N - i):
    r = l + i
    # lからrまでの区間で最小となるdp[l][m] + dp[m][r]の組み合わせを探す
    # lからrまでのAの累積和
    cums = A[r + 1] - A[l]
    for m in range(l,r):
      if dp[l][m] + dp[m + 1][r] + cums < dp[l][r]:
        dp[l][r] = dp[l][m] + dp[m + 1][r] + cums
        
print(dp[0][-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline

# dp[i][smaller][d] : i桁目で、K未満で、そこまでの総和をDで割った余り = 個数

K = readline().rstrip()
D = int(readline())
DIV = 10 ** 9 + 7
keta = len(K)

dp = [[[0] * D for i in range(2)] for j in range(keta)]

x0 = int(K[0])
dp[0][0][x0 % D] = 1
bef = x0 % D # 未満じゃないときに直前に値が入っているmodを記録しておく
for i in range(x0):
  dp[0][1][i % D] += 1
  
for i in range(1, keta):
  x = int(K[i])
  
  # 未満じゃない -> 未満じゃない
  dp[i][0][(bef + x) % D] = 1
  
  # 未満じゃない -> 未満
  # 0~x-1の値を取り得る
  for j in range(x):
    dp[i][1][(bef + j) % D] += dp[i - 1][0][bef]
  
  for j in range(D):
    dp[i][1][j] %= DIV
  
  bef = (bef + x) % D # 未満じゃないときに値が入っているmodを記録
  
  # 未満 -> 未満
  for j in range(D):
    for k in range(10): # 0~9のすべてを取れる
      dp[i][1][(k + j) % D] += dp[i - 1][1][j]
      
  for j in range(D):
    dp[i][1][j] %= DIV

print((dp[-1][0][0] + dp[-1][1][0] - 1) % DIV) # 0を数えないので引く

Fixed submission:
import sys
readline = sys.stdin.readline

# dp[i][smaller][d] : i桁目で、K未満で、そこまでの総和をDで割った余り = 個数

K = readline().rstrip()
D = int(readline())
DIV = 10 ** 9 + 7
keta = len(K)

dp = [[[0] * D for i in range(2)] for j in range(keta)]

x0 = int(K[0])
dp[0][0][x0 % D] = 1
bef = x0 % D # 未満じゃないときに直前に値が入っているmodを記録しておく
for i in range(x0):
  dp[0][1][i % D] += 1
  
for i in range(1, keta):
  x = int(K[i])
  
  # 未満じゃない -> 未満じゃない
  dp[i][0][(bef + x) % D] = 1
  
  # 未満じゃない -> 未満
  # 0~x-1の値を取り得る
  for j in range(x):
    dp[i][1][(bef + j) % D] += dp[i - 1][0][bef]
  
  for j in range(D):
    dp[i][1][j] %= DIV
  
  bef = (bef + x) % D # 未満じゃないときに値が入っているmodを記録
  
  # 未満 -> 未満
  for j in range(D):
    for k in range(10): # 0~9のすべてを取れる
      dp[i][1][(k + j) % D] += dp[i - 1][1][j]
      
  for j in range(D):
    dp[i][1][j] %= DIV

print((dp[-1][0][0] + dp[-1][1][0] - 1) % DIV) # 0を数えないので引く
Buggy python submission (verdict: Time Limit Exceeded):
A,B,C=map(int,input().split())
poisoned=False
ans=0
while True:
  if C>0 and not poisoned:
    ans+=1
    C-=1
    poisoned=True
  if B>0:
    ans+=1
    poisoned=False
    B-=1
  if A>0 and poisoned:
    A-=1
    poisoned=False
  if (B==0 and A==0 and poisoned) or (B==0 and C==0):
    break
print(ans)

Fixed submission:
A,B,C=map(int,input().split())
if A+B>=C:
  print(B+C)
else:
  print(B*2+A+1)
Buggy python submission (verdict: Time Limit Exceeded):
N,P=map(int,input().split())
if N==1:
  print(P)
  exit(0)
res=[]
while True:
  if P==1:
    break
  for i in range(2,P+1):
    if P%i==0:
      res.append(i)
      P//=i
      break
  else:
    break

import collections
counter=collections.Counter(res)
ans=1
for c in counter.items():
  key=c[0]
  val=c[1]
  ans*=(key**(val//N))
  
print(ans)

Fixed submission:
N,P=map(int,input().split())
if N==1:
  print(P)
  exit(0)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

res=factorization(P)
  
ans=1
for c in res:
  key=c[0]
  val=c[1]
  ans*=(key**(val//N))
  
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=set(['3','5','7'])
ans=0
for i in range(357,n+1):
  ans+=((len(p-set(str(i)))==0) and (len(set(str(i))-p)==0))
print(ans)

Fixed submission:
N=int(input())

nums=[]
all=set(['3','5','7'])
def dfs(x):
  if x>N:
    return
  if x>=357:
    if len(all-set(list(str(x))))==0:
      nums.append(x)
  for i in (3,5,7):
    dfs(x*10+i)

dfs(0)
print(len(nums))
Buggy python submission (verdict: Runtime Error):
n=list(map(int,open(0).read().split()))
print((n[1]+n[2],"Hello World")[n[0]==1])

Fixed submission:
n,*d=map(int,open(0).read().split())
print((sum(d),"Hello World")[n==1])
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
ans=0
import math
for i in range(1,min(m//n+1,int(math.sqrt(m))+1):
  if m%i==0:
    ans=max(i,ans)
print(ans)


Fixed submission:
n,m=map(int,input().split())
ans=0
import math
for i in range(1,int(math.sqrt(m))+1):
  if m%i!=0:
    continue
  i2=m//i
  if i*n<=m:
    ans=max(ans,i)
  if i2*n<=m:
    ans=max(ans,i2)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
ans=0
for i in range(1,m//n+1):
  if m%i==0:
    ans=i
print(ans)


Fixed submission:
n,m=map(int,input().split())
ans=0
import math
for i in range(1,int(math.sqrt(m))+1):
  if m%i!=0:
    continue
  i2=m//i
  if i*n<=m:
    ans=max(ans,i)
  if i2*n<=m:
    ans=max(ans,i2)
print(ans)
Buggy python submission (verdict: Runtime Error):
s=input()
k=int(input())
if k<=len(s):
  if len(set(s[:k]))==1 and s[0]=="1":
    print(1)
    exit(0)
print(s[1])

Fixed submission:
s=input()
k=int(input())
if k<=len(s):
  if len(set(s[:k]))==1 and s[0]=="1":
    print(1)
    exit(0)
ans="1"
for c in s:
  if c!="1":
    ans=c
    break
print(ans)

Buggy python submission (verdict: Runtime Error):
s=input()
if s[0]=="1":
  print(s[1])
else:
  print(s[0])


Fixed submission:
s=input()
k=int(input())
if k<=len(s):
  if len(set(s[:k]))==1 and s[0]=="1":
    print(1)
    exit(0)
ans="1"
for c in s:
  if c!="1":
    ans=c
    break
print(ans)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
mods=[0]*m
mods[0]=1
for i in range(1,len(a)):
  a[i]=a[i-1]+a[i]%m
  mods[a[i]%m]+=1
ans=0
for i in range(len(mods)):
  p=mods[i]
  if p>1:
    ans+=p*(p-1)//2
print(ans)

Fixed submission:
n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
from collections import defaultdict
mods=defaultdict(int)
mods[0]=1
for i in range(1,len(a)):
  a[i]=a[i-1]+a[i]%m
  mods[a[i]%m]+=1
ans=0
for v in mods.values():
  if v>1:
    ans+=v*(v-1)//2
print(ans)

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
mods=[0]*m
mods[0]=1
for i in range(1,len(a)):
  a[i]=a[i-1]+a[i]
  mods[a[i]%m]+=1
ans=0
for i in range(len(mods)):
  p=mods[i]
  if p>1:
    ans+=p*(p-1)//2
print(ans)

Fixed submission:
n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
from collections import defaultdict
mods=defaultdict(int)
mods[0]=1
for i in range(1,len(a)):
  a[i]=a[i-1]+a[i]%m
  mods[a[i]%m]+=1
ans=0
for v in mods.values():
  if v>1:
    ans+=v*(v-1)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
s=input()
x=int(input())
ans=""
for i in range(0,len(s)+1,x):
  ans+=s[i]
print(ans)

Fixed submission:
s=input()
x=int(input())
ans=""
for i in range(0,len(s),x):
  ans+=s[i]
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
readline=sys.stdin.readline

N=int(readline())
A=list(map(int,readline().split()))
B=[0]*N
sumB=0
for i in range(N):
  B[i]=A[i]-(i+1)
  
B=sorted(B)
candi=[0]*3
candi[0]=B[N//2-1]
candi[1]=B[N//2]
candi[2]=B[N//2+1]

ans=10**10
for c in candi:
  res=0
  for i in range(N):
    res+=abs(B[i]-c)
  if res<ans:
    ans=res
print(ans)


Fixed submission:
import sys
readline=sys.stdin.readline

N=int(readline())
A=list(map(int,readline().split()))
B=[0]*N
sumB=0
for i in range(N):
  B[i]=A[i]-(i+1)
  
B=sorted(B)
mid=0
if len(B)&1:
  mid=B[N//2]
else:
  mid=(B[N//2-1]+B[N//2])//2
  
ans=0
for i in range(N):
  ans+=abs(B[i]-mid)

print(ans)
Buggy python submission (verdict: Runtime Error):
n=input()
s=0
for i in range(len(n)):
  s=s+int(n[i])
print(("No","Yes")[int(n)%s==0]

Fixed submission:
n=input()
s=0
for i in range(len(n)):
  s=s+int(n[i])
print(("No","Yes")[int(n)%s==0])
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))

sums=[0]*(len(a)+1)
for i in range(len(a)):
  sums[i+1]=sums[i]+a[i]
  
cnt=0
for i in range(len(sums)-1):
  for j in range(i+1,len(sums)):
    if sums[j]-sums[i]==0:
      cnt+=1
      
print(cnt)

Fixed submission:
import collections

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

sums=[0]*(len(a)+1)
for i in range(len(a)):
  sums[i+1]=sums[i]+a[i]
  
counter=collections.Counter(sums)
cnt=0
for val in counter.values():
  if val>1:
    cnt+=(val*(val-1))//2

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
# a b c
# b e d
# c d f
# について、
#  a  b  c [a  b]
#  b  e  d [b  e]
#  c  d  f [c  d]
# [a  b  c  a  b]
# [b  e  d  b  e]
# 左上の1,1から始まるものが条件を満たすなら、
# 2,2から始まるものも3,3から始まるものも条件を満たす
# 一つ条件を満たすのであれば、N個条件を満たすことになる。
# 従い、以下を順にチェックして答えをN倍すれば良い
#  a  b  c [a  b]
#  b  e  d [b  e]
#  c  d  f [c  d]

import sys
readline = sys.stdin.readline

N = int(readline())
grid = [None] * N
for i in range(N):
  S = readline().rstrip()
  grid[i] = S + S[:-1]
  
# 左上の頂点を(0,0)~(N-1,0)の全てをチェックする
ans = 0
for p in range(N):
  # 左上の頂点はp
  ok = True
  for i in range(N):
    for j in range(i+1):
      if grid[i][j + p] != grid[j][i + p]:
        ok = False
        break
    if not ok:
      break
  if ok:
    ans += 1

print(ans * N)


Fixed submission:
# a b c
# b e d
# c d f
# について、
#  a  b  c [a  b]
#  b  e  d [b  e]
#  c  d  f [c  d]
# [a  b  c  a  b]
# [b  e  d  b  e]
# 左上の1,1から始まるものが条件を満たすなら、
# 2,2から始まるものも3,3から始まるものも条件を満たす
# 一つ条件を満たすのであれば、N個条件を満たすことになる。
# 従い、以下を順にチェックして答えをN倍すれば良い
#  a  b  c [a  b]
#  b  e  d [b  e]
#  c  d  f [c  d]

import sys
readline = sys.stdin.readline

N = int(readline())
grid = [None] * N
for i in range(N):
  S = readline().rstrip()
  grid[i] = S + S[:-1]
  
# 左上の頂点を(0,0)~(N-1,0)の全てをチェックする
ans = 0
for p in range(N):
  # 左上の頂点はp
  ok = True
  for i in range(N):
    for j in range(i+1):
      if grid[i][j + p] != grid[j][i + p]:
        ok = False
        break
    if not ok:
      break
  if ok:
    ans += 1

print(ans * N)