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

N, Y = map(int, input().split())
ax = ay = az = -1
if N > 2000 or (Y < 1000 and Y > 20000000):
	print("-1 -1 -1")
elif 10000*N == Y:
	ay = az = 0
	print(str(N)+" "+str(ay)+" "+str(az))
else:	
	for x in range(N+1):
		for y in range(N+1):
			for z in range(N+1):
				if x+y+z > N or N > x+y+z:
					continue
				total = 10000*x + 5000*y + 1000*z
				if total == Y and x+y+z == N:
					ax = x
					ay = y
					az = z
					break
			else:
				continue
			break
		else:
			continue
		break
	print(str(ax)+" "+str(ay)+" "+str(az))

### FIXED CODE ###

N, Y = map(int, input().split())
ax = ay = az = -1
for x in range(N+1):
	for y in range(N+1):
		if (N-x-y) < 0:
			continue
		total = 10000*x + 5000*y + 1000*(N-x-y)
		if total == Y:
			ax = x
			ay = y
			az = N-x-y
			break
	else:
		continue
	break
print(str(ax)+" "+str(ay)+" "+str(az))
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
use = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[0] * 10 for i in range(n+1)]

def makenum(x,y):
    res = 0
    for i in range(y):
        res = res* 10 + x
    return res
    
for i in range(1,n+1):
    kouho = []
    for j in a:
        if i - use[j] >= 0:
            if dp[i-use[j]] == [0] * 10 and i - use[j] != 0: # マッチの数が合わない場合
                continue #何もしない
            else:
                copy = dp[i-use[j]][:]
                copy[j] += 1
                kouho.append(copy)
    if kouho == []: #空の場合
        continue #何もしない
    else:
        usearray = []
        usenum = 0
        for array in kouho:
            tmpnum = 0
            for k in range(9,0,-1):
                tmpnum = tmpnum * (10**array[k]) + makenum(k,array[k])
            if tmpnum > usenum:
                usearray = array
                usenum = tmpnum
        dp[i] = usearray
ans = ""
for i in range(9,0,-1):
    ans += (str(i) * dp[n][i])
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
use = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[0] * 10 for i in range(n+1)]
for i in range(1,n+1):
    for j in a:
        if i - use[j] >= 0:
            if dp[i-use[j]] == [0] * 10 and i - use[j] != 0: # マッチの数が合わない場合
                continue #何もしない
            else:
                if sum(dp[i-use[j]])+1 >= sum(dp[i]):
                    copy = dp[i-use[j]][:]
                    copy[j] += 1
                    dp[i] = copy
ans = ""
for i in range(9,0,-1):
    ans += (str(i) * dp[n][i])
print(ans)
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
A=1
ANS=0
while A!=0:
  A = 0
  for i in range(N):
    if L[i] % 2 == 0 and A == 0:
      L[i] = L[i] // 2
      A = 1
      break
  if A != 0:
  	ANS += 1
print(ANS)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
A=1
ANS=IND=0
while A!=0:
  A = 0
  for i in range(IND, N):
    if L[i] % 2 == 0 and A == 0:
      L[i] = L[i] // 2
      A = 1
      break
    else:
      IND += 1
  if A != 0:
  	ANS += 1
print(ANS)
### BUGGY CODE ###

S=input()
Q=int(input())
case=0
for i in range(Q):
    temp=input().split()
    if len(temp)==1:
        case=1-case	
    else:
        if int(temp[1])==1:
            if case==0:
                S=temp[2]+S
            else:
                S=S+temp[2]

        else:
            if case==1:
                S=temp[2]+S
            else:
                S=S+temp[2]
if case==1:
    S=S[::-1]

print(S)



### FIXED CODE ###

S = input()
Q = int(input())
flip = 0
head = []
tail = []
for i in range(Q):
  Query = input().split()
  if len(Query) == 3:
    T,F,C = Query
    F = int(F)-1
    if F^flip == 1:
      tail.append(C)
    else:
      head.append(C)
  else:
    flip ^= 1
if flip:
  head, tail = tail, head
  S = S[::-1]
head = ''.join(head[::-1])
tail = ''.join(tail)
print(head+S+tail)
### BUGGY CODE ###

N, K = map(int, input().split())
h = sorted([int(input()) for i in range(N)])
res = []
for i in range(N-K+1):
    tmp = h[i:i+K]
    res.append(tmp[-1] - tmp[0])
print(min(res))

### FIXED CODE ###

N, K = map(int, input().split())
h = sorted([int(input()) for i in range(N)])
res = []
for i in range(N-K+1):
    res.append(h[i+K-1] - h[i])
print(min(res))
### BUGGY CODE ###

def solve(string):
    s, q, *qs = string.split("\n")
    for _q in qs:
        if _q == "1":
            s = s[::-1]
            continue
        _, f, c = _q.split()
        s = c + s if f == "1" else s + c
    return s


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


### FIXED CODE ###

def solve(string):
    s, q, *qs = string.split("\n")
    pre = []
    post = []
    r = False
    for _q in qs[::-1]:
        if _q == "1":
            r = not r
            continue
        _, f, c = _q.split()
        if r and f == "2" or not r and f == "1":
            pre.append(c)
        else:
            post.append(c)
    pre, post = "".join(pre), "".join(post[::-1])
    return pre + s[::-1] + post if r else pre + s + post


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))
### BUGGY CODE ###

n= int(input())
l = []
for _ in range(n):
    l.append(''.join(sorted(input())))

cnt = 0
for e in l:
    ll = l[1:]
    for ee in ll:
        if e == ee:
            cnt += 1
    l = ll

print(cnt)

### FIXED CODE ###

n= int(input())
l = []
for _ in range(n):
    l.append(''.join(sorted(input())))

d = dict()
cnt = 0
for e in l:
    if e in d:
        d[e] += 1
        cnt += d[e]
    else:
        d[e] = 0

print(cnt)
### BUGGY CODE ###

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

count = 0
for i in range(N):
  count_ = 0
  judge = i+1
  for j in range(judge,N):
    if count >= N - i:
      break;
    if H[i] >= H[j]:
      count_ += 1
    else:
      break;
    H[i] = H[j]
  if count_ > count:
    count = count_
  if count == N-1:
    break;

print(count)

### FIXED CODE ###

N = int(input())
H = [int(e) for e in input().split()]
count_max = 0
i = 0
while i < N:
  judge = True
  count = 0
  tmp = i
  for j in range(tmp,N):
    if j < N-1:
      if H[j] >= H[j+1]:
        count += 1
      else:
        break;

  #print(count)
  if count_max < count:
    count_max = count
  if judge == True:
    i += count + 1

print(count_max)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    s=input()
    q=int(input())
    inv=False
    for i in range(q):
        que=input()
        if que[0]=="1":
            inv=not(inv)
        else:
            f=int(que[2])
            if (f==1 and not(inv)) or (f==2 and inv):
                s=que[4]+s
            else:
                s+=que[4]
    if inv:
        print(s[::-1])
    else:
        print(s)



if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    s=input()
    q=int(input())
    s=deque(s)
    inv=False
    for i in range(q):
        que=input()
        if que[0]=='1':
            inv=not(inv)
        else:
            f=que[2]
            if (f=='1' and not(inv)) or (f=='2' and inv):
                s.appendleft(que[4])
            else:
                s.append(que[4])
    if inv:s.reverse()
    print(*s,sep='')

if __name__=='__main__':
    main()
### BUGGY CODE ###

### 解答
def popcount(X):
  pc = 0
  while X>0:
    pc += X%2
    X = X//2
  return pc

N = int(input())
B = input()
X = int(B, 2)

pcx = popcount(X)
pc0to1 = pcx + 1
pc1to0 = pcx - 1
if pc0to1 > 0:
  r0to1 = X%pc0to1
if pc1to0 > 0:
  r1to0 = X%pc1to0

for i in range(N):
  b = B[i]
  if b == "0":
    pc = pc0to1
  else:
    pc = pc1to0
  if pc == 0:
    print(0)
    continue

  if b == "0":
    x = r0to1 + 2**(N-i-1)%pc
  else:
    x = r1to0 - 2**(N-i-1)%pc
  x = x%pc

  ans = 1
  while x > 0:
    pc = popcount(x)
    x = x%pc
    ans += 1
  print(ans)

    
  

  




### FIXED CODE ###

### 解答
def popcount(X):
  pc = 0
  while X>0:
    pc += X%2
    X = X//2
  return pc

N = int(input())
B = input()
X = int(B, 2)

pcx = popcount(X)
pc0to1 = pcx + 1
pc1to0 = pcx - 1
if pc0to1 > 0:
  r0to1 = X%pc0to1
  r20to1 = [1]
  for i in range(1,N):
    r20to1.append((r20to1[-1]*2)%pc0to1)
if pc1to0 > 0:
  r1to0 = X%pc1to0
  r21to0 = [1]
  for i in range(1,N):
    r21to0.append((r21to0[-1]*2)%pc1to0)

for i in range(N):
  b = B[i]
  if b == "0":
    pc = pc0to1
  else:
    pc = pc1to0
  if pc == 0:
    print(0)
    continue

  if b == "0":
    x = r0to1 + r20to1[-(i+1)]
  else:
    x = r1to0 - r21to0[-(i+1)]
  x = x%pc

  ans = 1
  while x > 0:
    pc = popcount(x)
    x = x%pc
    ans += 1
  print(ans)
### BUGGY CODE ###

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

ans = 0
for i in A:
    if ans != 0:
        ans = ans * i
    else:
        ans = i

if ans > 1000000000000000000:
    print("-1")
else:
    print(ans)


### FIXED CODE ###

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

A.sort()
ans = 0

if A[0] == 0:
    print(ans)
    exit()

for i in A:
    if ans != 0:
        ans = ans * i
    else:
        ans = i
    if ans > 1000000000000000000:
        print("-1")
        exit()

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

n, m = [int(x) for x in input().split()]
l, r = [int(x) for x in input().split()]
s1 = {int(x) for x in range(l, r+1)}
for i in range(m-1):
    l, r = [int(x) for x in input().split()]
    s2 = {int(x) for x in range(l, r+1)}
    s1 = s1 & s2
    
print(len(s1))

### FIXED CODE ###

n, m = [int(x) for x in input().split()]
l = [0] * m
r = [0] * m
for i in range(m):
    l[i], r[i] = map(int, input().split())

L = max(l)
R = min(r)

if L <= R:
    print(R - L + 1)
else:
    print(0)
### BUGGY CODE ###

#ABC129D-Lamp.py

#import list
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(10000)

#constant
H, W = list(map(int,input().split()))
S = [input() for _ in range(H)]

#variable

#function
@lru_cache(maxsize=None)
def L(i,j):
    if S[i-1][j-1] == "#":
        return 0
    elif S[i-1][j-1] == ".":
        if j == 1:
            return 1
        else:
            return L(i,j-1) + 1

@lru_cache(maxsize=None)
def R(i,j):
    if S[i-1][j-1] == "#":
        return 0
    elif S[i-1][j-1] == ".":
        if j == W:
            return 1
        else:
            return R(i,j+1) + 1

@lru_cache(maxsize=None)
def U(i,j):
    if S[i-1][j-1] == "#":
        return 0
    elif S[i-1][j-1] == ".":
        if i == 1:
            return 1
        else:
            return U(i-1,j) + 1

@lru_cache(maxsize=None)
def D(i,j):
    if S[i-1][j-1] == "#":
        return 0
    elif S[i-1][j-1] == ".":
        if i == H:
            return 1
        else:
            return D(i+1,j) + 1

#class

#main function
def main():
    for i in range(1,H+1):
        for j in range(1,W+1):
            left = L(i,j)
            right = R(i,j)
            up = U(i,j)
            down = D(i,j)
    maxScore = 0
    for i in range(1,H+1):
        for j in range(1,W+1):
            score = L(i,j)+R(i,j)+U(i,j)+D(i,j)-3
            if score > maxScore:
                maxScore = score
    print(maxScore)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#ABC129D-Lamp.py

#import list
import sys
import numpy as np

#main function
def main():
    buffer = sys.stdin.buffer
    H, W = list(map(int,buffer.readline().split()))
    S = np.frombuffer(buffer.read(H*(W+1)), dtype="B") == ord(".")
    S = S.reshape((H,W+1))[:,:-1]
    L = np.empty((H,W), dtype="i4")
    R = np.empty((H,W), dtype="i4")
    U = np.empty((H,W), dtype="i4")
    D = np.empty((H,W), dtype="i4")

    L[:,0] = S[:,0]
    for i in range(1,W):
        L[:,i] = (L[:,i-1] + 1) * S[:,i]

    R[:,-1] = S[:,-1]
    for i in range(1,W):
        R[:,-1-i] = (R[:,-i] + 1) * S[:,-1-i]

    U[0] = S[0]
    for i in range(1,H):
        U[i] = (U[i-1] + 1) * S[i]

    D[-1] = S[-1]
    for i in range(1,H):
        D[-1-i] = (D[-i] + 1) * S[-1-i]

    score = L + R + U + D - 3
    print(int(score.max()))


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

import collections

h, w, n = map(int, input().split())
pos = collections.defaultdict(lambda: collections.defaultdict(bool))
squares = set()
for index in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    pos[a][b] = True
    for i in range(-2, 1):
        for j in range(-2, 1):
            y = a + i
            x = b + j
            if 0 <= x < w - 2 and 0 <= y < h - 2:
                squares.add((y, x))
counter = collections.Counter()
for y, x in squares:
    count = 0
    for i in range(3):
        for j in range(3):
            if pos[y + i][x + j]:
                count += 1
    counter[count] += 1
print((h - 2) * (w - 2) - sum(counter.values()))
for i in range(1, 10):
    print(counter[i])

### FIXED CODE ###

import collections

h, w, n = map(int, input().split())
squares = collections.defaultdict(lambda: collections.defaultdict(int))
for index in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    for i in range(-2, 1):
        for j in range(-2, 1):
            y = a + i
            x = b + j
            if 0 <= x < w - 2 and 0 <= y < h - 2:
                squares[y][x] += 1
counter = collections.Counter()
for y, xs in squares.items():
    for x, count in xs.items():
        counter[count] += 1
print((h - 2) * (w - 2) - sum(counter.values()))
for i in range(1, 10):
    print(counter[i])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from functools import reduce


def gcd(a, b):
    if a > b:
        return gcd(b, a)
    if a == 0:
        return b
    return gcd(b % a, a)

def gcd_group(A):
    return reduce(gcd, A)


def solve(N: int, A: "List[int]"):
    ret = 0
    for i in range(N):
        temp = gcd_group(A[:i] + A[i+1:])
        if temp > ret:
            ret = temp
    print(ret)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from functools import reduce


def gcd(a, b):
    if a > b:
        return gcd(b, a)
    if a == 0:
        return b
    return gcd(b % a, a)

def gcd_group(A):
    return reduce(gcd, A)


def solve(N: int, A: "List[int]"):
    left = [A[0]] # A[0]からA[i]までのGCD
    right = [A[N-1]] # A[i]からA[N-1]までのGCD
    for i in range(1, N):
        left.append(gcd(left[-1], A[i]))
        right.append(gcd(right[-1], A[-i-1]))
    right.reverse()

    ret = 0
    for i in range(N):
        if i == 0:
            temp = right[1]
        elif i == N-1:
            temp = left[N-2]
        else:
            temp = gcd(left[i-1], right[i+1])

        if temp > ret:
            ret = temp
    print(ret)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    n, m = map(int, input().split())
    uf = UnionFind(n)

    for _ in range(m):
        a, b = map(int, input().split())
        uf.union(a-1, b-1)
    
    print(len(max(uf.all_group_members().values(), key=lambda x: len(x))))


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque


def main():
    n, m = map(int, input().split())
    is_checked = [False for _ in range(n+1)]
    edges = [[] for _ in range(n+1)]
    ans = 0

    for _ in range(m):
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)

    for ni in range(n):
        if is_checked[ni]:
            continue
        is_checked[ni] = True
        q = deque([ni])
        depth = 0
        while len(q) > 0:
            p = q.popleft()
            for e in edges[p]:
                if not is_checked[e]:
                    is_checked[e] = True
                    q.append(e)
            depth += 1

        ans = max(ans, depth)

    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    N, M = map(int, input().split())
    ans = 1
    if M > 0:
        a, b = map(int, input().split())
        groups = []
        groups.append({a, b})
        for _ in range(1, M):
            a, b = map(int, input().split())
            flag = True
            for g in groups:
                if a in g:
                    g.add(b)
                    flag = False
                if b in g:
                    g.add(a)
                    flag = False
            if flag:
                groups.append({a, b})

        for g in groups:
            ans = max(ans, len(g))

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1] * (n + 1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0] * (n + 1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード

    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def main():
    N, M = map(int, input().split())
    UF = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        UF.Unite(a, b)
    ans = 0
    for i in range(N):
        ans = max(ans, UF.Count(i + 1))
    print(ans)


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

N = int(input())
As = list(map(int, input().split()))
d = dict()
for i in range(N):
    for j in range(N-i):
        span = (j,j+i+1)
        if i == 0:
            d[span] = As[j]
        else:
            d[span] = max(As[j]-d[(j+1,j+i+1)], As[j+i]-d[(j,j+i)])
print(d[span])


### FIXED CODE ###

N = int(input())
As = list(map(int, input().split()))
d = [0]*(N**2)
for i in range(N):
    for j in range(N-i):
        span = i*N+j
        if i == 0:
            d[span] = As[j]
        else:
            d[span] = max(As[j]-d[span-N+1], As[j+i]-d[span-N])
print(d[span])
### BUGGY CODE ###

k,s = map(int,input().split())
print(sum([1 for a in range(k+1) for b in range(k+1) for c in range(k+1) if a+b+c == s]))

### FIXED CODE ###

k,s = map(int,input().split())
print(sum([1 for a in range(k+1) for b in range(k+1) if 0 <= s-a-b <= k]))
### BUGGY CODE ###

N = input()
number = input()

a = number.split()
n_list=[]
count=0



for num in a:
    num = int(num)
    if num % 2 == 0:
        n_list.append(num)

if n_list != []:
    maxnum = max(n_list)
    for num2 in n_list:
        for i in range(maxnum):
            if num2 % 2**(i+1) == 0:
                count+=1


print(count)

### FIXED CODE ###

from math import log2

N = input()
number = input()

a = number.split()
n_list=[]
count=0



for num in a:
    num = int(num)
    if num % 2 == 0:
        n_list.append(num)


if n_list != []:
    maxnum = max(n_list)
    maxnum = log2(maxnum)
    maxnum = int(maxnum)
    for num2 in n_list:
        for i in range(maxnum):
            if num2 % 2**(i+1) == 0:
                count+=1


print(count)
### BUGGY CODE ###

def yakusu(n):
    max_yakusu = int(n**0.5)
    arr = [1]
    tmp = 2

    while n > 1:
        for i in range(tmp,min(n+1,max_yakusu+1)):
            if n % i == 0:
                arr.append(i)
                while n % i == 0:
                    n = int(n/i)
                    tmp = i + 1
                break
    return arr

def gcd(x,y):
    if y == 0:
       return x
    else:
       return gcd(y, x % y)

A,B = [int(x) for x in input().split()]
koyaku = gcd(A,B)

koyaku_insu = yakusu(koyaku)


print(len(koyaku_insu))

### FIXED CODE ###

def prime_factorize(n):
    a = [1]
    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
  
def gcd(x,y):
    if y == 0:
       return x
    else:
       return gcd(y, x % y)
 
A,B = [int(x) for x in input().split()]
koyaku = gcd(A,B)
 
koyaku_insu = list(set(prime_factorize(koyaku)))
 
 
print(len(koyaku_insu))