Harryxun/stf_run huggingface dataset:
n = int(input())
tree = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c
    tree[a].append((b, c))
    tree[b].append((a, c))

limit = 100010
depth = [0] * limit

def dfs(v, p, d): # (現在の頂点v, vの親, 現在の距離)
    depth[v] = d
    for e in tree[v]:
        if e[0] == p: continue
        dfs(e[0], v, d + e[1])

q, k = map(int, input().split())
k -= 1
dfs(k, -1, 0)
for i in range(q):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    res = depth[x] + depth[y]
    print(res)

### FIXED CODE ###

n = int(input())
tree = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c
    tree[a].append((b, c))
    tree[b].append((a, c))

from heapq import heappush, heappop
INF = 10 ** 18
def dijkstra(s, n): # (始点, ノード数)
    dist = [INF] * n
    hq = [(0, s)] # (distance, node)
    dist[s] = 0
    seen = [False] * n # ノードが確定済みかどうか
    while hq:
        v = heappop(hq)[1] # ノードを pop する
        seen[v] = True
        for to, cost in tree[v]: # ノード v に隣接しているノードに対して
            if seen[to] == False and dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(hq, (dist[to], to))
    return dist

q, k = map(int, input().split())
k -= 1
dist = dijkstra(k, n)
for i in range(q):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    res = dist[x] + dist[y]
    print(res)
n = int(input())
a = list(map(int, input().split()))

a.sort(reversed=True)
score = [0, 0]
for i in range(n):
    score[i%2] += a[i]

print(score[0] - score[1])


### FIXED CODE ###

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

a.sort(reverse=True)
score = [0, 0]
for i in range(n):
    score[i%2] += a[i]

print(score[0] - score[1])
N = int(input())
red = []
blue = []
chosen = [0]*N
ans = 0
for i in range(N):
  a,b = map(int, input().split())
  red.append((a,b))
for i in range(N):
  c,d = map(int, input().split())
  blue.append((c,d))
  
red.sort(key=lambda x:x[1])
blue.sort(key=lambda x:x[0])

for i in range(N):
  for j in range(N):
    if blue[i][0] >= red[j][0] and blue[i][1] >= red[j][1] and chosen[j] == 0
      chosen[j] = 1
      ans += 1
      break
      
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
R = []
B = []
ans = 0
for i in range(N):
  a,b = map(int,input().split())
  R.append((a,b))
for i in range(N):
  c,d = map(int,input().split())
  B.append((c,d))
R.sort(key=lambda x:x[0])
B.sort(key=lambda x:x[0])
H = []
l = 0
for i in range(N):
  for j in range(l,N):
    if R[j][0] > B[i][0]:
      l = j
      break
    H.append(R[j])
  H.sort(key=lambda x:x[1], reverse=True)
  for k in range(len(H)):
    if H[k][1] < B[i][1]:
      H.pop(k)
      ans += 1
      break
print(ans)
A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

D = float(abs(A-B))
E = float(V - W)
time = int(D/E)

if E <= 0:
	print("NO")
elif time <= T:
	print("YES")
else:
	print("NO")

### FIXED CODE ###

A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

D = float(abs(A-B))
E = float(V - W)

if E <= 0:
	print("NO")
	exit()
time = D/E
if time <= T:
	print("YES")
else:
	print("NO")
n,m=map(int,input())
k=[]
a=[]
for i in range(n):
    k.append(int(input()))
    a.append(list(map(int,input().split())))
ans=0
for i in range(n):
    f=True
    for j in range(m):
        if a[j]==0:
            f=False
    if f:
        ans+=1
print(ans)


### FIXED CODE ###

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

l=[0]*m
for i in range(n):
    ka=list(map(int,input().split()))
    A=ka[1:]
    for a in A:
        l[a-1]+=1
ans=0
for i in l:
    if i==n:
        ans+=1
print(ans)
N = int(input())
A = list(map(int, input().split()))
cnt = 0

for t in range(1,N+1):
    if t % 2 != 0 and A[t] % 2 != 0:
        cnt = cnt + 1

print(cnt)


### FIXED CODE ###

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

for t in range(1,N+1):
    if t % 2 != 0 and A[t-1] % 2 != 0:
        cnt = cnt + 1

print(cnt)
def inpul(): return list(map(int, input().split()))

 from fractions import Fraction
from functools import reduce

#最大公約数
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = inpul()
a = inpul()

ans = gcd_list(a)
print(ans)


### FIXED CODE ###

def inpul(): return list(map(int, input().split()))

import fractions
from functools import reduce

#最大公約数
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = inpul()
a = inpul()

ans = gcd_list(a)
print(ans)
A=input()
B=input()
if (A=1 and B=2)or(A=2 and B=1):
  print(3)
if (A=2 and B=3)or(A=3 and B=2):
  print(1)
if (A=3 and B=1)or(A=1 and B=3):
  print(2)


### FIXED CODE ###

A=int(input())
B=int(input())  
C=6-A-B
print(C)
import math
r = int(input())

s = r * r * math.pi
l = r * 2 * math.pi

print("%.5f %.5f" % (s,l)) 

### FIXED CODE ###

import math
r = float(input())

s = r * r * math.pi
l = r * 2 * math.pi

print("%.6f %.6f" % (s,l))
a,b = input().split()
if a == b:
  print(a*2)
else:
  print(max(a,b)*2-1)


### FIXED CODE ###

a,b = map(int,input().split())
if a == b:
    print(a*2)
else:
    c = max(a,b)
    d = c*2-1
    print(d)
import math

c1x,c1y,c1r = [int(i) for i in input().split()]
c2x,c2y,c2r = [int(i) for i in input().split()]

d = math.sqrt(pow(c1x-c2x, 2) +  pow(c1y-c2y, 2))

s = c1r + c2r

if d > s:
    print(4)
elif d == c:
    print(3)
elif d > 2*s:
    print(2)
elif d == 2*s:
    print(1)
else:
    print(0)


### FIXED CODE ###

import math

c1x,c1y,c1r = [int(i) for i in input().split()]
c2x,c2y,c2r = [int(i) for i in input().split()]

d = math.sqrt(pow(c1x-c2x, 2) +  pow(c1y-c2y, 2))

bcr = 0
scr = 0

if c1r > c2r:
    bcr = c1r
    scr = c2r
else:
    bcr = c2r
    scr = c1r


if d > bcr + scr:
    print(4)
elif d == bcr + scr:
    print(3)
elif d + scr > bcr:
    print(2)
elif d + scr == bcr:
    print(1)
else:
    print(0)
n, p = map(int ,input().split())
#引数　n, 返り値nまでの素数をリストで返す
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    #根号
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
ff = primes(p)
ans = 1
factorized = dict(zip(ff, [0 for i in range(len(ff))]))
div = 2
while p != 1:
    while p % div == 0:
        p /= div
        factorized[div] += 1
    div += 1
for i in factorized.keys():
    if factorized[i] >= n :
        ans *= i*(factorized[i] // n)
print(ans)


### FIXED CODE ###

import math
n, p = map(int ,input().split())
#引数　n, 返り値nまでの素数をリストで返す
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    #根号
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
ff = primes(int(math.sqrt(p) + 1))
ans = 1
factorized = dict(zip(ff, [0 for i in range(len(ff))]))
if n == 1:
    print(p)
    exit()
for i in factorized.keys():
    while p % i == 0:
        p /= i
        factorized[i] += 1
    
for i in factorized.keys():
    if factorized[i] >= n :
        ans *= i**(factorized[i] // n)
print(ans)
1,2,3,4,5 = input()
count = 0
for I in input():
  if I == 0:
    print(count)
  count++

### FIXED CODE ###

X = list(map(int, input().split()))
count = 1
for I in X:
  if I == 0:
    print(count)
    exit
  count += 1
A,B,C,D,E=map(int,input().split())

    if A == 0:
        print(1)
    elif B == 0:
        print(2)
    elif C == 0:
        print(3)
    elif D == 0:
        print(4)
    else E == 0:
        print(5)


### FIXED CODE ###

A,B,C,D,E=map(int,input().split())

if A == 0:
    print(1)
elif B == 0:
    print(2)
elif C == 0:
    print(3)
elif D == 0:
    print(4)
else:
    print(5)
from math import inf
import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()
n,k=get_ints()
h=get_array()
li=[inf]*n
li[0]=0

li[1]=abs(h[1]-h[0])
for i in range(2,n):
    for j in range(i-1,(i-k)-1,-1):
        if j<0:
            break

            #3print(i,j)
        li[i]=min(li[i],li[j]+abs(h[i]-h[j]))
##print(li)
print(li[n-1])


### FIXED CODE ###

import numpy as np
inf=10000007

n,k=map(int,input().split())
h=np.array(list(map(int,input().split())))
dp = np.zeros(n,dtype=int)
dp[0]=0

for i in range(1,n):
    l=max(0,i-k)

    dp[i] = np.min(dp[l:i] + abs(h[l:i] - h[i]))




##print(li)
print(dp[-1])
n=int(input())
x=list(map(int,input().split()))
ans=[0]*(x[n-1]-x[0]+1)
for i in range(x[n-1]-x[0]+1):
    for j in x:
        ans[i]+=(j-i)**2
print(min(ans))

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
x.sort()
ans=10**9

for i in range(x[0],x[-1]+1):
    temp=0
    for j in x:
        temp+=(j-i)**2
    ans=min(ans,temp)

print(ans)
import java.util.Scanner;
class Main
{
 public static void main(String args[])
 {
  int a,b;
  Scanner sc = new Scanner(System.in);
  while(True){
  a=sc.nextInt();
  b=sc.nestInt();
  if(a==0 && b==0)
    break;
  else if(a<b)
    System.out.println(a+" "+b);
  else
    System.out.println(b+" "+a);}
 }
}


### FIXED CODE ###

while True:
   a,b=map(int,input().split())
   if a==0 and b==0:
     break
   elif a<b:
     print(a,b)
   else:
     print(b,a)
l = int(input())
n = [int(i) for i in input().split()]
u = n.copy()
n.sort()
u.sort(reverse=True)

counter = 0

for j in range(l):
  for i in range(l):
    if n[i] == u[j]:
      pass
    elif u[j] % n[i] == 0:
      counter += 1
      break
    else:
      pass

print(l - counter)

### FIXED CODE ###

l = input().split()

for i in range(5):
  if l[i] == "0":
    print(i+1)
    break
monster, skill = map(int,input().split())

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

monster_hp.sort()

attack_count = 0

while(skill>0):
    skill -= 1
    monster_hp.pop(-1)

for hp in monster_hp:
    attack_count += hp

print(hp)

### FIXED CODE ###

monster, skill = map(int,input().split())

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

monster_hp.sort()

attack_count = 0

while(skill>0):
    skill -= 1
    if len(monster_hp) > 0:    
        monster_hp.pop(-1)
    

for hp in monster_hp:
    attack_count += hp

print(attack_count)
for i in range(9):
    for j  in range(9):
        print "%dx%d=%d", %(i+1, j+1, (i+1)*(j+1)

### FIXED CODE ###

for i in range(9):
    for j in range(9):
        print "%dx%d=%d" %(i+1,j+1, (i+1)*(j+1))
import numpy as np

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

a = np.eye(N, k=0) + np.eye(N, k=1) + np.eye(N, k=1-N)

a_matrix = np.array(a)
b_matrix = np.array(A)

x = np.linalg.solve(a_matrix,b_matrix)

x = x * 2

for i in range(N):
    print(int(x[i]),end="")
    if(i != N-1):
        print(" ",end="")
print()


### FIXED CODE ###

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

x=[]
s=sum(a)
x.append(s-2*sum(a[1::2]))
for i in range(1,n-1):
    x.append(2*a[i-1]-x[i-1])
x.append(2*a[n-1]-x[0])
print(*x)
N,M=map(int,input().split())
A=[0]+list(map(int,input().split()))

a=0
m=[0]*N
for i in range(N):
    a+=A[i]%M
    a%=M
    m[i]=a

m.sort()
ans=0
cnt=0
for i in range(N):
    if m[i]==m[i+1]:
        cnt+=1
    else:
        ans+=cnt*(cnt-1)//2
        cnt=1
ans+=cnt*(cnt-1)//2
print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
A=[0]+list(map(int,input().split()))

a=0
m=[0]*(N+1)
for i in range(N+1):
    a+=A[i]%M
    a%=M
    m[i]=a

m.sort()
ans=0
cnt=1
for i in range(N):
    if m[i+1]==m[i]:
        cnt+=1
    else:
        ans+=cnt*(cnt-1)//2
        cnt=1
ans+=cnt*(cnt-1)//2
print(ans)
from collections import defaultdict
it = lambda: list(map(int, input().strip().split()))


def solve():
    N, X, M = it()
    value = defaultdict(int)
    history = defaultdict(int)
    cur = 0
    cnt = 0
    for i in range(N):
        if X in history:
            break
        value[X] = cur
        history[X] = i
        cnt += 1
        cur += X
        X = X * X % M
    period = i - history[X]
    cur += (N - cnt) // period * (cur - value[X])
    for i in range((N - cnt) % period):
        cur += X
        X = X * X % M
    return cur

if __name__ == '__main__':
    print(solve())

### FIXED CODE ###

from collections import defaultdict
it = lambda: list(map(int, input().strip().split()))


def solve():
    N, X, M = it()
    if N == 1:
        return X % M
    value = defaultdict(int)
    history = defaultdict(int)
    cur = 0
    cnt = 0
    for i in range(N):
        if X in history:
            break
        value[X] = cur
        history[X] = i
        cnt += 1
        cur += X
        X = X * X % M
    period = i - history[X]
    cur += (N - cnt) // period * (cur - value[X])
    for i in range((N - cnt) % period):
        cur += X
        X = X * X % M
    return cur

if __name__ == '__main__':
    print(solve())
k,s = map(int, input().split())

count = 0
for i in range(k+1):
    for j in range(k+1):
        if s - (i+j) <= k:
            count += 1

print(count)

### FIXED CODE ###

print(str(input().replace(","," ")))
N=int(input())
P=list(map(int,input().split()))

m=P[0]
c=0
for i in range(N):
  if P[i]<=m:
    c+=1
  	m=P[i]
  
print(c)

### FIXED CODE ###

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

m=P[0]
c=0
for i in range(N):
  if P[i]<=m:
    c+=1
  m=min(m,P[i])
  
print(c)
S = input()
List = list(S)
trial = 0
for i in range(1,len(List)):
  if List[i] != List[i-1]:
    trial += 1
print(res)

### FIXED CODE ###

S = input()
List = list(S)
trial = 0
for i in range(1,len(List)):
  if List[i] != List[i-1]:
    trial += 1
print(trial)
n = int(input())
a = input()
b = ''
for i in range(n):
  if b[-1] != i:
    b += i
print(len(b))


### FIXED CODE ###

n = int(input())
a = input()
b = '1'
for i in range(n):
  if a[i] != b[-1]:
    b += a[i]
print(len(b)-1)
s=input()

target="keyence"
j=0

for i in range(len(s)):
    if s[i]==target[j]:
        j+=1

if j==len(target):
    print('YES')
else:
    print('NO')


### FIXED CODE ###

import sys

s=input()

target="keyence"
j=0
mismatch=0

for i in range(len(target)):
    if target[:i]==s[:i] and target[i:]==s[-7+i:]:
        print('YES')
        sys.exit()
print('NO')
X, Y, A, B, C = map(int, input().split())
Alist = list(map(int, input().split()))
Blist = list(map(int, input().split()))
cl = list(map(int, input().split()))

Alist.sort(reverse = True)
Blist.sort(reverse = True)
cl.sort(reverse = True)
list=[]

for i in range(X):
    list.append(Alist[i])
for i in range(Y):
    list.append(Blist[i])
list.sort()

for i in range(C):
    if cl[0] > list[i]:
        list[i] = cl[0]
        cl.pop(0)
ans = 0
for i in list:
    ans += i

print(ans)

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
Alist = list(map(int, input().split()))
Blist = list(map(int, input().split()))
list = list(map(int, input().split()))

Alist.sort(reverse = True)
Blist.sort(reverse = True)

for i in range(X):
    list.append(Alist[i])
for i in range(Y):
    list.append(Blist[i])
list.sort(reverse = True)

ans =0
for i in range(X + Y):
    ans += list[i]
    
print(ans)
MOD = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
plus,minus=[],[]
for i in a:
    if i<0:
        minus.append(i)
    else:
        plus.append(i)
plus.sort(reverse = True)
minus.sort()
plus.append(-float('inf'))
plus.append(float('inf'))
minus.append(float('inf'))
minus.append(-float('inf'))
ans = 1
if n == k:
    for i in range(n):
        ans *= a[i]
        ans %= MOD
    print(ans)
elif len(plus) == 2 and k % 2 == 1:
    for i in range(3, k + 3):
        ans *= minus[-i]
        ans %= MOD
    print(ans)
else:
    cplus = 0
    cminus = 0
    p = k // 2
    if k % 2 == 1:
        ans *= plus[0]
        cplus = 1
    else:
        for _ in range(p):
            if plus[cplus] * plus[cplus + 1] > minus[cminus] * minus[cminus]:
                ans *= plus[cplus] * plus[cplus + 1]
                ans %= MOD
                cplus += 2
            else:
                ans *= minus[cminus] * minus[cminus]
                ans %= MOD
                cminus += 2
    print(ans)




### FIXED CODE ###

    #n,k,*a=map(int,open(0).read().split())
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
mod=10**9+7
ans=1
i=0
j=-1
kk=k
while kk>1:
    if a[i]*a[i+1]>a[j]*a[j-1]:
        ans=ans*a[i]*a[i+1]%mod
        i+=2
        kk-=2
    else:
        ans=ans*a[j]%mod
        j-=1
        kk-=1
if kk==1:
    ans=ans*a[j]%mod

if a[-1]<0 and k%2==1:
    ans=1
    for i in a[n-k:]:
        ans=ans*i%mod
print(ans)
s=list(input())
for i in range(len(s)):
  if i%2==0 and s[i]=="L":
    print("No")
    sys.exit()
  if i%2==1 and s[i]=="R":
    print("No")
    sys.exit()
print(Yes)

### FIXED CODE ###

import sys
s=list(input())
for i in range(len(s)):
  if i%2==0 and s[i]=="L":
    print("No")
    sys.exit()
  if i%2==1 and s[i]=="R":
    print("No")
    sys.exit()
print("Yes")
n,x=int(input()),input()
g=int(x,2)
c=pow(2,n-1)
memo={}
for b in x:
    if b=="1":
        p=g-c
    else:
        p=g+c
    ret=0
    while p:
        q=bin(p).count("1")
        if (p,q)in memo:print(ret+memo[(p,q)]);break 
        p%=q
        ret+=1
    c//=2
    memo[(p,q)]=ret
    print(ret)

### FIXED CODE ###

n,x=int(input()),input()
o=x.count("1")
if o==1:
    for i,v in enumerate(x):
        if v=="1":print(0)
        else:
            if i!=n-1:
                if x[-1]=="0":print(1)
                else:print(2)
            else:print(2)

else:
    m=o-1
    M=o+1
    mp,mm={0:1},{0:1}
    for i in range(1,n):
        mp[i]=mp[i-1]*2%M
        mm[i]=mm[i-1]*2%m
    A=int(x,2)
    a=A%m
    b=A%M
    rest={0:0}
    for i in range(1,o+1):
        rest[i]=1+rest[i%bin(i).count("1")]
    for i,v in enumerate(x):
        if v=="1":
            print(1+rest[(a-mm[n-i-1])%m])
        else:
            print(1+rest[(b+mp[n-i-1])%M])
n=int(input())

A=list(map(int,input()))



print(max(A)-min(A))

### FIXED CODE ###

n=int(input())

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



print(max(A)-min(A))
import numpy as np

n = int(input())
a = [int(i) for i in input().split()] 
ans = np.array(a)

s = (n,n)
M = np.matrix(np.zeros(s))
for i in range(n):
    vec = np.zeros(n)
    vec[i]=1/2
    if i == (n-1):
        vec[0]=1/2
    else:
        vec[i+1]=1/2
    M[i] = vec
ans = (np.linalg.inv(M)*(ans.reshape(-1,1)))
print(' '.join(map(str, ans.T.tolist()[0])))

### FIXED CODE ###

import numpy as np

n = int(input())
a = [int(i) for i in input().split()] 
a = np.array(a)
x = np.zeros(n)

x[0] = sum(a) - (2*(sum(a[1::2])))

for i in range(n-1):
    x[i+1] = 2*a[i] - x[i]

print(' '.join(map(str, map(int, x))))
import math
print(math.factorial(5))

N, M = map(int, input().split())
a = []
for i in range(M):
  a.append(int(input()))
  
answer = 0
for i in range(len(a) - 1):
  dif = a[i + 1] - a[i]
  if dif >= 4:
    b = dif // 2
    tmp_sum = 0
    for j in range(b):
      tmp_sum += math.factorial(j + dif - j * 2) / (math.factorial(j) * math.factorial(dif - j * 2))
    if tmp_sum != 0 and answer = 1:
      answer += 1
    answer *= tmp_sum
    
print(answer)

### FIXED CODE ###

import math
 
N, M = list(map(int, input().split()))
stairs = [0] * (N + 1)

for i in range(M):
	stairs[int(input())] = -1

# all element of stairs
for i in range(N, -1, -1):
	# last is always 1
	if i == N:
		stairs[i] = 1
	# if stair[N - 1] is not broken 
	elif i == N - 1 and stairs[i] != -1:
		stairs[i] = stairs[i + 1]
	# if stairs[i] is not broken
	elif stairs[i] != -1:
		if stairs[i + 1] != -1:
			stairs[i] += stairs[i + 1]
		if stairs[i + 2] != -1:
			stairs[i] += stairs[i + 2]
print(int(stairs[0]) % 1000000007)
K= int(input())
A, B = map(int, input().split())
i = 0
while A <= B:
  if K / 4 == K // 4:
    i = i + 1
    A = A + 1
  else:
    i = i + 0
    A = A + 1
    
if i = 0:
  print("NG")
else:
  print("OK")

### FIXED CODE ###

K= int(input())
A, B = map(int, input().split())
i = 0
while A <= B:
  if A / K == A // K:
    i = i + 1
    A = A + 1
  else:
    i = i + 0
    A = A + 1
    
if i == 0:
  print("NG")
else:
  print("OK")
# input
X = int(input())

# process
a, b = 0, 0

nl = []
i = 0
np = 0
n = i**5
while n - np <= 10**9:
    nl.append(n)
    i += 1
    np = n
    n = i**5

for i in range(len(nl)):
    t = X-nl[i]
    if t in nl:
        a = i
        b = -(nl.index(X-nl[i]))
        break

    if -t in nl:
        a = i
        b = nl.index(X-nl[i])
        break

# output
print("{} {}".format(a, b))


### FIXED CODE ###

# input
X = int(input())

# process
a, b = 0, 0

nl = []
i = 0
np = 0
n = i**5
while n - np <= 10**9:
    nl.append(n)
    i += 1
    np = n
    n = i**5

for i in range(len(nl)):
    t = X-nl[i]
    if t in nl:
        a = i
        b = -(nl.index(t))
        break

    if -t in nl:
        a = i
        b = nl.index(-t)
        break

# output
print("{} {}".format(a, b))
n = int(input())
ans = "No"
for i in range(9):
    if n%(9-i)==0:
        if n/(9-i)<10:
            s="Yes"
print(s)

### FIXED CODE ###

n = int(input())
ans = "No"
for i in range(9):
    if n%(9-i)==0:
        if n/(9-i)<10:
            ans="Yes"
print(ans)
from operator import itemgetter

N, M = map(int,input().split())
A = sorted(list(map(int,input().split())))
Q = [list(map(int,input().split())) for _ in range(M)]
Q.sort(key=itemgetter(1), reverse=True)

idx = 0
flag = 0
for i in range(M):
    q = Q[i]
    B = q[0]
    C = q[1]
    for b in range(B):
        if A[idx] < C:
            A[idx] = C
            idx += 1
        else:
            flag = -1
    if flag == -1 or i == M-1:
        break
print(sum(A))


### FIXED CODE ###

from operator import itemgetter

N, M = map(int,input().split())
A = sorted(list(map(int,input().split())))
Q = [list(map(int,input().split())) for _ in range(M)]
Q.sort(key=itemgetter(1), reverse=True)

idx = 0
flag = 0
for i in range(M):
    q = Q[i]
    B = q[0]
    C = q[1]
    for b in range(B):
        if idx >= N:
            flag = -1
            break
        if A[idx] < C:
            A[idx] = C
            idx += 1
        else:
            flag = -1
    if flag == -1 or i == M-1:
        break
print(sum(A))
import sys


def input():
    return sys.stdin.readline()[:-1]

# N = int(input())
# A = [int(x) for x in input().split()]
# a, b, c = map(int, input().split())
# name1 = str(input())
# alph = {"A": 1, "B": 2, "C": 3, "D": 4, "E": 5}


a, b, c = map(int, input().split())
e,f,g = map(int, input().split())
if a==g and b==f and c==e:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline()[:-1]

# N = int(input())
# A = [int(x) for x in input().split()]
# a, b, c = map(int, input().split())
# name1 = str(input())
# alph = {"A": 1, "B": 2, "C": 3, "D": 4, "E": 5}


a=str(input())
b=str(input())

if a[0] == b[-1] and a[1] == b[-2] and a[2] == b[-3]:
    print("YES")
else:
    print("NO")
from fractions import gcd


def primes(N):
    p = [False, False] + [True] * (N - 1)
    for i in range(2, int(N ** 0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    return [i for i in range(N + 1) if p[i]]


def prime_factors(N):
    ret = []
    for p in primes(int(N ** 0.5) + 1):
        while N % p == 0:
            ret.append(p)
            N //= p
    if N > 1:
        ret.append(N)
    return ret


A, B = map(int, input().split())
g = gcd(A, B)
print(len(set(trial_division(g))) + 1)


### FIXED CODE ###

from fractions import gcd


def primes(N):
    p = [False, False] + [True] * (N - 1)
    for i in range(2, int(N ** 0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    ret = [i for i in range(N + 1) if p[i]]
    return ret


def trial_division(N):
    factors = []
    for p in primes(int(N ** 0.5)):
        while N % p == 0:
            factors.append(p)
            N //= p
    if N > 1:
        factors.append(N)
    return factors


A, B = map(int, input().split())
g = gcd(A, B)
print(len(set(trial_division(g))) + 1)