Harryxun/stf_run huggingface dataset:
def main():
    import sys
    input = sys.stdin.readline
    from bisect import bisect_left, bisect_right

    N, M = map(int, input().split())
    AB = []
    for i in [0]*N:
        A, B = map(int, input().split())
        AB.append((A, B))
    AB.sort(key=lambda x:x[0])

    POWER = 1
    x = [0] * (N+1)
    x[0] = AB[0][POWER]
    for i in range(N-1):
        x[i+1] = AB[i][POWER] ^ AB[i+1][POWER]
    x[N] = AB[N-1][POWER]

    graph = [ [] for _ in [0]*(N+1) ]
    for i in range(1, M+1):
        L, R = map(int, input().split())
        L = bisect_left(AB, (L, 0))
        R = bisect_right(AB, (R, 1))
        graph[L].append((R, i))
        graph[R].append((L, i))

    ans = []
    POS = 0
    ID = 1
    def dfs(v):
        used[v] = True
        res = x[v]
        for edge in graph[v]:
            if used[edge[POS]]: continue
            r = dfs(edge[POS])
            if r: ans.append(edge[ID])
            res ^= r
        return res

    used = [False] * (N+1)
    for i in range(N+1):
        if used[i]: continue
        if dfs(i):
            print(-1)
            return

    print(len(ans))
    ans.sort()
    print(*ans)


main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    from bisect import bisect_left, bisect_right
    sys.setrecursionlimit(10**9)

    N, M = map(int, input().split())
    AB = []
    for i in [0]*N:
        A, B = map(int, input().split())
        AB.append((A, B))
    AB.sort(key=lambda x:x[0])

    POWER = 1
    x = [0] * (N+1)
    x[0] = AB[0][POWER]
    for i in range(N-1):
        x[i+1] = AB[i][POWER] ^ AB[i+1][POWER]
    x[N] = AB[N-1][POWER]

    graph = [ [] for _ in [0]*(N+1) ]
    for i in range(1, M+1):
        L, R = map(int, input().split())
        L = bisect_left(AB, (L, 0))
        R = bisect_right(AB, (R, 1))
        graph[L].append((R, i))
        graph[R].append((L, i))

    ans = []
    POS = 0
    ID = 1
    def dfs(v):
        used[v] = True
        res = x[v]
        for edge in graph[v]:
            if used[edge[POS]]: continue
            r = dfs(edge[POS])
            if r: ans.append(edge[ID])
            res ^= r
        return res

    used = [False] * (N+1)
    for i in range(N+1):
        if used[i]: continue
        if dfs(i):
            print(-1)
            return

    print(len(ans))
    ans.sort()
    print(*ans)


main()
n = int(input())
s = input()
s2 = input()
if len(s)==2:
    print(3)
    exit()
i = 0

d = []#0が縦、1が横
while i<n:
    try:
        if s[i]==s[i+1]:
            d.append(1)
            i+=1
        else:
            d.append(0)
        i+=1
    except:
        break

ans = 1
#print(d)
if d[0]==0:
    ans = 3
else:
    ans = 6
mod = 10**9+7
for j in range(1,len(d)):
    if d[j]==0:
        if d[j-1]==0:
            ans*=2
    else:
        if d[j-1]==1:
            ans*=3
        else:
            ans*=2####
    ans%=mod
    

    
print(ans)

### FIXED CODE ###

n = int(input())
s = input()+"0"
s2 = input()##要らない

i = 0

d = []#0が縦、1が横
while i<n:
    try:
        if s[i]==s[i+1]:
            d.append(1)
            i+=1
        else:
            d.append(0)
        i+=1
    except:
        break

ans = 1
#print(d)
if d[0]==0:
    ans = 3
else:
    ans = 6
mod = 10**9+7
for j in range(1,len(d)):
    if d[j]==0:
        if d[j-1]==0:
            ans*=2
    else:
        if d[j-1]==1:
            ans*=3
        else:
            ans*=2####
    ans%=mod
    

    
print(ans)
b = input()
ans =0
cnt =0
 
for i in b:
    if i == 'A':
        cnt+=1
    elif i == 'T':
        cnt+=1
    elif i == 'C':
        cnt+=1
    elif i == 'G':
        cnt+=1
    else:
        if ans < cnt:
            ans = cnt
            cnt = 0
 
print(ans)
b = input()
ans =0
cnt =0

for i in b:
    if i == 'A':
        cnt+=1
    elif i == 'T':
        cnt+=1
    elif i == 'C':
        cnt+=1
    elif i == 'G':
        cnt+=1
    else:
        if ans < cnt:
            ans = cnt
        cnt = 0

print(ans)

### FIXED CODE ###

b = input()
ans = []
cnt = 0

for i in b:
    if i in "ACTG":
        cnt+=1
    else:
        ans.append(cnt)
        cnt = 0

ans.append(cnt)

print(max(ans))
a = int(input())
print(a.count(o)) 

### FIXED CODE ###

a = input()
print(a.count("1"))
N,M=map(int,input().split())
SC=[list(map(int,input().split())) for i in range(M)]
begin=10**N-1
end=10**N
if N==1:
  print(SC[0][1])
for i in range(begin,end):
  i=str(i)
  for s,c in SC:
    if i[s-1]!=c:
      break
  else:
    print(i)
    exit()
print(-1)

### FIXED CODE ###

N,M = map(int,input().split())
sc = [tuple(map(int,input().split())) for _ in range(M)]
sc = set(sc)
 
ans = -1
begin = 10**(N-1) - (1 if N == 1 else 0)
end = 10**N
for i in range(begin,end):
    num = str(i)
    for s,c in sc:
        if int(num[s-1]) != c:
            break
    else: ans = i
    if ans != -1:
        break
 
print(ans)
a=input()
b=input()

ans={1,2,3}
ans.remove(a)
ans.remove(b)

if ans == {a}
    print("a")
if ans == {b}
    print("b")
if ans == {c}
    print("c")

### FIXED CODE ###

a = input("")
b = input("")

a = int(a)
b = int(b)

print(6-a-b)
N,X = map(int, input().split())
List = [int(x) for x in input().split()]

List.append(X)
List.sort()

distance = []
for i in range(N):
    distance.append(List[i+1]-List[i])

d_min = min(distance)

num_list = []

c = 1
while c <= d_min:
    if d_min%c == 0:
        num_list.append(c)
    c += 1

j = len(num_list)-1
c2 = 0
while j >= 0:
    for k in range(len(distance)):
        if distance[k]%num_list[j] != 0:
            break
        else:
            c2 += 1
    if c2 == len(distance):
        ans = num_list[j]
        break
    j -= 1

print(ans)

### FIXED CODE ###

N,X = map(int, input().split())
List = [int(x) for x in input().split()]
 
import math
List.append(X)
List.sort()
 
distance = []
for i in range(N):
    distance.append(List[i+1]-List[i])
 
d_min = min(distance)
 
num_list = []
 
c = 1
while c <= math.sqrt(d_min):
    if d_min%c == 0:
        num_list.append(c)
    c += 1
 
num_list2 = [0]*len(num_list)
for i in range(len(num_list)):
    num_list2[len(num_list)-i-1] = int(d_min/num_list[i])
 
num_list = num_list + num_list2

num_list.append(d_min)

j = len(num_list)-1

while j >= 0:
    c2 = 0
    for k in range(len(distance)):
        if distance[k]%num_list[j] == 0:
            c2 += 1
    if c2 == len(distance):
        ans = num_list[j]
        j = 0
    j -= 1
 
print(ans)
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.buffer.readline().rstrip()
rs = lambda: sys.stdin.buffer.readline().split()
ri = lambda: int(sys.stdin.buffer.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.buffer.readline().split()))

n = ri()
ans = 0
d = 2
for d in range(2, int(n**0.5) + 1):
    e = d
    while n%d == 0:
        n //= d
        d *= d
        ans += 1
    while n%e == 0:
        n //= e
if n >= d:
    ans += 1
print(ans)




### FIXED CODE ###

a, b = input().split()
b = b.replace('.', '')
a = int(a)
b = int(b)
print((a*b)//100)
N = int(input())
T, A = map(int, input().split())
H = list(map(int, input().split()))

minT = 50

for i in range(N):
  aveT = T - H[i] * 0.006
  minT = min(minT, abs(aveT - A))
  #print(minT)
  if minT == abs(aveT - A):
    ans = i + 1
    
print(ans)

### FIXED CODE ###

N = int(input())
T, A = map(int, input().split())
H = list(map(int, input().split()))

minT = 651
ans = 1

for i in range(N):
  aveT = T - H[i] * 0.006
  minT = min(minT, abs(aveT - A))
  #print(minT)
  if minT == abs(aveT - A):
    ans = i + 1
    
print(ans)
#!/usr/bin/env python3
#ABC131 E
import sys
import math
import networkx as nx

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

if K > (N - 1)*(N - 2) // 2:
    print(-1)
    exit()

print((N - 1)*(N - 2) // 2 + (N - 1) - K)
for i in range(N - 1):
    print(1,i+2)
k = 2
for i in range(N,2,-1):
    if (i - 1)*(i - 2)//2 == K:
        break
    for j in range(k,N):
        print(k,j+1)
    k += 1

### FIXED CODE ###

#!/usr/bin/env python3
#ABC131 E
import sys
import math

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

if K > (N - 1)*(N - 2) // 2:
    print(-1)
    exit()

print((N - 1)*(N - 2) // 2 + (N - 1) - K)
for i in range(N - 1):
    print(1,i+2)
s = 2
t = 3
for i in range((N - 1)*(N - 2) // 2 - K):
    print(s,t)
    t += 1
    if t > N:
        s += 1
        t = s + 1
S = input()
print(S[1])
N = len(S)
print(N)

### FIXED CODE ###

L = float(input())
ans = L * L * L / 27.0
print(ans)
import math

# D - Maximum Average Sets
# 問題URL:http://abc057.contest.atcoder.jp/tasks/abc057_d

# N:商品の数　A個以上B個以下の範囲で選ぶ
N, A, B = map(int, input().split())
# C：最大価値組み合わせ総数
C = 0

# 商品価値をリストに入れる
V = [int(value) for value in input().split()]
# 商品価値が高い順に並び替え
V.sort(reverse=True)

# 商品価値が高いものから出来るだけ少なく（＝A個）選ぶのが最も平均価値が高くなる
S = V[0:A]
ave = sum(S) / A
print(ave)

Vs = V.count(min(S)) # A個選んだ中で最も低い価値を持つ商品は、もともとの商品リストの中にいくつあるか
Ss = S.count(min(S)) # A個選んだ時中で最も低い価値を持つ商品はいくつあるか

if min(S) == max(S): # もしもA個選んだ中の商品価値が全て同じだったら
    i = A
    while i <= B and V[-i] == min(S):
        C = C + math.factorial(Vs) // ( math.factorial(Vs - i) * math.factorial(i))
        i += 1
    

else: # 商品価値が均一でなかったのなら
    # nCk = n! /( (n-k)! * k! )に基づきCを計算
    C = math.factorial(Vs) // (math.factorial(Vs - Ss) * math.factorial(Ss) )

print(C)

### FIXED CODE ###

# 元ソースコード：http://abc057.contest.atcoder.jp/submissions/1183710
# 初心者の実験用です

import math
N,A,B = map(int,input().split())
V = list(map(int,input().split()))
V.sort()
S = V[-A:]
avgmax = sum(S) / A
print(avgmax)
 
Vs = V.count(min(S))
Ss = S.count(min(S))
if min(S) != max(S):
	C = math.factorial(Vs) // (math.factorial(Vs -Ss) * math.factorial(Ss))
	print(C)
else:
	i = A
	C = 0
	while i <= B and V[-i] == min(S):
		c = math.factorial(Vs) // (math.factorial(Vs -i) * math.factorial(i))
		C = C + c
		i = i + 1
	print(C)
s = input()
if s[:4] == 2019 and s[6] <= 4 or s[:4] < 2019:
  print("Heisei")
else:
  print("TBD")

### FIXED CODE ###

s = input()
 
if s <= '2019/04/30':
    print('Heisei')
else:
    print('TBD')
# 0～7で5を作るには
# 0123467 5 7643210 5
# M = 1がxor sum = 0とならず例外

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

def solve(M,K):
  if M == 0:
    if K == 0:
      return '0 0'
   	else:
      return '-1'
  if M == 1:
    if K == 0:
      return '0 1 1 0'
    else:
      return '-1'
  U = 1<<M
  if K >= U:
    return -1
  other = [x for x in range(U) if x != K]
  result = other + [K] + other[::-1] + [K]
  return ' '.join(result)

answer = solve(M,K)
print(answer)

### FIXED CODE ###

# 0～7で5を作るには
# 0123467 5 7643210 5
# M = 1がxor sum = 0とならず例外

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

def solve(M,K):
  if M == 0:
    if K == 0:
      return '0 0'
    else:
      return '-1'
  if M == 1:
    if K == 0:
      return '0 1 1 0'
    else:
      return '-1'
  U = 1<<M
  if K >= U:
    return -1
  other = [str(x) for x in range(U) if x != K]
  result = other + [str(K)] + other[::-1] + [str(K)]
  return ' '.join(result)

answer = solve(M,K)
print(answer)
L,N=(int(i) for i in input().split())
X = []
for i in range(0,N):
    a = int(input())
    X.append(a)
import math
if X[math.ceil(N/2)]<L/2:
  result=X[N-1]
  for i in range (0,math.ceil(N/2)):
    for j in range (N-1,math.ceil(N/2)-1,-1):
      result+=abs(X[j]-X[i])
else:
  result=X[0]
   for i in range (0,math.ceil(N/2)):
    for j in range (N-1,math.ceil(N/2)-1,-1):
      result+=abs(X[i]-X[j])
print(result)

### FIXED CODE ###

a,b,c=(int(i) for i in input().split())
if b+1>=c:
  print(b+c)
else:
  if a+1>=c-b:
    print(b+c)
  else:
    print(2*b+a+1)
s=input()
t=input()
n=0
for i in range(0,len(s)):
	if(s[i]==t[i]):
    	n=n+1
if(n==len(s)):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

s=input()
t=input()
n=0
for i in range(0,len(s)):
    if(s[i]==t[i]):
        n=n+1
if(n==len(s)):
    print("Yes")
else:
    print("No")
class Point(object):
    x = 0.0
    y = 0.0
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __sub__(left, right):
        return Point(left.x - right.x, left.y - right.y)
    #cross
    def __mul__(left, right):
        return left.x * right.y - left.y * right.x

for i in range(int(raw_input())):
    (x1, y1, x2, y2, x3, y3, x4, y4) = [float(i) for i in raw_input().split()]
    a = Point(x1, y1)
    b = Point(x2, y2)
    c = Point(x3, y3)
    d = Point(x4, y4)
    ab = a - b
    cd = c - d
    if(a * b == 0.0):
        print 'YES'
    elif(a * (Point - b) == 0.0):
        print 'YES'
    else:
        print 'NO'

### FIXED CODE ###

for i in range(int(raw_input())):
    (x1, y1, x2, y2, x3, y3, x4, y4) = map(float,raw_input().split())
    x1 -= x2
    y1 -= y2
    x3 -= x4
    y3 -= y4
    if(x1 == 0 or x3 == 0):
        if(x1 == 0 and x3 == 0):
            print 'YES'
        else:
            print 'NO'
    else:
        if(y1 / x1 == y3 / x3):
            print 'YES'
        else:
            print 'NO'
from itertools import combinations
N, A, B, C = [int(i) for i in input().split()]
l_ls = list()
for i in range(N):
    l_ls.append(int(input()))
dis_ls = [(i,[i]) for i in l_ls]
for i in range(2,7):
    dis_ls += [(sum(i),i) for i in combinations(l_ls, i)]
best = 1e9
for hoge in [[A, B, C], [A, C, B],[B, A, C],[B, C, A], [C,B,A],[C,A,B]]:
    _sum = 0
    for target in hoge:
        min = 1e9
        for dis in dis_ls:
            c_sa = abs(dis[0] - target) + 10 * (len(dis[1]) - 1)
            if sa < min:
                min = sa
                min_combi = dis[1]
        _sum += min
        dis_ls = [i for i in dis_ls if len(set(min_combi).intersection(set(i[1]))) == 0]
    if _sum < best:
        best = _sum
print(best)

### FIXED CODE ###

from itertools import product
N, A, B, C = [int(i) for i in input().split()]
l_ls = list()
for i in range(N):
    l_ls.append(int(input()))
best = 1e9
for combi in product(range(4),repeat=N):
    a = [l for l, label in zip(l_ls, combi) if label == 1]
    b = [l for l, label in zip(l_ls, combi) if label == 2]
    c = [l for l, label in zip(l_ls, combi) if label == 3]
    dis = abs(A - sum(a)) + abs(B - sum(b)) + abs(C - sum(c)) \
          + (len(a) + len(b) + len(c) - 3) * 10
    if len(a) * len(b) * len(c) == 0:
        continue
    if best > dis:
        best = dis
print(best)
def main():
    import sys
    input = sys.stdin.readline

    N = list(map(int, list(input()[::-1]))) + [0]

    ans = 0
    for i in range(len(N)-1):
        if N[i] < 5:
            ans += N[i]
        elif N[i] > 5:
            ans += 10 - N[i]
            N[i+1] += 1
        else:
            ans += 5
            if N[i+1] >= 5:
                N[i+1] += 1

    print(ans + N[len(N)-1])

main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    N = list(map(int, list(input()[:-1])))
    N = N[::-1] + [0]

    ans = 0
    for i in range(len(N)-1):
        if N[i] < 5:
            ans += N[i]
        elif N[i] > 5:
            ans += 10 - N[i]
            N[i+1] += 1
        else:
            ans += 5
            if N[i+1] >= 5:
                N[i+1] += 1

    print(ans + N[len(N)-1])

main()
a,b=map(int,input().split())
if a=b:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b=map(int,input().split())
if a==b:
  print("Yes")
else:
  print("No")
import copy
import sys

n, q = map(int, sys.stdin.readline().split())

s = input()

letterPlace = {}

golemGroup = {}

for i, letter in enumerate(list(s)):
  if letter in letterPlace:
    letterPlace[letter].append(i)
  else:
    letterPlace[letter] = [i]
  golemGroup[i] = 1

#print(golemGroup)

move = {
  "R" : 1,
  "L" : -1
}

for _ in range(q):
  spell = sys.stdin.readline().split()
  if spell[0] not in letterPlace:
    continue
  places = letterPlace[spell[0]]
  nextGroup = copy.copy(golemGroup)
  for place in places:
    if place == 0 and spell[1] == "L":
      del(nextGroup[place])
    elif place == n-1 and spell[1] == "R":
      del(nextGroup[place])
    else:
      if place not in golemGroup:
        continue
      if place + move[spell[1]] in golemGroup:
        nextGroup[place + move[spell[1]]] += golemGroup[place]
        del(nextGroup[place])
      else:
        nextGroup[place + move[spell[1]]] = golemGroup[place]
        del(nextGroup[place])
    golemGroup = copy.copy(nextGroup)
    #print(golemGroup)

out = 0
for v in golemGroup.values():
  out += len(v)

print(out)

### FIXED CODE ###

import copy
import sys

n, q = map(int, sys.stdin.readline().split())

s = input()

leftLimit = -1
rightLimit = n

spells =   spell = sys.stdin.readlines()
  
for spell in reversed(spells):
  target, direction = spell.split()
  if direction == "R" and target == s[rightLimit - 1]:
    rightLimit -= 1
    if rightLimit <= 0:
      break
  try:
    if direction == "R" and target == s[leftLimit]:
      if leftLimit != -1:
         leftLimit -= 1
  except Exception as e:
    pass
  if direction == "L" and target == s[leftLimit + 1]:
    leftLimit += 1
    if leftLimit >= n-1:
      break
  try:  
    if direction =="L" and target == s[rightLimit]:
      if rightLimit != n:
        rightLimit += 1
  except Exception as e:
    pass
  #print(target, direction, leftLimit, rightLimit)

print(max(rightLimit - leftLimit - 1 , 0))
s=input()

if s=="Sunny":
  print("Cloudy")
  
elif S=="Cloudy":
  print("Rainy")
  
else:
  print("Sunny")

### FIXED CODE ###

s=input()

if s=="Sunny":
  print("Cloudy")
  
elif s=="Cloudy":
  print("Rainy")
  
else:
  print("Sunny")
W,H,x,y,r=map(int,raw_input().split())
if (x-r)>=0 and W>=(x+r) and (y-r)>=0 and H>=(y+r):
    print "Yes"
else:
    print "No"

### FIXED CODE ###

import sys
(W, H, x, y, r) = [int(i) for i in sys.stdin.readline().split()]
if r <= x <= W - r and r <= y <= H - r:
    print("Yes")
else:
    print("No")
a,b,k = input().strip().split()
a,b,k = [int(a), int(b), int(k)]

if k < a:
	a = a-k
elif k >= a+b:
	a = 0
	b = 0
elif a+b > k > a:
	b = b-(k-a)
	a = 0

print('{} {}'.format(a,b))

### FIXED CODE ###

s,t = input().split()
print(t + s)
n = int(input())
list=[int(input()) for i in range(n)]
max = 0
a = 0
for i in range(n):
  for j in range(n):
    a = abs(list[i] - list[j])
    if a > max:
      max = a
      
if max <= 15:
  print('Yey!')
else:
  print(':(')
    

### FIXED CODE ###

n = 5
list=[int(input()) for i in range(n)]
p = int(input())
max = 0
a = 0
for i in range(n):
  for j in range(n):
    a = abs(list[i] - list[j])
    if a > max:
      max = a
      
if max <= p:
  print('Yay!')
else:
  print(':(')
S = list(input())
K = int(input())
if K == 1:
    print(S[0])
else:
  for x in range(S):
    if int(x) != 1:
      print(S[x])
      break

### FIXED CODE ###

S = list(map(int,input()))
K = int(input())
ans = 1
if K == 1 or S.count(S[0]) == len(S) or S.count(1) == len(S):
    ans = S[0]
else:
  for x in range(K):
    if S[x] != 1:
      ans = S[x]
      break
print(ans)
import sys
import math
for line in sys.stdin:
    a, b = map(int, line.split())
    gcdab = math.gcd(a, b)
    print(gcdab, a // gcdab * b)

### FIXED CODE ###

import sys
def gcd(a, b):
    for i in range(1, a+1):
        if a % i == 0:
            t = a // i
            if b % t == 0:
                return t
for line in sys.stdin:
    a, b = sorted(map(int, line.split()))
    gcdab = gcd(a, b)
    print(gcdab, a // gcdab * b)
from bisect import bisect_left, bisect, insort

def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = i
    if p != -1:
        ans[v] = max(ans[v], ans[p])
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    INF = 10**10
    ans = [INF]*n
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

### FIXED CODE ###

from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)


def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = bisect_left(dp, INF)-1
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [0]*n
    INF = 10**20
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    dp = [INF]*(n+1)
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))
from sys import stdin
[int(x) for x in list(stdin.readline())]

### FIXED CODE ###

print(input().count("1"))
from bisect import bisect_right
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def pf(x):
    ee=[]
    pp=[]
    if x&1==0:
        k=(x&-x).bit_length()-1
        pp.append(2)
        ee.append(k)
        x>>=k
    d=3
    while d**2<=x:
        while x%d==0:
            x//=d
            if pp and pp[-1]==d:ee[-1]+=1
            else:
                pp.append(d)
                ee.append(1)
        d+=2

    if x>1:
        if pp[-1] == x: ee[-1] += 1
        else:ee.append(1)

    return ee

def main():
    n=II()
    ss=[1]
    for a in range(2,45):ss.append(ss[-1]+a)
    #print(ss)
    ee=pf(n)
    #print(ee)
    ans=0
    for e in ee:
        i=bisect_right(ss,e)
        ans+=i
    print(ans)

main()

### FIXED CODE ###

from bisect import bisect_right
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def pf(x):
    ee=[]
    pp=[]
    if x&1==0:
        k=(x&-x).bit_length()-1
        pp.append(2)
        ee.append(k)
        x>>=k
    d=3
    while d**2<=x:
        while x%d==0:
            x//=d
            if pp and pp[-1]==d:ee[-1]+=1
            else:
                pp.append(d)
                ee.append(1)
        d+=2

    if x>1:
        if pp and pp[-1] == x: ee[-1] += 1
        else:ee.append(1)

    return ee

def main():
    n=II()
    ss=[1]
    for a in range(2,45):ss.append(ss[-1]+a)
    #print(ss)
    ee=pf(n)
    #print(ee)
    ans=0
    for e in ee:
        i=bisect_right(ss,e)
        ans+=i
    print(ans)

main()
import fractions
n,m=map(int, input().split())
a=list(map(int, input().split()))
b=[]
ans=0
for i in range(n):
    b.append(int(a[i]/2))

def lcm(x,y):
    return (x*y)//fractions.gcd(x,y)

c=[lcm(b[0],b[1])]
for i in range(1,n):
    x=lcm(c[i-2],b[i])
    c.append(x)

d=int(m//c[len(c)-1])
for i in range(1, d+1):
    if i%2!=0:
        ans+=1
    else:
        continue
print(ans)

### FIXED CODE ###

import math
import fractions
n,m=map(int, input().split())
a=list(map(int, input().split()))
b=[]
s=math.floor(math.log2(max(a)))
buf=0
for i in range(n): #aは偶数なので、1/2した値の配列を作った
    b.append(int(a[i]//2))

for i in range(s+1): #2のi乗ですべての数が割れるかどうか
    for j in b:
        if j%(2**i)==0:
            buf+=1
        else:
            continue
    if buf==n:
        buf=0
        continue
    else:
        break

def lcm(x,y): #最小公倍数を求める関数の定義
    return (x*y)//fractions.gcd(x,y)

if buf!=0 and buf!=n: #偶奇が入り混じってるとき
    print(0)
elif n==1: #配列の要素が1つしかないとき
    d=int(m//b[0])
    print(int((d+1)//2))
else:
    c=[lcm(b[0],b[1])] #以下のサイクルで求めた最小公倍数を入れる配列
    for i in range(1,n):
        x=lcm(c[i-1],b[i])
        c.append(x)
        if x<m:
            continue
        else:
            break
    d=int(m//c[len(c)-1]) #最後の値(c[len(c)-1])が配列bの最小公倍数
    ans=int((d+1)//2)
    print(ans)