Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

N = int(input())
A = list(map(int,input().split()))
C = A[N:(2*N)]

L = []
R = []
for i in range(N):
  heapq.heappush(L,A[i]) #左側にAの左側からN個を追加
  heapq.heappush(R,-A[-1-i]) #右側数列にAの右側からN個を追加。多いほうから取り出すので-1倍

#左側の総和を求める。
ansL = [sum(L)]
for i in range(N):
  heapq.heappush(L,C[i])
  heapq.heappop(L)
  ansL.append(sum(L))

ansR = [sum(R)]
for i in range(N):
  heapq.heappush(R,-C[-1-i])
  heapq.heappop(R)
  ansR.append(sum(R))

ans = -float('inf')
for i in range(N+1):
  temp = ansL[i]+ansR[-1-i]
  ans = max(ans,temp)
#print(ansL,ansR)
print(ans)

Fixed submission:
import heapq

N = int(input())
A = list(map(int,input().split()))
C = A[N:(2*N)]

L = []
R = []
for i in range(N):
  heapq.heappush(L,A[i]) #左側にAの左側からN個を追加
  heapq.heappush(R,-A[-1-i]) #右側数列にAの右側からN個を追加。多いほうから取り出すので-1倍

#左側の総和を求める。
ansL = [sum(L)]
for i in range(N):
  heapq.heappush(L,C[i])
  rmv = heapq.heappop(L)
  temp = ansL[i] + C[i] - rmv #一つ前の答え＋今新しく加えた数－最小値
  ansL.append(temp)
  #ansL.append(sum(L)) #sum(L)がO(N)かかっている？

ansR = [sum(R)]
for i in range(N):
  heapq.heappush(R,-C[-1-i])
  rmv = heapq.heappop(R)
  temp = ansR[i] - C[-1-i] - rmv
  ansR.append(temp)
  #ansR.append(sum(R)) #sum(R)がO(N)かかっている？

ans = -float('inf')
for i in range(N+1):
  temp = ansL[i]+ansR[-1-i]
  ans = max(ans,temp)
#print(ansL,ansR)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

N = int(input())
A = list(map(int,input().split()))
C = A[N:(2*N)]

L = []
R = []
for i in range(N):
  heapq.heappush(L,A[i]) #左側にAの左側からN個を追加
  heapq.heappush(R,-A[-1-i]) #右側数列にAの右側からN個を追加。多いほうから取り出すので-1倍

#左側の総和を求める。
ansL = [sum(L)]
for i in range(N):
  heapq.heappush(L,C[i])
  heapq.heappop(L)
  ansL.append(sum(L))

ansR = [sum(R)]
for i in range(N):
  heapq.heappush(R,-C[-1-i])
  heapq.heappop(R)
  ansR.append(sum(R))

ans = -float('inf')
for i in range(N+1):
  temp = ansL[i]+ansR[-1-i]
  ans = max(ans,temp)
#print(ansL,ansR)
print(ans)

Fixed submission:
import heapq

N = int(input())
A = list(map(int,input().split()))
C = A[N:(2*N)]

L = []
R = []
for i in range(N):
  heapq.heappush(L,A[i]) #左側にAの左側からN個を追加
  heapq.heappush(R,-A[-1-i]) #右側数列にAの右側からN個を追加。多いほうから取り出すので-1倍

#左側の総和を求める。
ansL = [sum(L)]
for i in range(N):
  heapq.heappush(L,C[i])
  rmv = heapq.heappop(L)
  temp = ansL[i] + C[i] - rmv #一つ前の答え＋今新しく加えた数－最小値
  ansL.append(temp)
  #ansL.append(sum(L)) #sum(L)がO(N)かかっている？

ansR = [sum(R)]
for i in range(N):
  heapq.heappush(R,-C[-1-i])
  rmv = heapq.heappop(R)
  temp = ansR[i] - C[-1-i] - rmv
  ansR.append(temp)
  #ansR.append(sum(R)) #sum(R)がO(N)かかっている？

ans = -float('inf')
for i in range(N+1):
  temp = ansL[i]+ansR[-1-i]
  ans = max(ans,temp)
#print(ansL,ansR)
print(ans)
Buggy python submission (verdict: Runtime Error):
H,W,K = map(int,input().split())
Room = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  for j in range(W):
    if temp[j] == "S":
      sx = i;sy =j
  Room.append(temp)
#print(sx,sy)
L = set([])
def dfs(x,y,stp):
  if x<0 or x>= H or y<0 or y>= W:
    print(1)
    exit()
  if Room[x][y] == "#":
    return
  if stp <= K:
    L.add((x,y))
    if stp == K:
      return
  stp +=1
  dfs(x+1,y,stp)
  dfs(x-1,y,stp)
  dfs(x,y+1,stp)
  dfs(x,y-1,stp)

dfs(sx,sy,0)
INF = float("inf")
ans = INF

for t in L:
  x,y = t[0],t[1]
  nokori = min(x,H-x,y,W-y)
  step = (nokori+K-1)//K + 1 #1は最初のステップ
  ans = min(ans,step)
print(ans)
        
        
        
              

Fixed submission:
import sys
sys.setrecursionlimit(500000) #これがないと再帰の回数オーバーでエラー出る。
from collections import deque
INF = float("inf")
H,W,K = map(int,input().split())
Room = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  for j in range(W):
    if temp[j] == "S":
      sx = i;sy =j
  Room.append(temp)
#print(sx,sy)
d = [(1,0),(-1,0),(0,1),(0,-1)]

R = [[INF]*W for _ in range(H)]
R[sx][sy] = 0
reach = set([])
reach.add((sx,sy))
Q = deque([[sx,sy]])
while Q:
  x,y = Q.popleft()
  if x==0 or x==H-1 or y==0 or y==W-1:
    print(1)
    exit()
  if R[x][y] == K:
    #L.add((x,y))
    #if stp == K:
    continue
  #stp +=1
  for i in range(4):
    nx = x+d[i][0]
    ny = y+d[i][1]
    #print(nx,ny)
    if nx<0 or nx>=H or ny<0 or ny>= W or Room[nx][ny] == "#" or R[nx][ny] != INF:
      continue
    reach.add((nx,ny))
    R[nx][ny] = R[x][y] + 1
    Q.append([nx, ny])
    #print(Q)

ans = INF

for t in reach:
  x,y = t[0],t[1]
  nokori = min(x,H-1-x,y,W-1-y)
  step = (nokori+K-1)//K + 1 #1は最初のステップ
  ans = min(ans,step)
print(ans)
Buggy python submission (verdict: Runtime Error):
import itertools
import sys

N, M = map(int,input().split())

if M < N-1:
  print(0)
  sys.exit()

p = [i for i in range(N)] #0スタート
root = []

for i in range(M):
  a,b = map(int,input().split())
  root.append([a-1,b-1])

#print(root)
pattern = list(itertools.permutations(p))

ans = 0
for i in range(len(pattern)):
  Flag = [0]*N
  Flag[0] = 1
  now = 0
  last = False
  for j in range(N-1):
    if now == root[pattern[i][j]][0]:
      now = root[pattern[i][j]][1]
    elif now == root[pattern[i][j]][1]:
      now = root[pattern[i][j]][0]
    else:
      break
    if Flag[now] != 0:
      break
    else:
      Flag[now] = 1
      if j == N-2:
        last = True
  if last:
    ans += 1
print(ans)

Fixed submission:
import itertools
import sys

N, M = map(int,input().split())

if M < N-1:
  print(0)
  sys.exit()

p = [i for i in range(N)] #点の数
root = []
for i in range(M):
  a,b = map(int,input().split())
  root.append((a-1,b-1))

#たどる点の順番の全探索
pattern = list(itertools.permutations(p))
#print(pattern)

ans = 0
for i in range(len(pattern)):
  if pattern[i][0] != 0:
    break
  Flag = True
  for j in range(N-1):
    if (pattern[i][j], pattern[i][j+1]) in root:
      continue
    elif (pattern[i][j+1], pattern[i][j]) in root:
      continue
    else:
      Flag = False
      break
  if Flag:
    ans += 1
print(ans)

Buggy python submission (verdict: Runtime Error):
import itertools

N, M = map(int,input().split())

p = [i for i in range(N)] #0スタート
root = []

for i in range(M):
  a,b = map(int,input().split())
  root.append([a-1,b-1])

#print(root)
pattern = list(itertools.permutations(p))

ans = 0
for i in range(len(pattern)):
  Flag = [0]*N
  Flag[0] = 1
  now = 0
  last = False
  for j in range(N-1):
    if now == root[pattern[i][j]][0]:
      now = root[pattern[i][j]][1]
    elif now == root[pattern[i][j]][1]:
      now = root[pattern[i][j]][0]
    else:
      break
    if Flag[now] != 0:
      break
    else:
      Flag[now] = 1
      if j == N-2:
        last = True
  if last:
    ans += 1
print(ans)

Fixed submission:
import itertools
import sys

N, M = map(int,input().split())

if M < N-1:
  print(0)
  sys.exit()

p = [i for i in range(N)] #点の数
root = []
for i in range(M):
  a,b = map(int,input().split())
  root.append((a-1,b-1))

#たどる点の順番の全探索
pattern = list(itertools.permutations(p))
#print(pattern)

ans = 0
for i in range(len(pattern)):
  if pattern[i][0] != 0:
    break
  Flag = True
  for j in range(N-1):
    if (pattern[i][j], pattern[i][j+1]) in root:
      continue
    elif (pattern[i][j+1], pattern[i][j]) in root:
      continue
    else:
      Flag = False
      break
  if Flag:
    ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
k, s = map(int, input().split())

ans = 0
for i in range(0,k+1):
  for j in range(0,k+1):
    if i+j <= s and s-(i+j) <= k:
      ans += 1
print(ans)

Fixed submission:
s = str(input())

for i in range(len(s)):
  if s[i] == ",":
    s = s[:i]+" "+s[i+1:]
print(s)
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
INF = float("inf")
load = [[[INF, 0] for _ in range(N)] for _ in range(N)]
#print(load)
#dis = [[] for _ in range(N)]
#ID = [0 for _ in range(M)] #、0は未使用、1は使用
for i in range(M):
  a,b,c = map(int,input().split())
  a-=1;b-=1
  load[a][b] = [c,0]
  load[b][a] = [c,0]
  #dis[a].append([b,i])
  #dis[b].append([a,i])
#for i in range(N):
for i in range(N):
  load[i][i] = [0,0]
#print(load)

for k in range(N):
  for i in range(N):
    for j in range(N):
      if load[i][j][0] > load[i][k][0]+load[j][k][0]:
        load[i][j][1] = 1
#print(load)
ans = 0
for i in range(N):
  for j in range(i+1,M):
    if load[i][j][1] == 1:
      ans += 1
print(ans)

Fixed submission:
import heapq
N,M = map(int,input().split())
INF = float("inf")
edge = [[] for _ in range(N)]
#print(load)
#dis = [[] for _ in range(N)]
List = [] #0は未使用、1は使用
for i in range(M):
  a,b,c = map(int,input().split())
  a-=1;b-=1
  edge[a].append([c,b,i])
  edge[b].append([c,a,i])
  List.append([c,a,b,i])

def dijkstra_heap(s):
  d = [INF for _ in range(N)]
  used = [True for _ in range(N)]
  d[s] = 0
  used[s] = False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while len(edgelist):
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]: #すでに探索済みの場合にはスキップ
      continue
    v = minedge[1]
    d[v] = minedge[0]
    #L.add(minedge[2]) #この道を使用したと記録
    used[v] = False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,[e[0]+d[v],e[1],e[2]])
  return d

L = set([])
for i in range(N):
  dist = dijkstra_heap(i)
  for c, s, g, ID in List: #道のリストの一つ一つの点を見て、それが最短距離で使われているか確認
    if dist[s] + c == dist[g]:
      L.add(ID)
ans = M -len(L)
print(ans)
Buggy python submission (verdict: Runtime Error):
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

      
from collections import defaultdict
 
N, K, L = map(int, input().split())

# 道路のUnionFind
uf1 = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    uf1.union(p - 1, q - 1)
 
# 鉄道のUnionFind
uf2 = UnionFind(N)
for i in range(L):
    r, s = map(int, input().split())
    uf2.union(r - 1, s - 1)
 
# 道路と鉄道の連結の組み合わせ（根のペアのカウント）
c = {}
for i in range(N):
    if (uf1.find(i), uf2.find(i)) in c:
      c[(uf1.find(i), uf2.find(i))] += 1
    else:
      c[(uf1.find(i), uf2.find(i))] = 1      

# 回答を出力
for i in range(N):
    print(c[(uf1.find(i), uf2.find(i))])

Fixed submission:
from collections import defaultdict
 
N, K, L = map(int, input().split())

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

# 道路のUnionFind
uf1 = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    uf1.union(p - 1, q - 1)
 
# 鉄道のUnionFind
uf2 = UnionFind(N)
for i in range(L):
    r, s = map(int, input().split())
    uf2.union(r - 1, s - 1)
 
# 道路と鉄道の連結の組み合わせ（根のペアのカウント）
c = defaultdict(int)
for i in range(N):
    c[(uf1.find(i), uf2.find(i))] += 1

# 回答を出力
for i in range(N):
    print(c[(uf1.find(i), uf2.find(i))])
Buggy python submission (verdict: Time Limit Exceeded):
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
n = int(input())
cnt = 0
for i in range(1,n):
  d = make_divisors(n-i)
  cnt += len(d)
print(cnt)

    

Fixed submission:
n = int(input())
cnt = 0
for i in range(1,n):
  cnt += (n-1)//i
print(cnt)
Buggy python submission (verdict: Runtime Error):
S = input()
T = input()
l = len(T)
ans = l
print(ans)
for i in range(l):
  for j in range(l):
    if (i<=j):
      if T[i:j+1] in S:
        if f >= i and f + (l-j) <= len(S):
          ans = min(ans, l - (j+1-i))
print(ans)
        

Fixed submission:
S = input()
T = input()
ls = len(S)
lt = len(T)
ans = lt
for i in range(0,ls-lt+1):
  m = 0
  for j in range(lt):
    if S[i:i+lt][j]!=T[j]:
      m += 1
  ans = min(ans,m)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(0,N-1):
  for j in range(i+1,N):
    ans += A[i]*A[j]%(10**9+7)
print(ans%(10**9+7))

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
inf = 10**9+7
aa = [0]*N

for i in range(N):
  aa[i] = A[i]**2
X = sum(A)**2 - sum(aa)
print((X//2)%inf)
Buggy python submission (verdict: Time Limit Exceeded):
import collections
N, M = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
  A[i],B[i] = map(int,input().split())
ans = 0
f = [-1]*N
for i in range(M):

  if f[A[i]-1] == -1 and f[B[i]-1] == -1:
    f[A[i]-1] = i
    f[B[i]-1] = i
  elif f[A[i]-1] != -1 and f[B[i]-1] == -1:
    f[B[i]-1] = f[A[i]-1]
  elif f[A[i]-1] == -1 and f[B[i]-1] != -1:
    f[A[i]-1] = f[B[i]-1]
  else:
    f = [f[B[i]-1] if j == f[A[i]-1] else j for j in f]
ff = [i for i in f if i != -1]
if ff != []:
  print(max(collections.Counter(ff).values()))
else:
  print(1)

Fixed submission:
# cf. 16315733
N, M = list(map(int, input().split()))
# upperは、根なら-その木の長さを、枝ならその木の根の要素のインデックスを指す。
upper = [-1] * N
# xの根を返す
def root(x):
  # xが根なら
  if upper[x] < 0:
    return x
  # xが枝なら
  else:
    # 根のインデックスをさかのぼる
    upper[x] = root(upper[x])
    # 根のインデックスを返す
    return upper[x]

# x,yが同じグループにあるかどうか判定する
def equiv(x, y):
  return root(x) == root(y)

def unite(x, y):
  x, y = root(x), root(y)
  if x != y:
    if upper[y] < upper[x]:
      #xとyの値をスワップ、必ずupper[y] >= upper[x]とするつまりxのほうが高い
      x,y = y,x
    # 要素の数を足す：結合後の要素の数を求める
    upper[x] += upper[y]
    # yの根をxにする（木が高い方を根にする）
    upper[y] = x
  return x == y

for i in range(M):
  a, b = list(map(int, input().split()))
  unite(a-1, b-1)
print(-min(upper))

Buggy python submission (verdict: Runtime Error):
import collections
N, M = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
  A[i],B[i] = map(int,input().split())
ans = 0
f = [-1]*N
for i in range(M):
  if f[A[i]-1] == -1 and f[B[i]-1] == -1:
    f[A[i]-1] = i
    f[B[i]-1] = i
  elif f[A[i]-1] != -1 and f[B[i]-1] == -1:
    f[B[i]-1] = f[A[i]-1]
  else:
    f[A[i]-1] = f[B[i]-1]
ff = [i for i in f if i != -1]
print(max(collections.Counter(ff).values()))

Fixed submission:
# cf. 16315733
N, M = list(map(int, input().split()))
# upperは、根なら-その木の長さを、枝ならその木の根の要素のインデックスを指す。
upper = [-1] * N
# xの根を返す
def root(x):
  # xが根なら
  if upper[x] < 0:
    return x
  # xが枝なら
  else:
    # 根のインデックスをさかのぼる
    upper[x] = root(upper[x])
    # 根のインデックスを返す
    return upper[x]

# x,yが同じグループにあるかどうか判定する
def equiv(x, y):
  return root(x) == root(y)

def unite(x, y):
  x, y = root(x), root(y)
  if x != y:
    if upper[y] < upper[x]:
      #xとyの値をスワップ、必ずupper[y] >= upper[x]とするつまりxのほうが高い
      x,y = y,x
    # 要素の数を足す：結合後の要素の数を求める
    upper[x] += upper[y]
    # yの根をxにする（木が高い方を根にする）
    upper[y] = x
  return x == y

for i in range(M):
  a, b = list(map(int, input().split()))
  unite(a-1, b-1)
print(-min(upper))
Buggy python submission (verdict: Runtime Error):
N = int(input())
X = int(input(),2)

def pcrem(n,cnt):
  if (n==0):
    print(cnt)
    return 0
  pc = bin(n).count("1")
  pcrem(n%pc,cnt+1)

for i in range(N):
  f = X^(1<<N-i-1)
  pcrem(f,0)

Fixed submission:
L,R,d = map(int,input().split())
ans=0
for i in range(L,R+1):
  if (i%d == 0):
    ans+=1
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
N =int(input())
for i in range(N):
  count = 0
  M = int(math.sqrt(i+1))
  for j in range(M):
    for k in range(M):
      for l in range(M):
        if((j+1)**2 + (k+1)**2 + (l+1)**2 + (j+1)*(k+1) + (k+1)*(l+1) + (l+1)*(j+1) == i+1):
          count+=1
        if ((j+1)**2 + (k+1)**2 + (l+1)**2 + (j+1)*(k+1) + (k+1)*(l+1) + (l+1)*(j+1) > i+1):
          break
  print(count)

Fixed submission:
import math
N = int(input())
ans_list = [0 for i in range(N)]
index = int(math.sqrt(N))

for x in range(1,index):
  for y in range(1,index):
    for z in range(1,index):
      n = x**2 + y**2 + z**2 + x*y + y*z + z*x 
      if (n <= N):
        ans_list[n-1] += 1
for i in range(N):
  print(ans_list[i])

Buggy python submission (verdict: Time Limit Exceeded):
import math
N =int(input())
for i in range(N):
  count = 0
  M = int(math.sqrt(i+1))
  for j in range(M):
    for k in range(M):
      for l in range(M):
        if((j+1)**2 + (k+1)**2 + (l+1)**2 + (j+1)*(k+1) + (k+1)*(l+1) + (l+1)*(j+1) == i+1):
          count+=1
  print(count)

Fixed submission:
import math
N = int(input())
ans_list = [0 for i in range(N)]
index = int(math.sqrt(N))

for x in range(1,index):
  for y in range(1,index):
    for z in range(1,index):
      n = x**2 + y**2 + z**2 + x*y + y*z + z*x 
      if (n <= N):
        ans_list[n-1] += 1
for i in range(N):
  print(ans_list[i])

Buggy python submission (verdict: Runtime Error):
N = int(input())
X = int(input(),2)

def pcrem(n,cnt):
  if (n==0):
    print(cnt)
    return 0
  pc = bin(n).count("1")
  pcrem(n%pc,cnt+1)

for i in range(N):
  f = X^(1<<N-i-1)
  pcrem(f,0)


Fixed submission:
import math
N = int(input())
ans_list = [0 for i in range(N)]
index = int(math.sqrt(N))

for x in range(1,index):
  for y in range(1,index):
    for z in range(1,index):
      n = x**2 + y**2 + z**2 + x*y + y*z + z*x 
      if (n <= N):
        ans_list[n-1] += 1
for i in range(N):
  print(ans_list[i])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
prd = 1
flag = False
if (0 in A):
  print(0)
else:
  for i in range(len(A)):
    prd = prd * A[i]
    if (prd > 10**18):
      flag = True
  if (flag):
    print(-1)
  else:
    print(prd)

Fixed submission:
def main():
  N = int(input())
  A = list(map(int, input().split()))
  if 0 in A:
    print(0)
    return
  prd = 1
  for a in A:
    prd *= a
    if prd > 1000000000000000000:
      print(-1)
      return
  print(prd)

main()
Buggy python submission (verdict: Runtime Error):
import collections
import bisect
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

N = int(input())
c = collections.Counter(prime_factorize(N))
sums = []
s=1
ans = 0
if c.values():
  while s <= max(c.values()):
    sums.append(s)
    s += s+1
  for v in c.values():
    idx = bisect.bisect_left(sums,v)
    
    if idx <= len(c.values()):
      if sums[idx] == v:
        ans += idx+1
      else:
        ans += idx
    else:
      ans += max(sums)
print(ans)

Fixed submission:
import collections
import bisect
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

N = int(input())
c = collections.Counter(prime_factorize(N))
sums = []
s=1
ans = 0
for v in c.values():
  count = 0
  for i in range(1,v+1):
    if count+i > v:
      break
    else:
      count += i
      ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())
query = []
for i in range(Q):
  tq = list(input().split())
  if (len(tq) == 1):
    query.append(1)
  if (len(tq) == 3):
    query.append([int(tq[1]),tq[2]])
eo = 1
for q in query:
  if q == 1:
    eo = eo*(-1)
  else:
    eoq = eo*q[0]
    if eoq == 1 or eoq == -2:
      S = q[1] + S
    else:
      S = S + q[1]
if eo == -1:
  S = S[::-1]
print(S)

Fixed submission:
from collections import deque
S = input()
ds = deque(S)
Q = int(input())
query = []
for i in range(Q):
  tq = list(input().split())
  if (len(tq) == 1):
    query.append(1)
  if (len(tq) == 3):
    query.append([int(tq[1]),tq[2]])
eo = 1
for q in query:
  if q == 1:
    eo = eo*(-1)
  else:
    eoq = eo*q[0]
    if eoq == 1 or eoq == -2:
      ds.extendleft(q[1])
    else:
      ds.extend(q[1])
jds = "".join(ds)
if eo == -1:
  jds = jds[::-1]
print(jds)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())
query = []
for i in range(Q):
  tq = list(input().split())
  if (len(tq) == 1):
    query.append(1)
  if (len(tq) == 3):
    query.append([int(tq[1]),tq[2]])
for q in query:
  if q == 1:
    S = S[::-1]
  else:
    if q[0] == 1:
      S = q[1] + S
    else:
      S = S + q[1]
print(S)

Fixed submission:
from collections import deque
S = input()
ds = deque(S)
Q = int(input())
query = []
for i in range(Q):
  tq = list(input().split())
  if (len(tq) == 1):
    query.append(1)
  if (len(tq) == 3):
    query.append([int(tq[1]),tq[2]])
eo = 1
for q in query:
  if q == 1:
    eo = eo*(-1)
  else:
    eoq = eo*q[0]
    if eoq == 1 or eoq == -2:
      ds.extendleft(q[1])
    else:
      ds.extend(q[1])
jds = "".join(ds)
if eo == -1:
  jds = jds[::-1]
print(jds)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import bisect
N = int(input())
L = list(map(int, input().split()))
ans = 0
LS = sorted(L)
l = len(LS)
for i in range(l):
  for j in range(l):
    if i < j:
      for k in range(j+1,l):
        if LS[i]+LS[j] > LS[k]:
          ans += 1
        else:
          break
print(ans)


Fixed submission:
import itertools
import bisect
N = int(input())
L = list(map(int, input().split()))
ans = 0
LS = sorted(L)
l = len(LS)
for i in range(l):
  for j in range(l):
    if i < j:
      k = bisect.bisect_left(LS,LS[i]+LS[j])
      ans += k-j-1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
N = int(input())
L = list(map(int, input().split()))
ans = 0
for x in itertools.combinations(L, 3):
  if x[0] < x[1] + x[2] and x[1] < x[0] + x[2] and x[2] < x[0] + x[1]:
    ans += 1
print(ans)

Fixed submission:
import itertools
import bisect
N = int(input())
L = list(map(int, input().split()))
ans = 0
LS = sorted(L)
l = len(LS)
for i in range(l):
  for j in range(l):
    if i < j:
      k = bisect.bisect_left(LS,LS[i]+LS[j])
      ans += k-j-1
print(ans)
Buggy python submission (verdict: Runtime Error):
N, A, B = map(int, innput().split())
print(min([N*A,B]))

Fixed submission:
N, A, B = map(int, input().split())
print(min([N*A,B]))
Buggy python submission (verdict: Runtime Error):
W, H, x, y = map(float, input().split())
if x == W/2 & y == H/2:
  chohuku = 1
else:
  chohuku = 0
print(str((H*W)/2) + " " + str(chohuku))


Fixed submission:
W, H, x, y = map(float, input().split())
if x == W/2 and y == H/2:
  chohuku = 1
else:
  chohuku = 0
print(str((H*W)/2) + " " + str(chohuku))
Buggy python submission (verdict: Runtime Error):
P, Q, R = map(int, input().split())
print(min[P+Q,Q+R,R+P])

Fixed submission:
P, Q, R = map(int, input().split())
print(min([P+Q,Q+R,R+P]))