Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N = int(input())
l = [-1] * N

def get(v1, v2):
    print(v1)
    s = input()
    if s=="Male":
        l[v1] = 0
    elif s=="Female":
        l[v1] = 1
    else:
        print(v1)
        return -1

    print(v2)
    s = input()
    if s=="Male":
        l[v2] = 0
    elif s=="Female":
        l[v2] = 1
    else:
        print(v2)
        return -1
    
    return l[v2]==l[v1]


left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2
    v = get(left, mid)
    if v==-1:
        exit()
    elif (v==True and (mid-left)%2) or (v==False and (mid-left)%2==0):
        right = m
    else:
        left = m

### FIXED CODE ###

N = int(input())
l = [-1] * N

print(0)
s = input()
if s=="Male":
    l[0] = 0
elif s=="Female":
    l[0] = 1
else:
    exit(0)

print(N-1)
s = input()
if s=="Male":
    l[N-1] = 0
elif s=="Female":
    l[N-1] = 1
else:
    exit(0)

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        exit(0)

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        left, right = left, mid
    else:
        left, right = mid, right
### BUGGY CODE ###

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

for _ in range(K):
    B = [0]*N
    for i in range(N):
        l = max(0,i-A[i])
        r = min(N-1,i+A[i])
        B[l] += 1
        if N > r+1:
            B[r+1] -= 1
    for i in range(N-1):
        B[i+1] += B[i]

    A = B

    if all(B) == N:
        break

print(*A)

### FIXED CODE ###

import numpy as np

from numba import njit
@njit(cache=True)
def solve(N,K,A):
    for _ in range(K):
        B = np.zeros(N,dtype=np.int64)
        for i in range(N):
            l = max(0,i-A[i])
            r = min(N-1,i+A[i])
            B[l] += 1
            if N > r+1:
                B[r+1] -= 1
        
        A = np.cumsum(B)
        if np.all(A==N):
            break

    return A

def main():
    N,K = map(int,input().split())
    A = np.array(list(map(int,input().split())))

    A = solve(N,K,A)
    print(*A)

main()
### BUGGY CODE ###

n = int(input())
A = [input() for _ in range(n)]
AS = set(A)
ASd = set(A)
for i in ASd:
    if A.count(i) % 2 == 0:
        AS.remove(i)
print(len(AS))

### FIXED CODE ###

n = int(input())
A = [input() for _ in range(n)]
AS = set()
for i in A:
    if i not in AS:
        AS.add(i)
    else:
        AS.remove(i)
print(len(AS))
### BUGGY CODE ###

n=int(input())
ans=0
for i in range(n):
    ans+=i
print(ans)

### FIXED CODE ###

n=int(input())
ans=(n*(n-1))//2
print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
ss=set(s)
l=[0]
for j in range(n):
    for i in ss:
        if l[0]!=s:
            s=s.replace(i*2,i)
            l[0]==s
        else:
            break
print(len(s))


### FIXED CODE ###

n=int(input())
s=input()
ss=set(s)
l=s[0]
count=1
for j in range(n):
    if l!=s[j]:
        count+=1
        l=s[j]
print(count)
### BUGGY CODE ###

N = int(input())
ans=0
c=0
for a in range(1,1001):
    for b in range(1,1001):
        c=N-a*b
        if c>=1:
            ans+=1
ans1=0
for a in range(1,1001):
    for b in range(1001,1000001):
        c=N-a*b
        if c>=1:
            ans1+=1
print(ans+ans1*2)

### FIXED CODE ###

N = int(input())
ans=0
c=0
for a in range(1,1001):
    c=N-a*a
    if c>=1:
        ans+=1
ans1=0
for a in range(1,1000001):
    for b in range(a+1,int(N/a)+1):
        c=N-a*b
        if c>=1:
            ans1+=1
print(ans+ans1*2)
### BUGGY CODE ###

INF=10**30
from heapq import heapify,heappop,heappush
N=int(input())
a=list(map(int,input().split()))

right=list(map(lambda x:-x,a[2*N:]));heapify(right)
rmin=[INF]*(3*N);rmin[2*N]=sum(right)*-1

for i in reversed(range(N,2*N)):
    b=min(heappop(right)*-1,a[i])
    heappush(right,b*-1)
    rmin[i]=sum(right)*-1

left=a[:N];heapify(left)
lmax=[-INF]*(3*N);lmax[N-1]=sum(left)
for i in range(N,2*N):
    b=heappop(left)
    heappush(left,max(b,a[i]))
    lmax[i]=sum(left)
res=-INF
for i in range(N,2*N+1):
    res=max(res,lmax[i-1]-rmin[i])
print(res)

### FIXED CODE ###

INF=10**30
from heapq import heapify,heappop,heappush
N=int(input())
a=list(map(int,input().split()))

right=list(map(lambda x:-x,a[2*N:]));heapify(right)
rmin=[INF]*(3*N);rmin[2*N]=sum(right)*-1

for i in reversed(range(N,2*N)):
    p=heappop(right)*-1
    b=min(p,a[i])
    d=0 if b==p else b-p
    heappush(right,b*-1)
    rmin[i]=rmin[i+1]+d

left=a[:N];heapify(left)
lmax=[-INF]*(3*N);lmax[N-1]=sum(left)
for i in range(N,2*N):
    p=heappop(left)
    b=max(p,a[i])
    d=0 if b==p else b-p
    heappush(left,b)
    lmax[i]=lmax[i-1]+d
res=-INF
for i in range(N,2*N+1):
    res=max(res,lmax[i-1]-rmin[i])
print(res)
### BUGGY CODE ###

# -*- coding:utf-8 -*-

def solve():
    R, G, B, N = list(map(int, input().split()))

    ans = 0
    for r in range(0, N+1):
        num1 = r*R
        if num1 > N: break

        for g in range(0, N+1):
            num2 = g*G
            if num1+num2 > N: break

            for b in range(0, N+1):
                num3 = b*B
                if num1+num2+num3 > N: break
                if num1+num2+num3 == N:
                    ans += 1

    print(ans)

if __name__ == "__main__":
    solve()


### FIXED CODE ###

# -*- coding:utf-8 -*-

def solve():
    R, G, B, N = list(map(int, input().split()))

    # r, g, bのそれぞれに関してforで回すとO(N**3)で間に合わないので、
    # rを固定する。するとO(N**2)で解ける
    ans = 0
    for g in range(N+1):
        if g*G > N: break
        for b in range(N+1):
            if g*G+b*B > N: break
            if (N - (g*G+b*B))%R == 0:
                ans += 1
    print(ans)


if __name__ == "__main__":
    solve()
### BUGGY CODE ###

s=input()
t=input()
if len(set(t)-set(s))>0:
  print(-1)
  exit()

ss=s*2
ind=-1
ans=0
for c in t:
  nex=ss[ind+1:].find(c)
  ind=(ind+1)+nex
  if ind>=len(s):
    ind-=len(s)
    ans+=len(s)

print(ans+ind+1)


### FIXED CODE ###

s=input()
t=input()
if len(set(t)-set(s))>0:
  print(-1)
  exit()

ss=s*2
ind=-1
ans=0
for c in t:
  nex=ss[ind+1:].find(c)
  ind=(ind+1)+nex
  if ind>=len(s):
    ind-=len(s)
    ans+=len(s)

print(ans+ind+1)
### BUGGY CODE ###

import heapq
import math
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

"""
a = [1,7,3,5,4]

#heapify
#配列a = [1,7,3,5,4]をheapにする
heapq._heapify_max(a)
print(a) #[7, 5, 3, 1, 4]

#heappop
#最大値の取り出し
print(_heappop_max(a)) #7
print(a) #[5, 4, 3, 1]

#heappush
#要素(2)の挿入
_heappush_max(a,2)
print(a) #[5, 4, 3, 1, 2]

#最大値の取り出し
print(_heappop_max(a)) #5
"""

N, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = [a[i] for i in range(N)]
heapq._heapify_max(b)

okaiage = []
heapq._heapify_max(okaiage)
_heappush_max(okaiage, _heappop_max(b)/2)

m = M - 1
for j in range(N-1):
    temp_oka = _heappop_max(okaiage)
    temp_a = _heappop_max(b)
    if m > 0:
        if temp_a > temp_oka:
            _heappush_max(okaiage, temp_a/2)
            _heappush_max(okaiage, temp_oka)
        else:
            _heappush_max(okaiage, temp_a)
            _heappush_max(okaiage, temp_oka/2)
    else:
        _heappush_max(okaiage, temp_a)
        _heappush_max(okaiage, temp_oka)
    m -= 1
if m > 0:
    for i in range(m):
        temp_oka = _heappop_max(okaiage) / 2
        _heappush_max(okaiage, temp_oka)
okaiage_kiri = [int(math.floor(_heappop_max(okaiage))) for i in range(N)]
print(sum(okaiage_kiri))


### FIXED CODE ###

import heapq
import math
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

"""
a = [1,7,3,5,4]

#heapify
#配列a = [1,7,3,5,4]をheapにする
heapq._heapify_max(a)
print(a) #[7, 5, 3, 1, 4]

#heappop
#最大値の取り出し
print(_heappop_max(a)) #7
print(a) #[5, 4, 3, 1]

#heappush
#要素(2)の挿入
_heappush_max(a,2)
print(a) #[5, 4, 3, 1, 2]

#最大値の取り出し
print(_heappop_max(a)) #5
"""

N, M = map(int, input().split())
a = [int(i) for i in input().split()]
heapq._heapify_max(a)

for j in range(M):
    _heappush_max(a, _heappop_max(a)//2)
print(sum(a))
### BUGGY CODE ###

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

i = 1
ans = 1
R = int(P**(1/N)) + 1
if N > 1:
	for l in range(R):
		if P % (R-l)**N == 0:
			ans = R-l
			break
		i += 1
else:
	ans = P
print(ans)



### FIXED CODE ###

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

ans = 1
R = int(P**(1/N)) + 1
if N == 1:
	ans = P
elif N > 40:
	ans = 1
else:
	for l in range(R):
		if P % (R-l)**N == 0:
			ans = R-l
			break
print(ans)
### BUGGY CODE ###

N, X, M = map(int, input().split())
check = [0]*(M+1)
check[X] += 1
A = X
last_count = 0
while True:
    A = (A**2)%M
    if check[A] != 0:
        last_count = sum(check)
        target_value = A
        break
    check[A] += 1
A2 = X
first_count = 0
while True:
    first_count += 1
    A2 = (A2**2)%M
    if A2 == target_value:
        break

roop_count = last_count-first_count
A3 = target_value
mass = A3
for i in range(roop_count-1):
    A3 = (A3**2)%M
    mass += A3
if roop_count == 0:
    A = X
    ans = X
    for i in range(N-1):
        A = (A**2)%M
        ans += A
    print(ans)
    exit()

ans = X
A = X
for i in range(min(N,first_count)-1):
    A = (A**2)%M
    ans += A
if N > first_count:
    ans += ((N-first_count)//roop_count)*mass
    A4 = target_value
    if (N-first_count)%roop_count >= 1:
        ans += A4
    for i in range(((N-first_count)%roop_count)-1):
        A4 = (A4**2)%M
        ans += A4

print(ans)

### FIXED CODE ###

N, X, M = map(int, input().split())
if X <= 1:
    print(X*N)
    exit()
check = [0]*(M+1)
check[X] += 1
A = X
last_count = 0
while True:
    A = (A**2)%M
    if check[A] != 0:
        last_count = sum(check)
        target_value = A
        break
    check[A] += 1
A2 = X
first_count = 0
while A2 != target_value:
    first_count += 1
    A2 = (A2**2)%M

roop_count = last_count-first_count

A3 = target_value
mass = A3
for i in range(roop_count-1):
    A3 = (A3**2)%M
    mass += A3
if roop_count == 0:
    print(N*X)
    exit()
if first_count != 0:
    ans = X
    A = X
    for i in range(min(N,first_count)-1):
        A = (A**2)%M
        ans += A
else:
    ans = 0
if N > first_count:
    ans += ((N-first_count)//roop_count)*mass
    A4 = target_value
    if (N-first_count)%roop_count >= 1:
        ans += A4
    for i in range(((N-first_count)%roop_count)-1):
        A4 = (A4**2)%M
        ans += A4
print(ans)
### BUGGY CODE ###

from operator import itemgetter

N = int(input())
X=[]
ans=0
for i in range(N):
    H = list(map(int, input().split()))
    O=[]
    O.append(H[0]-H[1])
    O.append(H[0]+H[1])
    X.append(O)
#print(X)
X=sorted(X, key=itemgetter(1))
while(len(X)>0):
    #print(X)
    ans+=1
    S=X[0][1]
    X.remove(X[0])
    I = []
    for i in range(len(X)):
        if(X[i][0]>=S):
            I.append(X[i])
    X=I
    #print(I)



print(ans)


### FIXED CODE ###

from operator import itemgetter

N = int(input())
X=[]
ans=0
for i in range(N):
    H = list(map(int, input().split()))
    O=[]
    O.append(H[0]-H[1])
    O.append(H[0]+H[1])
    X.append(O)
#print(X)
X=sorted(X, key=itemgetter(1))
S=X[0][1]
ans+=1
for i in range(len(X)):
    if(X[i][0]>=S):
        ans+=1
        S=X[i][1]
"""
while(len(X)>0):
    #print(X)
    ans+=1
    S=X[0][1]
    X.remove(X[0])
    I = []
    for i in range(len(X)):
        if(X[i][0]>=S):
            I.append(X[i])
    X=I
    #print(I)
"""


print(ans)
### BUGGY CODE ###

N = int(input())
*A, = map(int, input().split())
A = sorted(A)
checked = [True] * N
ans = 0
for i, a in enumerate(A):
    if not checked[i]: continue
    flag = True
    for j in range(i+1, N):
        if A[j] % a == 0:
            checked[j] = False
            if A[j] == a: flag = False
    if flag: ans += 1 
print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
*A, = map(int, input().split())
A = sorted(A)
max_A = A[-1]
cnt = Counter(A)
admissible = [True] * (max_A + 1)
checked = [False] * (max_A + 1)
ans = 0
for a in A:
    if not admissible[a] or checked[a]: continue
    ans += 1
    i = 2
    while a * i <= max_A:
        admissible[a * i] = False
        i += 1
    checked[a] = True
    if cnt[a] > 1: ans -= 1
print(ans)
### BUGGY CODE ###

N = int(input())
print(0, flush=True)
s0 = input()
if s0 == 'Vacant':
    exit()
l = 0
r = N-1

while r - l > 1:
    m = (l+r) // 2  # 中央値のクエリを送る
    print(m, flush=True)
    s = input()
    if s == 'Vacant':
        exit()
    if m & 2 == 1:  # r-lが奇数であることと同義
        if s != s0:  # 異性ならば
            l = m  # 前半部分に空席はないから下限をあげる
        else:  # 同性ならば
            r = m  # 前半部分に空席があるので上限を下げる
    else:  # r-lが偶数であることと同義
        if s != s0:  # 異性ならば
            r = m  #
        else:  # 同性ならば
            l = m
print(r, flush=True)
sr = input()


### FIXED CODE ###

# 円状に席が並んでいるので、空席を作ると男女の並びが不自然になるのは確か
# 男 空席 男 とやると一見空席が見つけられないような気がするが、それは円のどこかで同性同士が隣り合ってしまうので無理
# 空席の隣は必ず男と女である

N = int(input())
# Vacantがあるとそこで並びがずれる

# 0を基準とする
print(0, flush=True)  # 0番目の座席に対してリクエストを送る
s0 = input()
if s0 == "Vacant":
    exit()

l = 0  # ずれていない(ずれているかも)
r = N-1  # ずれている
while r - l > 1:
    m = (l+r) // 2  # 中央値のリクエストを送る
    print(m, flush=False)
    s = input()
    if s == 'Vacant':
        exit()
    if m % 2 == 1:
        if s != s0:
            l = m
        else:
            r = m
    else:
        if s != s0:
            r = m
        else:
            l = m
print(r, flush=True)
sr = input()
### BUGGY CODE ###

n,m=map(int,input().split())
inf=[]
pre=[[] for _ in range(n)]
for _ in range(m):
    p,y=map(int,input().split())
    inf.append([p,y])
    pre[p-1].append(y)
for p in range(n): pre[p].sort()
for i in inf: print("{:06}{:06}".format(i[0],1+pre[i[0]-1].index(i[1])))

### FIXED CODE ###

n,m=map(int,input().split())
pre=[[] for _ in range(n)]
for _ in range(m):
    p,y=map(int,input().split())
    pre[p-1].append([y,_,p])
for p in range(n):
    pre[p].sort(key=lambda x:x[0])
    for i in range(len(pre[p])):
        pre[p][i].append(i)
lis=[]
for i in pre:
    for j in i:
        lis.append(j)
lis.sort(key=lambda x:x[1])
for i in lis: print("{:06}{:06}".format(i[2],i[3]+1))
### BUGGY CODE ###

N,W=map(int,input().split())
w=[]
v=[]
for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
V=sum(v)

dp=[[float("inf") for i in range(V+1)] for _ in range(110)]
dp[0][0]=0

for i in range(0,N):
    for j in range(V+1):
        if j-v[i]>=0:
            dp[i+1][j]=min(dp[i+1][j],dp[i][j-v[i]]+w[i])

        dp[i+1][j]=min(dp[i+1][j],dp[i][j])


ans=0

for j in range(V+1):
    if dp[N][j]<=W:
        ans=j

print(ans)


### FIXED CODE ###

N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
    w[i],v[i]=map(int,input().split())
V=sum(v)

dp=[[float("inf") ]*(V+1) for _ in range(110)]
dp[0][0]=0

for i in range(0,N):
    for j in range(V+1):
        if j-v[i]>=0:
            dp[i+1][j]=min(dp[i+1][j],dp[i][j-v[i]]+w[i])
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
ans=0
for j in range(V+1):
    if dp[N][j]<=W:
        ans=j
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
A=[]
B=[]
money=0
maxa=0
maxb=0
for i in range(N):
  x,y=map(int,input().split())
  if maxa<x:
    maxa=x
    maxb=i
  A.append(x)
  B.append(y)
for i in range(N):
  lowest=maxb
  low=maxa
  for j in range(N):
    if (low>A[j] and A[j]!=0):
      lowest=j
      low=A[j]
  if B[lowest]>M:
    money+=M*A[lowest]
    M-=B[lowest]
    break
  else:
    money+=B[lowest]*A[lowest]
    M-=B[lowest]
  A[lowest]=0
print(money)

### FIXED CODE ###

n,m=map(int,input().split());d,ans=[],0
for i in range(n):d.append(list(map(int,input().split())))
d.sort()
for i in range(n):
  if d[i][1]<=m:
    ans+=d[i][0]*d[i][1]
    m-=d[i][1]
  else:
    ans+=d[i][0]*m
    m=0
  if m<=0:break
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
from bisect import bisect_left

d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

N = d_in()
A_list = ds_in()
A_list.sort()

ans = 0
while len(A_list) > 1:
    max_a = A_list.pop()
    binary = bin(max_a)
    cand = 2 ** len(binary[2:]) - max_a
    if cand == 0:
        if max_a == A_list[-1]:
            A_list.pop()
            ans += 1
    else:
        idx = bisect_left(A_list, cand)
        if idx < len(A_list) and cand == A_list[idx]:
            A_list.pop(idx)
            ans += 1

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
from collections import Counter

d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

N = d_in()
A_list = np.array(ds_in())
A_list.sort()
EPSILON = 10**(-6)

cand_A = 2 ** (np.log2(A_list + EPSILON).astype(int) + 1) - A_list
idx = np.searchsorted(A_list, cand_A)
A_count = dict(Counter(A_list))

ans = 0
for i in range(N-1, -1, -1):
    if A_count[A_list[i]] <= 0:
        continue
    A_count[A_list[i]] -= 1
    if (A_list[idx[i]] == cand_A[i]) and (A_count[cand_A[i]] > 0):
        ans += 1
        A_count[cand_A[i]] -= 1

print(ans)
### BUGGY CODE ###

h,n,*t = map(int,open(0).read().split())

dp = [0] + [10**8]* h

for a,b in  zip(*[iter(t)]*2):
    for life_point in range(h +1):
        
        original_life = max(0,life_point - a)
#         print(original_life)
        magic_consum = dp[original_life]+ b
#         print(magic_consum)
        dp[life_point] = min(dp[life_point],magic_consum)
#         print(dp)
print(dp[h])

### FIXED CODE ###

h,n,*t = map(int,open(0).read().split())

dp = [0] + [10**8]* h

for a,b in  zip(*[iter(t)]*2):
    for life_point in range(h +1):
        
        original_life = max(0,life_point - a)
#         print(original_life)
        magic_consum = dp[original_life]+ b
#         print(magic_consum)
        dp[life_point] = min(dp[life_point],magic_consum)
#         print(dp)
print(dp[h])
### BUGGY CODE ###

from collections import deque
import sys
def input():
  return sys.stdin.readline()[:-1]

H, W=map(int, input().split())
S=['#'*(W+2)]+['#'+input()+'#' for i in range(H)]+['#'*(W+2)]

def f(data):
  m[data[0]][data[1]]=data[2]
  if m[data[0]-1][data[1]]<0 and S[data[0]-1][data[1]]=='.':
    q.append([data[0]-1, data[1], data[2]+1])
  if m[data[0]+1][data[1]]<0 and S[data[0]+1][data[1]]=='.':
    q.append([data[0]+1, data[1], data[2]+1])
  if m[data[0]][data[1]-1]<0 and S[data[0]][data[1]-1]=='.':
    q.append([data[0], data[1]-1, data[2]+1])
  if m[data[0]][data[1]+1]<0 and S[data[0]][data[1]+1]=='.':
    q.append([data[0], data[1]+1, data[2]+1])

out=0
for x in range(1, H+1):
  for y in range(1, W+1):
    if S[x][y]=='#':
      continue
    q=deque()
    q.append([x, y, 0])
    m=[[-1]*(W+2) for i in range(H+2)]
    while len(q)>0:
      data=q.popleft()
      f(data)
      if data[2]>out:
        out=data[2]
      
print(out)

### FIXED CODE ###

from collections import deque
import sys
def input():
  return sys.stdin.readline()[:-1]

H, W=map(int, input().split())
S=['#'*(W+2)]+['#'+input()+'#' for i in range(H)]+['#'*(W+2)]

def f(data):
  m[data[0]][data[1]]=data[2]
  if m[data[0]-1][data[1]]==-2 and S[data[0]-1][data[1]]=='.':
    m[data[0]-1][data[1]]=-1
    q.append([data[0]-1, data[1], data[2]+1])
  if m[data[0]+1][data[1]]==-2 and S[data[0]+1][data[1]]=='.':
    m[data[0]+1][data[1]]=-1
    q.append([data[0]+1, data[1], data[2]+1])
  if m[data[0]][data[1]-1]==-2 and S[data[0]][data[1]-1]=='.':
    m[data[0]][data[1]-1]=-1
    q.append([data[0], data[1]-1, data[2]+1])
  if m[data[0]][data[1]+1]==-2 and S[data[0]][data[1]+1]=='.':
    m[data[0]][data[1]+1]=-1
    q.append([data[0], data[1]+1, data[2]+1])

out=0
for x in range(1, H+1):
  for y in range(1, W+1):
    if S[x][y]=='#':
      continue
    q=deque()
    q.append([x, y, 0])
    m=[[-2]*(W+2) for i in range(H+2)]
    while len(q)>0:
      data=q.popleft()
      f(data)
      if data[2]>out:
        out=data[2]
      
print(out)
### BUGGY CODE ###

# 二回訪れたら終了、それまでに2に行ったらOK
# インデックスと値を入れ替えながらやってみる
n = int(input())
dic = []
for i in range(n):
    dic.append(int(input()))

used = []
tmp = 1
ans = 0
while True:
    target = dic[tmp - 1]
    if target == 2:
        print(ans + 1)  # 次の一手で決まるので
        exit()
    if target in used:
        print(-1)
        exit()
    tmp = target
    used.append(tmp)
    ans += 1


### FIXED CODE ###

# 二回訪れたら終了、それまでに2に行ったらOK
# インデックスと値を入れ替えながらやってみる
n = int(input())
dic = []
for i in range(n):
    dic.append(int(input()))

used = [False for _ in range(10 ** 5 + 1)]
tmp = 1
ans = 0
while True:
    target = dic[tmp - 1]
    if target == 2:
        print(ans + 1)  # 次の一手で決まるので
        exit()
    if used[target]:
        print(-1)
        exit()
    tmp = target
    used[tmp] = True
    ans += 1
### BUGGY CODE ###

n = int(input())

a = list(int(i) for i in input().split())
b = []
for i in range(0,len(a)):
    b.append(a[i])


def solve(cnt,A,N):
    for i in range(1, N):
        if sum(A[0:i])>0:
            if sum(A[0:i+1])>=0:
                r = A[i]
                A[i]=-sum(A[0:i])-1
                cnt+=abs(r-A[i])
        else:
            if sum(A[0:i+1])<=0:
                r = A[i]
                A[i]=-sum(A[0:i])+1
                cnt+=abs(r-A[i])
    return cnt

cnt1=0
if b[0]<=0:
    while b[0]<=0:
        b[0]+=1
        cnt1+=1

ans1=solve(cnt1,b,n)
cnt2=0
if a[0]>=0:
    while a[0]>=0:
        a[0]-=1
        cnt2+=1

ans2=solve(cnt2,a,n)
print(min(ans1,ans2))


### FIXED CODE ###

n = int(input())

a = list(map(int,input().split()))
b = [i for i in a]


def solve(cnt,A,N):
    sumA=A[0]
    for i in range(1, N):
        if sumA>0:
            if sumA+A[i]>=0:
                r = A[i]
                A[i]=-sumA-1
                cnt+=abs(r-A[i])
        else:
            if sumA+A[i]<=0:
                r = A[i]
                A[i]=-sumA+1
                cnt+=abs(r-A[i])

        sumA+=A[i]
    return cnt

cnt1=0
if b[0]<=0:
    ini=b[0]
    b[0]=1
    cnt1=abs(1-ini)


ans1=solve(cnt1,b,n)
cnt2=0
if a[0]>=0:
    ini=a[0]
    a[0]=-1
    cnt2=abs(-1-ini)


ans2=solve(cnt2,a,n)

print(min(ans1,ans2))
### BUGGY CODE ###

import math
import time
from collections import deque
from collections import defaultdict
from copy import deepcopy

mod = 10 ** 9 + 7
t = time.time()


def inv(n, mod):
    return power(n, mod-2)

def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, n):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    return ret


def main():
    A, B = iip()

    a = set(soinsuu_bunkai(A))
    b = set(soinsuu_bunkai(B))

    ans = 1 # 1の場合
    for aa in a:
        if aa in b:
            ans+=1

    print(ans)

main()

### FIXED CODE ###

import math
import time
from collections import deque
from collections import defaultdict
from copy import deepcopy

mod = 10 ** 9 + 7
t = time.time()



def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def main():
    A, B = iip()

    a = set(soinsuu_bunkai(A))
    b = set(soinsuu_bunkai(B))

    ans = 1 # 1の場合
    for aa in a:
        if aa in b:
            ans+=1

    print(ans)

main()