Harryxun/stf_run huggingface dataset:
from collections import deque
import sys

readline = sys.stdin.readline

H, W = map(int, readline().split())
a = tuple(readline() for _ in range(H))


def adjacent_vertices(v):
    r, c = divmod(v, H)

    if r > 0:
        yield v - H
    if r < H - 1:
        yield v + H
    if c > 0:
        yield v - 1
    if c < W - 1:
        yield v + 1


gen = (r * H + c for r in range(H) for c in range(W) if a[r][c] == '#')

# BFSで黒から最遠点までの距離を求める
dist = [-1] * (H * W)
q = deque()
for v in gen:
    dist[v] = 0
    q.append(v)
while q:
    v = q.popleft()
    d = dist[v]
    for nv in filter(lambda x: dist[x] == -1, adjacent_vertices(v)):
        dist[nv] = d + 1
        q.append(nv)

print(d)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
a = [input() for _ in range(H)]

dist = [[-1] * W for _ in range(H)]
dq = deque()

for r in range(H):
    for c in range(W):
        if a[r][c] == '#':
            dist[r][c] = 0
            dq.append((r, c))


def in_range(r, c):
    return 0 <= r < H and 0 <= c < W


dr_s = (0, 0, -1, 1)
dc_s = (-1, 1, 0, 0)

d = 0
while dq:
    r, c = dq.popleft()
    d = dist[r][c]
    for dr, dc in zip(dr_s, dc_s):
        nr = r + dr
        nc = c + dc
        if not in_range(nr, nc): continue
        if dist[nr][nc] != -1: continue
        dist[nr][nc] = d + 1
        dq.append((nr, nc))

print(d)
#ABC117B
n = int(input())
l = [int(input()) for i in range(n)]
print("Yes" if max(l) >= sum(l)-max(l) else "No")

### FIXED CODE ###

#ABC117B
n = int(input())
l = list(map(int,input().split()))
print("Yes" if max(l) < (sum(l)-max(l)) else "No")
s=input()
x,y=map(int,input().split())
X,Y=[],[]
ct,dir,ss=0,1,1
for i in range(len(s)):
  if s[i]=="F":
    ct+=1
    if i==len(s)-1:
      if dir==1:
        X.append(ct)
      else:
        Y.append(ct)
  else:
    if ss==1:
      x-=ct
      ct,dir,ss=0,0,0
    elif dir==1:
      X.append(ct)
      ct,dir=0,0
    else:
      Y.append(ct)
      ct,dir=0,1

def chk(Z,z):
  tot,nz=sum(Z),len(Z)
  if tot==0:
    if z==0:
      return True
    else:
      return False
  elif z>tot:
    return False
  else:
    DP=[[False]*(2*tot+1) for _ in range(nz+1)]
    DP[0][tot]=True
    for i in range(nz):
      zz=Z[i]
      for j in range(2*tot+1):
        if j+zz<2*tot+1:
          DP[i+1][j]=DP[i][j+zz]
        elif j-zz>=0:
          DP[i+1][j]=DP[i][j-zz]
    return DP[nz][z+tot]

if chk(X,x) and chk(Y,y):
  print("Yes")
else:
  print("No")




### FIXED CODE ###

s=input()
x,y=map(int,input().split())
ct=0
XY=[]
for i in range(len(s)):
  if s[i]=="F":
    ct+=1
  else:
    XY.append(ct)
    ct=0
XY.append(ct)
x-=XY[0]
X=XY[2::2]
Y=XY[1::2]


def chk(Z,z):
  tot,nz=sum(Z),len(Z)
  if tot==0:
    if z==0:
      return True
    else:
      return False
  elif abs(z)>tot:
    return False
  else:
    DP=[[False]*(2*tot+1) for _ in range(nz+1)]
    DP[0][tot]=True
    for i in range(nz):
      zz=Z[i]
      for j in range(2*tot+1):
        if j+zz<2*tot+1 and DP[i][j+zz]==True:
          DP[i+1][j]=True
        if j-zz>=0 and DP[i][j-zz]==True:
          DP[i+1][j]=True
    return DP[nz][z+tot]

if chk(X,x) and chk(Y,y):
  print("Yes")
else:
  print("No")
class BellmanFord:
    def __init__(self, graph, num_v, start_point):
        """
        graph : [[a1,b1,c1],[a2,b2,c2],‥]みたいな3次元配列のリスト,a1からb1までのコストはc1
        num_v :頂点の数
        start_point :スタート地点(a1)
        """
        self.num_v = num_v
        self.graph = graph
        self.start_point = start_point
 
 
    def execute(self):
        dist = [float("inf") for _ in range(self.num_v)]
        dist[self.start_point] = 0

        negative = [False for _ in range(self.num_v)]

        for i in range(self.num_v - 1):
            for start, end, cost in self.graph:
                if dist[end] > dist[start] + cost:
                    dist[end] = dist[start] + cost

        #負の経路がないなら|V-1|以上の繰り返しで最短経路の更新は行われない、負の経路の検出
        for i in range(self.num_v):
            for start, end, cost in self.graph:
                if dist[end] > dist[start] + cost:
                    dist[end] = dist[start] + cost
                    negative[end] = True
                if negative[start]:
                    negative[end] = True
        return dist, negative
 
N,M = map(int,input().split())
T = [[int(_) for _ in input().split()] for i in range(M)]

E = []
for a, b, c in T:
    E.append((a - 1, b - 1, c))

bellman = BellmanFord(graph, n, 0)
result, negative = bellman.execute()
 
if negative[-1]:
    print("inf")
else:
    print(-result[-1])

### FIXED CODE ###

class BellmanFord:
    def __init__(self, graph, num_v, start_point):
        """
        graph : [[a1,b1,c1],[a2,b2,c2],‥]みたいな3次元配列のリスト,a1からb1までのコストはc1
        num_v :頂点の数
        start_point :スタート地点(a1)
        """
        self.num_v = num_v
        self.graph = graph
        self.start_point = start_point
 
 
    def execute(self):
        dist = [-1*float("inf") for _ in range(self.num_v)]
        dist[self.start_point] = 0

        negative = [False for _ in range(self.num_v)]

        for i in range(self.num_v - 1):
            for start, end, cost in self.graph:
                if dist[end] < dist[start] + cost:
                    dist[end] = dist[start] + cost

        for i in range(self.num_v):
            for start, end, cost in self.graph:
                if dist[end] < dist[start] + cost:
                    dist[end] = dist[start] + cost
                    negative[end] = True
                if negative[start]:
                    negative[end] = True
        return dist, negative

N,M = map(int,input().split())
T = [[int(_) for _ in input().split()] for i in range(M)]
 
E = []
for a, b, c in T:
    E.append((a - 1, b - 1, c))

bellman = BellmanFord(E, N, 0)
result, negative = bellman.execute()
 
if negative[-1]:
    print("inf")
else:
    print(result[-1])
n = int(input())
str_list = input().split()

result = 1

for i in range(n):
  result = result + str_list(i)
  
t = 1
for j in range(18)
  t = t * 10
if(result > t):
  print('-1')
else:
  print(result)
   

### FIXED CODE ###

n = int(input())
str_list = input().split()

list = [int(k) for k in str_list]

list.sort(reverse=True)

result = 1

if(0 in list):
  print('0')
  exit()

for i in range(n):
  result = result * list[i]
  if(result > 1000000000000000000):
    print('-1')
    exit()

print(result)
A , B = map( int , input().split() )

import math

print( A * B // math.gcd( A , B ))

### FIXED CODE ###

A , B = map( int , input().split() )

import fractions

print( A * B // fractions.gcd( A , B ))
import numpy as np
n = int(input())
a = np.array([int(i) for i in input().split()])
a_sum = a.sum()
ans = 10**15
for i in range(1,n):
    x = a[:i].sum()
    aa = np.abs(2 * x - a_sum)
    ans = min(ans,aa)
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array([int(i) for i in input().split()])
a_c = a.cumsum()
a_t = a_c[-1]
diff = np.abs(2 * a_c - a_t)
ans = diff[:-1].min()
print(ans)
import math
dish = [int(input()) for _ in range(5)]
sm = 9
smin = 0
for item in dish:
  r = item % 10
  if 1 <= r <= 10:
    if sm > r:
      sm = r
      smin = item
ans = 0    
for cnt, item in enumerate(dish):
  if cnt == smin:
    ans += item
  else:
    ans += math.ceil(item, -1)
print(ans)    

### FIXED CODE ###

import math
dish = [int(input()) for _ in range(5)]
sm = 9
smin = 0
for cnt, item in enumerate(dish):
  r = item % 10
  if 1 <= r <= 9:
    if sm > r:
      sm = r
      smin = cnt
ans = 0    
for cnt, item in enumerate(dish):
  if cnt == smin:
    ans += item
  else:
    r = item % 10
    if 1 <= r <= 9:
      ans += item + 10 - r
    else:
      ans += item
print(ans)
N = int(input())
Dictionary = {}
for i in range(N):
    S = input()
    if S not in Dictionary :
        Dictionary[S] = 1
    else :
        Dictionary[S] = Dictionary[S]+1
sorted_Dic = sorted(Dictionary.items(), key=lambda x: x[1],reverse=True)

ans_list = []
for i in range(N):
    if sorted_Dic[i][1]==sorted_Dic[0][1]:
        ans_list.append(sorted_Dic[i][0])
    else:
        break;
for item in sorted(ans_list):
  print(item)
    

### FIXED CODE ###

N = int(input())
Dictionary = {}
for i in range(N):
    S = input()
    if S not in Dictionary :
        Dictionary[S] = 1
    else :
        Dictionary[S] = Dictionary[S]+1

sorted_Dic = sorted(Dictionary.items(), key=lambda x: x[1],reverse=True)

if len(sorted_Dic)==1:
  print(sorted_Dic[0][0])
else:
  ans_list = []
  for i in range(N):
      if sorted_Dic[i][1]==sorted_Dic[0][1]:
          ans_list.append(sorted_Dic[i][0])
      else:
          break;
  for item in sorted(ans_list):
    print(item)
year = int(input())

if year < 1 or 9 < year:
    raise ValueError
elif year is in [3, 5, 7]:
    print('YES')
else:
    print('NO')


### FIXED CODE ###

year = int(input())

if year < 1 or 9 < year:
    raise ValueError('Input value must be less than 9 and more than 1')
elif year in [3, 5, 7]:
    print('YES')
else:
    print('NO')
def main():
    s = list(input())
    t = list(input())
    s = sorted(s)
    t = sorted(t)
    ind = 0
    for i in range(len(s)):
        if s[i] == t[i]:
            ind = i
    shrt = False
    for i in range(ind, len(t)):
        if s[0] < t[i]:
            shrt = True
            break
    if shrt :
        print("Yes")
    else:
        print("No")
main()

### FIXED CODE ###

def main():
    s = list(input())
    t = list(input())
    s = sorted(s)
    t = sorted(t)
    t = t[::-1]
    
    if "".join(s) < "".join(t):
        print("Yes")
    else:
        print("No")
main()
from sys import stdin

[int(x) for x in list(stdin.readline())]

### FIXED CODE ###

print(input().count("1"))
H,N = map(int,input().split())
A = list(map(int,input().split()))
if sum(A)>=H:
  print(Yes)
else:
  print(No)

### FIXED CODE ###

H,N = map(int,input().split())
A = list( map(int,input().split()))
if sum(A)>=H:
    print("Yes")
else:
    print("No")
a=list(input())
count=0
kekka=[]
for i in range(len(a)):
    if a[i]=="A" or a[i]=="T" or a[i]=="C" or a[i]=="G":
        count+=1
    else:
        kekka.append(count)
        count=0
print(max(kekka))

### FIXED CODE ###

a=list(input())
count=0
kekka=[]
for i in range(len(a)):
    if a[i]=="A" or a[i]=="T" or a[i]=="C" or a[i]=="G":
        count+=1
    else:
        count=0
    kekka.append(count)
        
print(max(kekka))
n = int(input())
x = list(map(int, input().split()))

sortedx = x[:]
sortedx.sort()

for i in range(n):
    #ix = sortedx.index(x[i])
    #print(sortedx)
    #print(ix)
    if x[i] <= sortedx[n//2-1]:
        print(sortedx[n//2-1])
    else:
        print(sortedx[n//2-2])

### FIXED CODE ###

a, b, x = list(map(int, input().split()))

if a>x:
    print('NO')
elif a+b<x:
    print('NO')
else:
    print('YES')
n = int(input())
if n==1:
  	print("Hello World")
else:
  	a,b = map(int,input().split())
    print(int(a+b))


### FIXED CODE ###

n = int(input())
if n==1:
  print("Hello World")
else:
  a = int(input())
  b = int(input())
  print(int(a+b))
a, b, c= map(int,input().split())
if a<b:
    if b<c:
        x=a
        y=b
        z=c
    elif b>c:
        if c<a:
            x=c
            y=a
            z=b
        else:
            x=a
            y=c
            z=b
if a>b:
    if b>c:
        x=c
        y=b
        z=a
    elif b<c:
        if c<a:
            x=b
            y=c
            z=a
        else:
            x=b
            y=a
            z=c
    

print(str(x)+" "+str(y)+" "+str(z))

### FIXED CODE ###

a= list(map(int,input().split()))
a.sort()
print(a[0], a[1], a[2])
a,b,c,d = list(map(int, input().split()))
if a+b>=d:
    print(a)
else:
    print(a-(d-a-b)

### FIXED CODE ###

a,b,c,d= list(map(int, input().split()))
if d<a:
    print(d)
elif d<a+b:
    print(a)
else:
    print(a-(d-a-b))
from collections import Counter
N=int(input())
S=Counter(list(input()))

for i in range(1,N):
  S_=Counter(list(input()))
  for s in S:
    if S_[s]<S[s]:
      S[s]=S_[s]

ans=[]
for s in S:
  for _ in range(S[s]):
    ans.append(s)
print("".join(sorted(ans))

### FIXED CODE ###

from collections import Counter
N=int(input())
S=Counter(list(input()))

for i in range(1,N):
  S_=Counter(list(input()))
  for s in S:
    if S_[s]<S[s]:
      S[s]=S_[s]

ans=[]
for s in S:
  for _ in range(S[s]):
    ans.append(s)
print("".join(sorted(ans)))
import collections
 
s = input()
K = int(input())
 
l = len(s)
sub = set()
 
if l <= 50:
    for i in range(l):
        for j in range(i+1):
            sub.add(s[j:i+1])
    #print(sub)
    subl = list(sub)
    subl.sort()
    #print(subl)
    print(subl[K-1])
 
else:
    cl = collections.Counter(s).most_common()
    cl.sort(key=lambda x: x[0])
    #print(cl)
    be = cl[0][0]
    for i in range(l):
        if s[i] == be:
            for j in range(K):
                sub.add(s[i:i+j+1])
    #print(sub)
    subl = list(sub)
    subl.sort()
    print(subl[K-1])

### FIXED CODE ###

import collections

s = input()
K = int(input())

l = len(s)
sub = set()

if l <= 50:
    for i in range(l):
        for j in range(i+1):
            sub.add(s[j:i+1])
    #print(sub)
    subl = list(sub)
    subl.sort()
    #print(subl)
    print(subl[K-1])

else:
    cl = collections.Counter(s).most_common()
    cl.sort(key=lambda x: x[0])
    #print(cl)
    d = 0
    while len(sub) < K:
        be = cl[d][0]
        for i in range(l):
            if s[i] == be:
                for j in range(K):
                    sub.add(s[i:min(i+j+1,l)])
        d += 1
    #print(sub)
    subl = list(sub)
    subl.sort()
    print(subl[K-1])
n, m = map(int,input().split())
lst = list(map(int,input().split()))
lst = sorted(lst)
lst = reversed(lst)
x = sum(lst)
if (lst[m] < x/4/m):
  print("No")
else:
  print("Yes")

### FIXED CODE ###

n, m = map(int,input().split())
lst = list(map(int,input().split()))
lst.sort()
lst.reverse()
x = sum(lst)
if (lst[m - 1] < x/4/m):
  print("No")
else:
  print("Yes")
dp = [[0 for i in range(N-j)] for j in range(N)]
dp
for j in range(N):
    dp[j][0]=(int(S[j])%mod)
    for i in range(1,N-j):
        dp[j][i]=((dp[j][i-1]*10+int(S[j+i]))%mod)
ans = 0
for i in range(N):
    ans += dp[i].count(0)
    
print(ans)

### FIXED CODE ###

from collections import Counter

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

def solve_2(S):
    ind = (i for i, x in enumerate(S, 1) if x % 2 == 0)
    return sum(ind)

def solve_5(S):
    ind = (i for i, x in enumerate(S, 1) if x % 5 == 0)
    return sum(ind)

def solve(S,P):
    if P == 2:
        return solve_2(S)
    if P == 5:
        return solve_5(S)
    S = S[::-1]
    T = [0] * len(S)
    T[0] = S[0] % P
    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= P
        T[i] = T[i-1] + power * S[i]
        T[i] %= P
    counter = Counter(T)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]


print(solve(S,P))
weather=["Sunny","Cloudy","Rainy"]
s=input()
pritn(weather[weather.index[s]-2])

### FIXED CODE ###

weather=["Sunny","Cloudy","Rainy"]
S=input()
print(weather[weather.index(S)-2])
x = list(map(int, input().split()))
    count = 1
    for i in x:
        if i == 0:
            print(count)
            break
        count += 1

### FIXED CODE ###

x = list(map(int, input().split()))
count = 1
for i in x:
  if i == 0:
    print(count)
    break
  count += 1
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
from collections import deque
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j]=='#':
      continue
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0
    q = deque([[i,j]])
    while q:
      a = q.popleft()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for m in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        h = m[0]
        w = m[1]
        if (h<0)or(h>H-1)or(w<0)or(w>W-1):
          continue
        if S[h][w]=='#':
          A[h][w]=0
          continue
        c = b+1
        if c>=A[h][w]:
          continue
        A[h][w]=c
        q.append([h,w])
        
    A = [a for a in b for b in A if a!=inf]
    ans = max(ans,max(max(A)))
    
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
from collections import deque
import numpy as np
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j]=='#':
      continue
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0
    q = deque([[i,j]])
    while q:
      a = q.popleft()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for m in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        h = m[0]
        w = m[1]
        if (h<0)or(h>H-1)or(w<0)or(w>W-1):
          continue
        if S[h][w]=='#':
          continue
        c = b+1
        if c>=A[h][w]:
          continue
        A[h][w]=c
        q.append([h,w])
      
    A = np.array(A)
    ans = max(ans,max(A[A<10**5]))
    
print(ans)
import math

def LCM(a,b):
    return a*b/math.gcd(a,b)

if __name__=="__main__":
    A,B,C,D=map(int,input().split())
    lcm=LCM(C,D)
    count=B//C+B//D-B//lcm
    count1=(A-1)//C+(A-1)//D-(A-1)//lcm
    result=B-A+1-count+count1
    print(int(result))

### FIXED CODE ###

import fractions

def LCM(a,b):
    return int(a*b/fractions.gcd(a,b))

if __name__=="__main__":
    A,B,C,D=map(int,input().split())
    lcm=LCM(C,D)
    count=B//C+B//D-B//lcm
    count1=(A-1)//C+(A-1)//D-(A-1)//lcm
    result=B-A+1-count+count1
    print(int(result))
N,K=map(int,input().split())
ans=list()
for i in range(K):
  D=int(input())
  L=list(map(int,input(),split()))
  ans+=L
  ans=list(set(ans))
print(N-len(ans))

### FIXED CODE ###

A,B=map(int,input().split())
R=list(range(1,A+1))
for i in range(2*B):
  L=list(map(int,input().split()))
  if i%2==1:
    for j in range(len(L)):
      if L[j] in R:
        R.pop(R.index(L[j]))
  if R==list():
    break
print(len(R))
a, b = int(input().split())

print(a*b)

### FIXED CODE ###

a, b = map(int, input().split())
print(a*b)
input_string = input().split()

K = int(input_string[0])
A = int(input_string[1])
B = int(input_string[2])

if (A > B):
    print(K+1)
    
# y = -Ax + B(K-x)
# y = -Ax + BK - Bx
# y = -(A + B)x + BK

y = -(A + B)*0 + B*K + 1

print(y)


### FIXED CODE ###

input_string = input().split()
N = int(input_string[0])
K = int(input_string[1])

r = int(N / 2 + 0.5)

if (r >= K):
    print("YES")
else:
    print("NO")
n = int(input())
m=list(map(int,input().split()))
d={}
k=0
for i in range(n):
    k+=m[i]
    if m[i] in d:
        d[m[i]]+=1
    else:
        d[m[i]]=1
for x in range(int(input())):
    
    b,c=list(map(int,input().split()))

    k+=d[b]*(c-b)
    
    if c in d:
        d[c]+=d[b]
    else:
        d[c] = d[b]
    del d[b] 
    print(k)

### FIXED CODE ###

n = int(input())
m=list(map(int,input().split()))
d={}
k=0
for i in range(n):
    k+=m[i]
    if m[i] in d:
        d[m[i]]+=1
    else:
        d[m[i]]=1
for x in range(int(input())):
    
    b,c=list(map(int,input().split()))

    
    
    if b in d:
        k+=d[b]*(c-b)
        if c in d:
            d[c]+=d[b]
        else:
            d[c] = d[b]
        del d[b] 
    print(k)
N=int(input())
S=input()
ans=0
for i in range(N-2):
	if S[i]+S[i+1]+S[i+2]=='ABC':
		ans+=1
print(ans)

### FIXED CODE ###

k,x= map(int, input().split())

if 500*k>=x:
    print('Yes')
else:
    print('No')
n,x,m = list(map(int,input().split()))

ans = x % m
dic = dict()
dicNum = dict()
dicSum = dict()

if n > 10000:
    for i in range(2,n+1):
        b = x
        x = x**2 % m
        if x in dicNum.keys():
            t = i - dicNum[x]
            zan = n - i + 1
            k = zan // t
            ans += (dicSum[i-1] - dicSum[dicNum[x]-1]) * k
            if zan% t != 0:
                zan = zan % t
                ans += dicSum[dicNum[x] - 1 + zan] - dicSum[dicNum[x]-1]
            break
        else:
            ans += x
            dicSum[i] = ans
            dic[x] = ans
            dicNum[x] = i

else:
    for i in range(2,n+1):
        ans += x
        dicSum[i] = ans
        dic[x] = ans
        dicNum[x] = i

print(ans)

### FIXED CODE ###

n,x,m = list(map(int,input().split()))

if x == 0:
    ans = 0
else:
    ans = x % m
dicNum = dict()
dicSum = dict()
dicNum[x] = 1
dicSum[1] = x
dicSum[0] = 0

for i in range(2,n+1):
    b = x
    x = x**2 % m
    if x in dicNum.keys():
        t = i - dicNum[x]
        zan = n - i + 1
        k = zan // t
        ans += (dicSum[i-1] - dicSum[dicNum[x]-1]) * k
        if zan% t != 0:
            zan = zan % t
            ans += dicSum[dicNum[x] - 1 + zan] - dicSum[dicNum[x]-1]
        break
    else:
        ans += x
        dicSum[i] = ans
        dicNum[x] = i

print(ans)
import math
N=int(input())
a=list(map(int,input().split()))
b=0
d=0
e=0
for i in range(N):
  b+=a[i]
c=b
b=b//N


if (c-b)*10>5:
  b+=1
for i in range(N):
  if a[i]>b:
    d+=b
  else:
    e+=b
print(math.sqrt(d-e))

  

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
m=10**4
for i in range(n):
  b=a[:i+1]
  c=a[i+1:]
  
  if abs(sum(b)-sum(c))<m:
    m=abs(sum(b)-sum(c))
    
print(m)
import sys
d0=[0]*1024
d1=[[0 for i in range(286)]for j in range(1024)]
B=[1,2,4,8,16,32,64,128,256,512]

def init():
  global d0,d1
  for i in range(1024):
    binary=format(i,'b')
    n0=binary.count('1')
    d0[i]=n0
    if n0==1:
      d1[i][B.index(i)]=1
    else:
      for j in range(len(binary)):
        dp=n0*j
        if binary[-j-1]=='1':
          i2=i-B[j]
          for k in range(286-dp):
            d1[i][k+dp]+=d1[i2][k]
  return
  
def f0070(n,s):
  x=sum([d1[i][s] for i in range(1024) if d0[i]==n])
  return x

init()
for a in sys.stdin:
  n,s=map(int,a.split())
  print f0070(n,s)

### FIXED CODE ###

import sys
K=1024
N=331
R=range(K)
B=[1,2,4,8,16,32,64,128,256,512]
C=[0]*K
D=[[0 for i in range(N)]for j in R]

for i in R:
  s=format(i,'b')
  n=s.count('1')
  C[i]=n
  if n==1:D[i][B.index(i)]=1
  else:
    for j in range(len(s)):
      if s[-j-1]=='1':
        dp=n*j
        i2=i-B[j]
        for k in range(N-dp):
          D[i][k+dp]+=D[i2][k]
   
for a in sys.stdin:
  n,s=map(int,a.split())
  x=0
  if s<N:x=sum([D[i][s] for i in R if C[i]==n])
  print x
import sys
n = int(sys.argv[1])
a = int(sys.argv[2])
b = int(sys.argv[3])
print(min(a*n, b))



### FIXED CODE ###

import sys
n, a, b = [int(x) for x in input().split()]
print(min(a*n, b))
import numpy as np

n = int(input())

a = list(map(int, input().split()))
p = np.prod(a)

top = p
under = 0

for aa in a:
    under += p / aa

print(top / under)


### FIXED CODE ###

import numpy as np

n = int(input())

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

ue = 1

for aa in a:
    ue *= aa

shita = 0

for aa in a:
    shita += ue / aa

print(ue / shita)
import math
A,B=map(int,input().split())
gcd_list=[]
so_list=[]
for num in range(2,math.gcd(A,B)+1):
    if A%num==0 and B%num==0:
        gcd_list.append(num)
for i in gcd_list:
    flag=0
    if len(so_list)==0:
        so_list.append(i)
    else:
        for num in so_list:
            if i%num==0:
                flag=1
                break
        if flag==0:
            so_list.append(i)
print(len(so_list)+1)


### FIXED CODE ###

from math import gcd
A, B = map(int,input().split())
max_cmn_div = gcd(A, B)

# 約数列挙関数
def make_divisor(n):
    divisor = []
    for i in range(1, int(n**(1/2))+1):
        if n % i == 0:
            divisor.append(i)
            if i != n//i:
                divisor.append(n//i)
    return divisor

def check_prime(n):
    for i in range(2, int(n**(1/2))+1):
        if n % i == 0:
            return 0
    return 1

cmn_div = make_divisor(max_cmn_div)
ans = 0
for i in cmn_div:
    if check_prime(i):
        ans += 1
print(ans)