Harryxun/stf_run huggingface dataset:
def f(n, k):
  num_bit = 3 - bin(k).count('1')
  c = [0, 0, 1, 3]
  return 3**n - num_bit*2**n + c[num_bit]

# k = 0:(), 1:(3), 2(5), 3:(3, 5), 4:(7), 5:(3, 7), 6:(5, 7), 7:(3, 5, 7)
def solve(N, k=0):
  n = len(N)
  num_used = bin(k).count('1')
  if n + num_used < 3:
    return 0
  else:
    a = int(N[0])
    base = sum([f(i, k) for i in range(3, n)])
    if a > 7:
      return sum([f(i, k) for i in range(3, n+1)])
    elif a == 7:
      return base + f(n-1, k|2) + f(n-1, k|1) + solve(N[1:], k|4)
    elif a > 5:
      return base + f(n-1, k|2) + f(n-1, k|1)
    elif a == 5:
      return base + f(n-1, k|1) + solve(N[1:], k|2)
    elif a > 3:
      return base + f(n-1, k|1)
    elif a == 3:
      return base + solve(N[1:], k|1)
    elif a > 0:
      return base
    else: # a == 0
      return solve(N[1:])

print(solve(input()))

### FIXED CODE ###

def f(n, k):
  num_bit = 3 - bin(k).count('1')
  c = [0, 0, 1, 3]
  return 3**n - num_bit*2**n + c[num_bit]

# k = 0:(), 1:(3), 2(5), 3:(3, 5), 4:(7), 5:(3, 7), 6:(5, 7), 7:(3, 5, 7)
def solve(N, k=0):
  n = len(N)
  num_used = bin(k).count('1')
  if n==0 and num_used==3:
    return 1
  elif n==0 or n+num_used<3:
    return 0
  else:
    a = int(N[0])
    if a > 7:
      return f(n-1, k|1) + f(n-1, k|2) + f(n-1, k|4)
    elif a == 7:
      return f(n-1, k|2) + f(n-1, k|1) + solve(N[1:], k|4)
    elif a > 5:
      return f(n-1, k|2) + f(n-1, k|1)
    elif a == 5:
      return f(n-1, k|1) + solve(N[1:], k|2)
    elif a > 3:
      return f(n-1, k|1)
    elif a == 3:
      return solve(N[1:], k|1)
    else:
      return 0

N = input()
base = sum([f(i, 0) for i in range(3, len(N))])
print(solve(N) + base)
s = input()
l = []
cnt = 0
for i in s:
    if i == "A" or i =="C" or i == "G" or i == "T":
        cnt += 1
        
    else:
        l.append(cnt)
print(max(l))

### FIXED CODE ###

s = input()
l = []
cnt = 0
for i in range(len(s)):
    if s[i] == "A" or s[i] =="C" or s[i] == "G" or s[i] == "T":
        cnt += 1
        #print(i, cnt)
        if i == len(s) - 1:
            l.append(cnt)
            
        
        
        
    elif i != "A" or i !="C" or i != "G" or i != "T":
        l.append(cnt)
        cnt = 0
        #print("y")
print(max(l))
def solve(i, m):
  if dp[i][m] != -1:
    return dp[i][m]

  if m == 0:
    dp[i][m] = 1
  elif i >= n:
    dp[i][m] = 0
  elif solve(i+1, m):
    dp[i][m] = 1
  elif solve(i+1, m-A[i]):
    dp[i][m] = 1
  else:
    dp[i][m] = 0

  return dp[i][m]



n = input()
A = map(int, raw_input().split())
p = input()
m = map(int, raw_input().split())

dp = [[]]

for i in range(n):
  for m in range(p):
    dp[i][m] == -1

for i in range(p):
  if solve(0, m[i]):
    print 'yes'
  else:
    print 'no'

### FIXED CODE ###

def solve(i, m):
  if dp[i][m] != -1:
    return dp[i][m]

  if m == 0:
    dp[i][m] = 1
  elif i >= n:
    dp[i][m] = 0
  elif solve(i+1, m):
    dp[i][m] = 1
  elif solve(i+1, m-A[i]):
    dp[i][m] = 1
  else:
    dp[i][m] = 0

  return dp[i][m]



n = input()
A = map(int, raw_input().split())
p = input()
m = map(int, raw_input().split())

dp = [[-1 for col in range(2000)] for row in range(n+1)]

for i in range(p):
  if solve(0, m[i]):
    print 'yes'
  else:
    print 'no'
from heapq import *
def abc144c():
  n,k=map(int,input().split())
  a=sorted(list(map(int,input().split())))
  f=sorted(list(map(int,input().split())))[::-1]
  q=[] 
  for i,j in zip(a,f):
    heappush(q,(-i*j,j))
  kk=min(k,10**12)
  for i in range(k):
    tmp,key=heappop(q)
    heappush(q,(tmp+key,key))
  ans,key=heappop(q)
  print(max(-ans,0))
abc144c()


### FIXED CODE ###

a,b=map(int,input().split())
if 1<=a<=9 and 1<=b<=9:
  print(a*b)
else:
  print(-1)
x, y = map(str, input().split())
if x == y:
  print("=")
else:
  if x==A:
    print(">")
  elif x==B:
    if y==A:
      print("<")
    else:
      print(">")
  elif x == C:
    if y==A or y==B:
      print("<")
    else:
      print(">")

### FIXED CODE ###

x, y = map(str, input().split())
if x == y:
  print("=")
else:
  if x=="A":
    print("<")
  elif x=="B":
    if y=="A":
      print(">")
    else:
      print("<")
  elif x == "C":
    if y=="A" or y=="B":
      print(">")
    else:
      print("<")
  elif x == "D":
    if y=="E" or y=="F":
      print("<")
    else:
      print(">")
  elif x == "E":
    if y == "F":
      print("<")
    else:
      print(">")
  else:
    print(">")
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
for i in range(m):
  b,c=map(int,input().split())
  chk=False
  for j in range(b):
    if a[j]<c:
      a[j]=c
      chk=True
    else:
      break
  j+=1
  if chk:
    for k in range(j,n):
      if a[k]>c:
        break
    a=a[j:k]+a[0:j]+a[k:n] 
print(sum(a))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
dic={}
for i in range(m):
  b,c=map(int,input().split())
  if c in dic:
    dic[c]+=b
  else:
    dic[c]=b
ol=sorted(dic.items(), reverse=True, key=lambda x:x[0])
index=0
loopstop=False
for li in ol:
  for i in range(li[1]):
    if li[0]>a[index]:
      a[index]=li[0]
      index+=1
      if index>=n:
        loopstop=True
        break;
    else:
      loopstop=True
      break;
  if loopstop:
    break
print(sum(a))
n=int(input())
dat = list(map(int, input().split()))

 re=1
     
print(re)
     

 
      
      
             


    
    
     
                

         
           




### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()
a, b, n = map(int, input().split())

x = 0
ans = 0
if n < b:
    x = n
    ans = math.floor(a*x/b) - a * math.floor(x/b)
else:
    x = n - 1
    ans = math.floor(a*x/b) - a * math.floor(x/b)
print(ans)

### FIXED CODE ###

import math
a, b, n = map(int, input().split())

x = 0
ans = 0
if n < b:
    x = n
    ans = math.floor(a*x/b) - a * math.floor(x/b)
else:
    x = b - 1
    ans = math.floor(a*x/b) - a * math.floor(x/b)
print(ans)
A, B, C, D = map(int, input().split())

x = C / B
y = C % B
p = A / D
q = A % D

if (x < p):
  print("Yes")
elif (x > p):
  print("No")
else
  if (y == 0):
    print("Yes")
  elif (y <> 0 and q == 0):
    print("No")
  else :
    print("Yes")


### FIXED CODE ###

A, B, C, D = map(int, input().split())
 
flg = True
t = False
while(flg):
  C -= B
  if (C <= 0):
    t = True
    break
  A -= D
  if (A <= 0) :
    t = False
    break

if (t):
  print("Yes")
else:
  print("No")
for i, s in enumerate(S):
    if i != len(S)-1:
        if s == 'R':
            if S[i+1] == 'R':
                R_counter += 1
            else:
                R_counter += 1
                index_save = i
        if s == 'L':
            if S[i+1] == 'L':
                L_counter += 1
            else:
                L_counter += 1
                output[index_save] = ((R_counter+1)//2 + L_counter //2)
                output[index_save+1] = (R_counter//2 + (L_counter+1)//2)
                R_counter = 0
                L_counter = 0
    else:
        L_counter += 1
        output[index_save] = ((R_counter+1)//2 + L_counter //2)
        output[index_save+1] = (R_counter//2 + (L_counter+1)//2)
        
        
print(*output)



    

### FIXED CODE ###

S = input()

output = [0] * len(S)
R_counter = 0
L_counter = 0
index_save = 0

for i, s in enumerate(S):
    if i != len(S)-1:
        if s == 'R':
            if S[i+1] == 'R':
                R_counter += 1
            else:
                R_counter += 1
                index_save = i
        if s == 'L':
            if S[i+1] == 'L':
                L_counter += 1
            else:
                L_counter += 1
                output[index_save] = ((R_counter+1)//2 + L_counter //2)
                output[index_save+1] = (R_counter//2 + (L_counter+1)//2)
                R_counter = 0
                L_counter = 0
    else:
        L_counter += 1
        output[index_save] = ((R_counter+1)//2 + L_counter //2)
        output[index_save+1] = (R_counter//2 + (L_counter+1)//2)
        
        
print(*output)
# -*- coding: utf-8 -*
n = int(raw_input())
x =[]
x = map(int, raw_input().split())

for i in range(n):
 copyx = list(x)
 del copyx[i]
 copyx.sort()
 b = copyx[int((n-1)/2)]
 print(b)

### FIXED CODE ###

# -*- coding: utf-8 -*-
a,b,x = map(int, raw_input().split())
if a<=x and x<=a+b:
 print("YES")
else:
 print("NO")
n=int(input())
t=input()
T=list(t)

num=n/2

if T[0:num]==T[num:6]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n=int(input())
t=input()
T=list(t)

num=round(n/2)
 

if T[0:num]==T[num:n]:
	print("Yes")
else:
	print("No")
N = int(input())
A = list(map(int,input().split()))
B = [A[i]-i for i in range(N)]
S = sorted(B)

res = 0
if N%2 == 1:
    b = S[(N-1)//2]#中央値
    for i in range(N):
        res += abs(B[i]-b)
else:
    medint1 = N//2
    medint2 = N//2-1
    med1 = S[medint1]
    med2 = S[medint2]
    for i in range(N):
        t1 += abs(B[i]-med1)
        t2 += abs(B[i]-med2)
    res = min(t1,t2)
print(res)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [A[i]-i for i in range(N)]
S = sorted(B)

res = 0
if N%2 == 1:
    b = S[(N-1)//2]#中央値
    for i in range(N):
        res += abs(B[i]-b)
else:
    medint1 = N//2
    medint2 = N//2-1
    med1 = S[medint1]
    med2 = S[medint2]
    t1 = 0
    t2 = 0
    for i in range(N):
        t1 += abs(B[i]-med1)
        t2 += abs(B[i]-med2)
    res = min(t1,t2)
print(res)
a, b = map(int, input().split())
if a in range(1,9);
 if b in range(1,9);
  print(a*b)
else:
  print("-1")


### FIXED CODE ###

import sys
a, b = map(int, input().split())
k = range(1,10)
if a in k:
 if b in k:
  print(a*b)
  sys.exit()
 else:
  pass
print("-1")
N, K = map(int, input().split())

lst = [0] * N

for i in range(K):
	d = input()
    A = list(map(int, input().split()))
    for a in A:
    	lst[a-1] += 1

print(lst.count(0))        

### FIXED CODE ###

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

lst = [0] * N

for i in range(K):
	d = input()
	A = list(map(int, input().split()))
	for a in A:
		lst[a-1] += 1

print(lst.count(0))
from collections import deque
f_inf = float('inf')
H, W = map(int, input().split())
ch, cw = map(int, input().split())
ch, cw = ch-1, cw-1
dh, dw = map(int, input().split())
dh, dw = dh-1, dw-1
S = [list(input()) for _ in range(H)]
m = [[f_inf]*W for _ in range(H)]
m[ch][cw] = 0
que = deque([])
que.appendleft([ch,cw])
while que:
  print(que)
  print(m)
  h, w = que.popleft()
  for dh, dw in ((1,0), (-1,0), (0, 1), (0, -1)):
    next_h, next_w = h + dh, w + dw
    if 0 <= next_h < H and 0 <= next_w < W and S[next_h][next_w] == ".":
        if m[next_h][next_w] > m[h][w]:
          m[next_h][next_w] = m[h][w] # 移動Aで行けるところにmの値を合わせる
          que.appendleft([next_h,next_w])
  for dh in range(-2, 3):
    for dw in range(-2, 3): # 移動Bで行ける範囲
      next_h, next_w = h + dh, w + dw
      if 0 <= next_h < H and 0 <= next_w < W and S[next_h][next_w] == ".":
        if m[next_h][next_w] > m[h][w] + 1: # h,wから移動Aですでに行けているところは更新されない
          m[next_h][next_w] = m[h][w] + 1 
          que.append([next_h, next_w]) # appendleftではなくappend 優先順位が後
print(m[dh][dw] if m[dh][dw] != f_inf else -1)

### FIXED CODE ###

from collections import deque
f_inf = float('inf')
H, W = map(int, input().split())
sh, sw = map(int, input().split())
sh, sw = sh-1, sw-1
eh, ew = map(int, input().split())
eh, ew = eh-1, ew-1
S = [list(input()) for _ in range(H)]
m = [[f_inf]*W for _ in range(H)]
m[sh][sw] = 0
que = deque([])
que.appendleft([sh,sw])
while que:
  h, w = que.popleft()
  for dh, dw in ((1,0), (-1,0), (0, 1), (0, -1)):
    next_h, next_w = h + dh, w + dw
    if 0 <= next_h < H and 0 <= next_w < W and S[next_h][next_w] == ".":
        if m[next_h][next_w] > m[h][w]:
          m[next_h][next_w] = m[h][w] # 移動Aで行けるところにmの値を合わせる
          que.appendleft([next_h,next_w])
  for dh in range(-2, 3):
    for dw in range(-2, 3): # 移動Bで行ける範囲
      next_h, next_w = h + dh, w + dw
      if 0 <= next_h < H and 0 <= next_w < W and S[next_h][next_w] == ".":
        if m[next_h][next_w] > m[h][w] + 1: # h,wから移動Aですでに行けているところは更新されない
          m[next_h][next_w] = m[h][w] + 1 
          que.append([next_h, next_w]) # appendleftではなくappend 優先順位が後
print(m[eh][ew] if m[eh][ew] != f_inf else -1)
import math
import os
import random
import re
import sys
def findpath(a):
  if len(a)==2:
     return abs(a[1]-a[0])    
  if len(a)==3:
    return min(abs(a[2]-a[1])+abs(a[1]-a[0]),abs(a[2]-a[0]))
  return min(abs(a[2]-a[0])+findpath(a[2::]),abs(a[1]-a[0])+findpath(a[1::]))
n=int(input())
a=input().split()
for i in range(n):
  a[i]=int(a[i])
print (findpath(a))

### FIXED CODE ###

import math
import os
import random
import re
import sys
def dpfindpath(a):
	dpath=[int(0) for _ in range(len(a))]
	dpath[0]=0
	dpath[1]=abs(a[1]-a[0])
	for i in range(2,len(a)):
		dpath[i]=min(abs(a[i]-a[i-1])+dpath[i-1],abs(a[i]-a[i-2])+dpath[i-2])
	return dpath[len(a)-1]
n=int(input())
a=input().split()
for i in range(n):
  a[i]=int(a[i])
print (dpfindpath(a))
def dfs(i, V, E):
    if i in E.keys():
        for k in E[i].keys():
            if V[k] >= 0:
                continue
            if E[i][k] % 2:
                V[k] = 1 - V[i]
            else:
                V[k] = V[i]
            V = dfs(k, V, E)
    return V

n = int(input())
E = {}
for i in range(n - 1):
    ui, vi, wi = map(int, input().split())
    if ui in E.keys():
        E[ui][vi] = wi
    else:
        E[ui] = {vi: wi}
    if vi in E.keys():
        E[vi][ui] = wi
    else:
        E[vi] = {ui: wi}
V = [-1 for _ in range(n + 1)]
V[1] = 0
V = dfs(1, V, E)
for vi in V[1:]:
    print(vi)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 5 + 1)

def dfs(i, V, E):
    for k in E[i].keys():
        if V[k] >= 0:
            continue
        if E[i][k] % 2:
            V[k] = 1 - V[i]
        else:
            V[k] = V[i]
        V = dfs(k, V, E)
    return V

n = int(input())
E = {}
for i in range(n - 1):
    ui, vi, wi = map(int, input().split())
    if ui in E.keys():
        E[ui][vi] = wi
    else:
        E[ui] = {vi: wi}
    if vi in E.keys():
        E[vi][ui] = wi
    else:
        E[vi] = {ui: wi}
V = [-1 for _ in range(n + 1)]
V[1] = 0
V = dfs(1, V, E)
for vi in V[1:]:
    print(vi)
n = int(input())
mochi = set([int(input()) for i in range(n)])
print(len(s))


### FIXED CODE ###

n = int(input())
d = set([int(input()) for i in range(n)])
print(len(d))
import bisect
inf = 10**18
a, b, q = map(int, input().split())
s = [-inf] + [int(input()) for _ in range(a)] + [inf]
t = [-inf] + [int(input()) for _ in range(a)] + [inf]

for _ in range(q):
    x = int(input())
    i = bisect.bisect_right(s, x)
    j = bisect.bisect_right(t, x)
    ans = inf
    for s_x in [s[i-1], s[i]]:
        for t_x in [t[i-1], t[i]]:
            ans0 = abs(s_x - x) + abs(t_x - s_x)
            ans1 = abs(t_x - x) + abs(s_x - t_x)
            ans = min(ans, ans0, ans1)
    print(ans)


### FIXED CODE ###

a, b, q = map(int, input().split())
s = [int(input()) for _ in range(a)]
t = [int(input()) for _ in range(b)]
x = [(int(input()), i) for i in range(q)]
x = sorted(x)

def check(x, s0, s1, t0, t1):
    ans = float('inf')
    for x1, x2 in [(s0, t0), (s0, t1), (s1, t0), (s1, t1),
                   (t0, s0), (t0, s1), (t1, s0), (t1, s1)]:
        ans = min(ans, abs(x-x1)+abs(x1-x2))
    return ans

s0, t0 = -float('inf'), -float('inf')
s1, t1 = s[0], t[0]
i_s, i_t = 0, 0
answers = []
for x_i, i in x:
    while s1 < x_i and i_s < a-1:
        s0 = s1
        i_s += 1
        s1 = s[i_s]
    while t1 < x_i and i_t < b-1:
        t0 = t1
        i_t += 1
        t1 = t[i_t]
    ans = check(x_i, s0, s1, t0, t1)
    answers.append((i, ans))

for _, ans in sorted(answers):
    print(ans)
N, K = map(int, input().split())
half=[K]
for i in range(1,K):
    if K%(2**i)==0:
        half.append(int(K/(2**i)))
    else:
        half.append(1+int(K/(2**i)))
    maxi=i
    if int(K/(2**i))==0:
        break
half.sort()

ans=[]
if half[0]<N:
   # ans.append(half[0]/(2**(maxi)))

    for i in range(maxi):

        
        if half[i+1]<N:
            sa=half[i+1]-half[i]
        #    print(half[i],sa)
            ans.append(sa/(2**(maxi-i)))
        else:
            sa=N-half[i]
      #      print(half[i],sa)
            ans.append(sa/(2**(maxi-i)))
            j=i
            break

if half[j+1]==N:
    #print(half[j+1])
    ans.append(1/(2**(maxi-j-1)))
            
if half[-1]<N:
    sa=N-half[-1]+1
  #  print(half[-1],sa,"kjh")
    ans.append(sa)



#print(half)
#print(ans)
ans=sum(ans)/N
print(ans)

### FIXED CODE ###

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

points=[]
for i in range(N):
    x=K/(i+1)
    y=math.log(x)/math.log(2)
    y=max(0,math.ceil(y))
    z=pow(2,-math.ceil(y))
    points.append(z)
print(sum(points)/N)
import sys
input = sys.stdin.readline
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)

N,M,K = map(int,input().split())
uf = UnionFind(N)
lst=[0]*(N)
ans=[0]*(N)
for i in range(M):
 A,B=map(int,input().split())
 uf.union(A-1,B-1)
 lst[A-1]+=1
 lst[B-1]+=1
for i in range(K):
 A,B=map(int,input().split())
 if uf.same(A-1,B-1):
  lst[A-1]+=1
  lst[B-1]+=1
for i in range(N):
 ans[i]=uf.size(i)-lst[i]-1
L=[str(a) for a in ans]
L=' '.join(L)
print(L)


### FIXED 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)

N,M,K = map(int,input().split())
uf = UnionFind(N)
lst=[0]*(N)
ans=[0]*(N)
for i in range(M):
 A,B=map(int,input().split())
 uf.union(A-1,B-1)
 lst[A-1]+=1
 lst[B-1]+=1
for i in range(K):
 A,B=map(int,input().split())
 if uf.same(A-1,B-1):
  lst[A-1]+=1
  lst[B-1]+=1
for i in range(N):
 ans[i]=uf.size(i)-lst[i]-1
L=[str(a) for a in ans]
L=' '.join(L)
print(L)
import numpy as np

n = int(input())
x = [tuple(map(int, input().split())) for _ in range(n)]

def circle(x, y, z):

    ra = np.array(x)
    rb = np.array(y)
    rc = np.array(z)

    A = np.dot(rb-rc,rb-rc)
    B = np.dot(rc-ra,rc-ra)
    C = np.dot(ra-rb,ra-rb)

    T = A*(B+C-A)
    U = B*(C+A-B)
    W = C*(A+B-C)

    rcc = (T*ra + U*rb + W*rc)/(T + U + W)

    return rcc

def dis(a, b, c, d):
    return (a - b)**2 + (c - d)**2

e = 10 ** (-9)
ans = 10 ** 18
for i in range(n):
    for j in range(i+1, n):
        a = x[i]
        b = x[j]
        px, py = (a[0]+b[0])/2, (a[1]+b[1])/2
        r = dis(px, a[0], py, a[1])
        ok = True
        for s, t in x:
            if dis(px, s, py, t) > r + e:
                ok = False
                break
        if ok:
            ans = min(ans, r)

if ans != 10 ** 18:
    print(ans)
    exit()

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            a = x[i]
            b = x[j]
            c = x[k]
            px, py = circle(a, b, c)
            r = dis(px, a[0], py, a[1])
            ok = True
            for s, t in x:
                if dis(px, s, py, t) > r + e:
                    ok = False
                    break
            if ok:
                ans = min(ans, r)

print(ans ** (1/2))

### FIXED CODE ###

import numpy as np

n = int(input())
x = [tuple(map(int, input().split())) for _ in range(n)]

def circle(x, y, z):

    ra = np.array(x)
    rb = np.array(y)
    rc = np.array(z)

    A = np.dot(rb-rc,rb-rc)
    B = np.dot(rc-ra,rc-ra)
    C = np.dot(ra-rb,ra-rb)

    T = A*(B+C-A)
    U = B*(C+A-B)
    W = C*(A+B-C)

    rcc = (T*ra + U*rb + W*rc)/(T + U + W)

    return rcc

def dis(a, b, c, d):
    return (a - b)**2 + (c - d)**2

e = 10 ** (-9)
ans = 10 ** 18
for i in range(n):
    for j in range(i+1, n):
        a = x[i]
        b = x[j]
        px, py = (a[0]+b[0])/2, (a[1]+b[1])/2
        r = dis(px, a[0], py, a[1])
        ok = True
        for s, t in x:
            if dis(px, s, py, t) > r + e:
                ok = False
                break
        if ok:
            ans = min(ans, r)

if ans != 10 ** 18:
    print(ans ** (1/2))
    exit()

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            a = x[i]
            b = x[j]
            c = x[k]
            px, py = circle(a, b, c)
            r = dis(px, a[0], py, a[1])
            ok = True
            for s, t in x:
                if dis(px, s, py, t) > r + e:
                    ok = False
                    break
            if ok:
                ans = min(ans, r)

print(ans ** (1/2))
n, q = int(input().split())
#n = 4
#q = 3

ans = [0]*n
ki = {}
for i in range(1,n+1):
    ki[i] = []

z = ["1 2", "2 3", "2 4"]

for i in range(n-1):
    e = list(map(int, input().split()))
    #e = list(map(int, z[i].split()))
    ki[e[0]].append(e[1])

print(ki)

def df(graph, start, point):
    stack = [start]
    visited = []
    while stack:
        v = stack.pop(0)
        ans[v - 1] += point
        if v not in visited:
            visited.append(v)
            stack = graph.get(v, []) + stack

y = ["2 10", "1 100", "3 1"]
for i in range(q):
    p = list(map(int, input().split()))
    #p = list(map(int, y[i].split()))
    df(ki, p[0], p[1])

for n in ans:
    print(n, end=" ")





### FIXED CODE ###

import sys

def main():
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    n, q = map(int, input().split())
    #n, q = map(int, "4 3".split())
    g = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        #a, b = map(int, ["1 2", "2 3", "2 4"][i].split())
        g[a-1].append(b-1)
        g[b-1].append(a-1)


    add = [0] * n
    for i in range(q):
        p, v = map(int, input().split())
        #p, v = map(int, ["2 10", "1 100", "3 1"][i].split())
        #dfs(p-1, v)
        add[p-1] += v

    ans = [0] * n
    def dfs(v,p,value): #p: parent of v
        value += add[v]
        ans[v] = value
        for c in g[v]:
            if c == p: continue
            dfs(c,v,value)
    dfs(0, -1, 0)
    """
    def dfs(start, point):
        stack = [start]
        while stack:
            x = stack.pop()
            ans[x] += point
            stack += g[x]
    """

    print(' '.join(map(str, ans)))

if __name__ == '__main__':
    main()
import sys

for line in sys.stdin:
    A=line.split()
    B=map(int,A)

    e=1

    while e != 0:
        e=B[0]%B[1]
        C=B[1]
        B[1]=e
        B[0]=C

    print B[0]

### FIXED CODE ###

A=map(int,raw_input().split())
A.sort()

while A[1]%A[0]!=0:
    temp=A[0]
    A[0]=A[1]%A[0]
    A[1]=temp

print A[0]