Harryxun/stf_run huggingface dataset:
N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for _ in range(1,N)]

query_list = [input().split() for _ in range(Q)]
query_list_int = [[int(k) for k in i]  for i in query_list]

val_list = [0 for _ in range(N)]
linkde_node_list = [[] for _ in range(N)]

#無向グラフのリンクを作成
for a, b in tree_list:
    linkde_node_list[int(a) -1].append(int(b) - 1)
    # linkde_node_list[int(b) -1].append(int(a) - 1)


for index, val in query_list_int:
    val_list[index-1] += val

def dfs(node_index, pairent_index):
    for child in linkde_node_list[node_index]:
        if child == pairent_index:
            continue

        val_list[child] += val_list[node_index]
        dfs(child, node_index)

    return val_list

res = dfs(0, -1) 
#0はルート、-1は親を持っていない事

print(*res)

### FIXED CODE ###

N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for j in range(1, N)]

query_list = [input().split() for k in range(Q)]
query_list_int = [[int(k) for k in i] for i in query_list]

val_list = [0 for _ in range(N)]

linked_node_list = [[] for _ in range(N)]

for a, b in tree_list:
    a, b = int(a)-1, int(b) -1
    linked_node_list[a].append(b)
    linked_node_list[b].append(a)


for index, val in query_list_int:
    val_list[index-1] += val

stack = [0]
parent = [0] * (N+1)

while True:
    v=stack.pop()
    for child in linked_node_list[v]:
        if child != parent[v]:
            parent[child] = v
            stack.append(child)
            val_list[child] += val_list[v]
    if not stack:
        break

print(*val_list)
import bisect


I = lambda: list(map(int, input().split()))
N = I()
A = I()
B = I()
C = I()
A.sort()
B.sort()
C.sort()

summ = 0
for ai in A:
    r = bisect.bisect_right(B, ai)
    for bi in B[r:]:
        rr = bisect.bisect_right(C, bi)
        summ += (N - r) * (N - rr)

print(summ)


### FIXED CODE ###

import bisect


I = lambda: map(int, input().split())
N = int(input())
A = list(I())
B = list(I())
C = list(I())
B.sort()
C.sort()

s = [0] * (N + 1)
for i, bi in enumerate(B):
    s[i + 1] = s[i] + N - bisect.bisect_right(C, bi)

print(sum(s[N] - s[bisect.bisect_right(B, ai)] for ai in A))
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

u=input().rstrip()
n=int(u)
u=list(u)
s=int(u[-1])
sm=0
for i in u:
    sm+=int(i)

import math
def judprime(x):
    y=math.sqrt(x)
    count=0
    for j in range(2,int(y)+1):
        if x%j==0:
            count+=1
    if count==0:
        return 1
    else:
        return 0
#print(judprime(7))
#print(judprime(42))
pri =[1,3,7,9]
if judprime(n)==1:
    print("Prime")
else:
    if s in pri and sm%3!=0:
        print("Prime")
        
    else:
        print("Not Prime")
 


    
    



    
    


    
    

### FIXED CODE ###

#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,m,que=MI()
lis=[[0]*n for i in range(n)]
for i in range(m):
    l,r=MI()
    lis[l-1][r-1]+=1
for i in range(n):
    lis[i]=list(accumulate(lis[i]))
#print(lis)
for i in range(que):
    p,q=MI()
    ans=0
    for i in range(p,q+1):
        if i==1:
            ans+=lis[i-1][q-1]
        else:
            ans+=lis[i-1][q-1]-lis[i-1][i-2]
    print(ans)
x,n= list(map(int, input().split()))
p = list(map(int, input().split())) 
import numpy as np

def getNearestValue(list, num):
    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return list[idx]
if x not in p:
    print(x)
else:
    t = [i for i in range(1,101)]
    for i in range(n):    
        t.remove(p[i])
#     print(t)
    print(getNearestValue(t, x))


### FIXED CODE ###

x,n= list(map(int, input().split()))
p = list(map(int, input().split())) 
import numpy as np

if x not in p:
    print(x)
else:
    t = [i for i in range(-101,201)]
    for i in range(n):    
        t.remove(p[i])
#         print(t)

    res = 100
    s = 1000
    for i in range(len(t)):
#         print(t[i])
        if s >= abs (x - t[len(t)-1-i]):
            s = abs (x - t[len(t)-1-i])
            res = t[len(t)-1-i]
    print(res)
import sys

def way(moku, wa, cur):
    if wa==moku:
        return 1
    if cur == n or wa > moku:
        return 0
    re1 = way(moku, wa + ms[cur], cur + 1)
    re2 = way(moku, wa, cur + 1)
    return re1 + re2

n = int(sys.stdin.readline())
ms = []
for i in range(n):
    ms += [int(sys.stdin.readline())]

total=sum(ms)
dp=[0]*(total+1)
dp[0]=1
for m in ms:
    for i in range(total,m-1,-1):
        dp[i]=dp[i]*2+dp[i-m]
    for i in range(m):
        dp[i]*=2
    print(m,dp)

border = (total + 1) // 2
yo=sum(dp[border:])*3
if total%2==0:
    yo-=way(total//2,0,0)*3
print((3**n-yo)%998244353)

### FIXED CODE ###

import numpy as np
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 998244353
    n = int(input())
    mx = 90005
    dp = np.zeros(mx, dtype="i8")
    dp2 = np.zeros(mx, dtype="i8")
    dp[0] = 1
    dp2[0] = 1
    sum_a = 0
    for _ in range(n):
        a = int(input())
        sum_a += a
        dp[mx - 1:a - 1:-1] = dp[mx - 1:a - 1:-1] * 2 + dp[mx - a - 1::-1]
        dp[:a] *= 2
        dp %= md
        dp2[mx - 1:a - 1:-1] += dp2[mx - a - 1::-1]
        dp2 %= md
    ng = np.sum(dp[(sum_a + 1) // 2:]) - np.sum(dp2[(sum_a + 1) // 2:]) * 2 + 1
    ng %= md
    total = (pow(3, n, md) - 3 * pow(2, n, md) + 3) % md
    print((total - ng * 3) % md)
    # ALL-NG（NG…最大辺が周の半分以上になる）で求める
    # 最大辺を赤として、dp[r] 赤の和がrのパターンを求める
    # 「赤だけ」、「赤と他一色だけ」(両方dp2に含まれる)のパターンは除く必要がある
    # 赤の和が総和の半分以上になるパターンを考えるので、
    # 赤以外の色だけになるパターンは除く必要がない
    # その後、緑、青が最大の辺になる場合も考えて3倍

main()
str = raw_input()
print "Yes" if((str[0] == str[1] and str[1] == str[2]) or (str[1] == str[2] and str[2] == str[3]))else "No


### FIXED CODE ###

str = raw_input()
print "Yes" if((str[0] == str[1] and str[1] == str[2]) or (str[1] == str[2] and str[2] == str[3]))else "No"
N=int(input())
List=list(map(int,input().split()))
a=0
for i in range (len(List)):
   a= a+(1/i)
print (1/a)

### FIXED CODE ###

N=int(input())
List=list(map(int,input().split()))
a=0
for i in range (len(List)):
   a+= 1/(List[i])
print(1/a)
#!/usr/bin/env python

def main():
    N, M, X = map(int, input().split())
    mat = [list(map(int, input().split())) for _ in range(N)]

    ans = 12 * (10 ** 5) +1
    for i in range(1<<N):
        tmp = [0] * (M+1)
        for j in range(N):
            if (i>>j)&1:
                tmp = [x+y for x, y in zip(tmp, mat[j])]
        if all(tmp[i] >= X for i in range(1, M):
                ans = min(ans, tmp[0])

    print('-1') if ans == 12 * (10 ** 5) +1 else print(ans)
            
if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python

def main():
    N, M, X = map(int, input().split())
    mat = [list(map(int, input().split())) for _ in range(N)]

    flag = False
    ans = 10 ** 18

    for i in range(1<<N):
        tmp = [0] * (M+1)
        mflag = True
        for j in range(N):
            if (i>>j)&1:
                tmp = [x+y for x, y in zip(tmp, mat[j])]
        for k in range(M):
            if tmp[1+k] < X:
                mflag = False
                break
        if mflag and tmp[0] < ans:
            ans = tmp[0]
            flag = True
    print(ans) if flag else print('-1')

if __name__ == '__main__':
    main()
N = int(input())
total = 0
for i in range(1,N + 1):
    if i % 3 == 0 or i % 5 == 0:
        continue
    t = t + i
print(total)

### FIXED CODE ###

N = int(input())
total = 0
for i in range(1,N + 1):
    if i % 3 == 0 or i % 5 == 0:
        continue
    total = total + i
print(total)
import fractions
import sys


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

if A == B:
    print(3)
    sys.exit()
	


def primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

###############################


gcd_ab = fractions.gcd(A,B)	


primes_ab = primes(gcd_ab)

# 1は必ずはいる
count = 1
for t in primes_ab:
    if A % t == 0 and B % t == 0:
        count += 1

print(count)




### FIXED CODE ###

import fractions


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


gcd_ab = fractions.gcd(A,B)	



def factorization(n):
    arr = 0
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr += 1

    if temp!=1:
        arr += 1

    return arr

f = factorization(gcd_ab)
print(f + 1)
import sympy

N=int(input())
count=0
if N==195:
    print(5)
elif N==189:
    print(4)
elif N==165:
    print(3)
elif N==135:
    print(2)
elif N==105:
    print(1)
else:
    print(0)


### FIXED CODE ###

N=int(input())
count=0
if N>=195:
    print(5)
elif N>=189:
    print(4)
elif N>=165:
    print(3)
elif N>=135:
    print(2)
elif N>=105:
    print(1)
else:
    print(0)
def c2(x):
    return x * (x - 1) // 2
 
 
n = int(input())
a = list(map(lambda i: int(i) - 1, input().split()))
b = list(a.count(i) for i in range(n))
# c = list(c2(b[i]) for i in range(n))
# d = list(c2(b[i] - 1) for i in range(n))
c = list(c2(i) for i in b)
d = list(c2(i - 1) for i in b)
 
s = sum(c)
# for k in range(n):
#     i = a[k]
#     ans = s - c[i] + d[i]
#     print(ans)
for i in a:
    print(s - c[i] + d[i])

### FIXED CODE ###

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


def c2(x):
    return x * (x - 1) // 2


print(c2(n) + c2(m))
today = input()
 
if today = "Sunny":
  tomorrow = "Cloudy"
elseif today = "Cloudy":
  tomorrow = "Rainy"
else:
  tomorrow = "Sunny"
 
print(tomorrow)

### FIXED CODE ###

today = input()
 
if today == "Sunny":
  tomorrow = "Cloudy"
elif today == "Cloudy":
  tomorrow = "Rainy"
else:
  tomorrow = "Sunny"
 
print(tomorrow)
n, k = list(map(int, input().split()))
s = input()
s[k-1] = s[k-1].upper()
print(s)

### FIXED CODE ###

n, k = list(map(int, input().split()))
s = list(input())
s[k-1] = s[k-1].lower()
print("".join(s))
a,b,c = map(int,input().split())
if 2*b = a+c:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

a,b,c = map(int,input().split())
if 2*b == a+c:
  print("YES")
else:
  print("NO")
import sys, os, time, math
import numpy as np
import pandas as pd

import sys, os, time, math
import numpy as np
import pandas as pd
 
 
# print("Start")
N = list(map(str, input().split()))
# N = np.array(list(map(int, input().split())))
# print(N, K)
# print(N)
 
if (N[0][0] == "7") or (N[0][1] == "7") or (N[0][2] == "7"):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = input()
# N = N[0]
# N = np.array(list(map(int, input().split())))
# print(N, K)
# print(N)
 
if (N[0] == "7") or (N[1] == "7") or (N[2] == "7"):
    print("Yes")
else:
    print("No")
a, op,  b = map(int, input().split())
if op =="+":
    print(a+b)
else:
    print(a-b)

### FIXED CODE ###


a, op,  b = map(str, input().split())
if op =="+":
    print(int(a)+int(b))
else:
    print(int(a)-int(b))
INF = 1<<31
n = input()
l = [input() for i in range(n-1)]
dp = [[INF]*2 for i in range(n+1)]
dp[1][0] = 0
for i in range(1,n):
    for j in range(i+1,0,-1):
        dp[j][1] = min(dp[j][1], dp[j][0]+l[i-1])
        dp[j][0] = min(dp[j-1][0], dp[j-1][1]+l[i-1])
print min(dp[n/2])

### FIXED CODE ###

INF = 1<<31
n = input()
dp = [[[INF]*2 for _ in xrange(n/2+2)] for _ in range(2)]
dp[1][1][0] = dp[1][0][1] = 0
for i in range(2,n+1):
    x = i % 2
    s = input()
    t = min(i,n/2)
    for j in range(1,t+1):
        dp[x][j][0] = min(dp[1-x][j-1][0], dp[1-x][j-1][1] + s)
        dp[x][j][1] = min(dp[1-x][j][0] + s, dp[1-x][j][1])
print min(dp[0][n/2])
n=int(input())
s=list(map(str,input().split()))
li=[0]*n
ans=0
for i in range(0,n):
  li[i]=''.join(sorted(s[i]))
  
for j in range(0,n-1):
  for k in range(j+1,n):
    if li[j]==li[k]:
      ans+=1
    else:
      ans+=0
      
print(ans)      


### FIXED CODE ###

n=int(input())
dic={}
for _ in range(0,n):
  s="".join(sorted(input()))
  if s in dic:
    dic[s]+=1
  else:
    dic[s]=1
    
ans=0    
for a in dic.values():
  ans+=(a*(a-1))/2
  
print(int(ans))
a,b=input(),input()
print a*b,a*2+b*2

### FIXED CODE ###

a,b=map(int,raw_input().split())
print a*b,a*2+b*2
n,m=map(int,input().split( ))
line=list(map(int,input().split( )))s


L=[]
R=[]
for i in range(m):
    l,r=map(int,input().split( ))
    L.append(l)
    R.append(r)

print(max(min(R)-max(L)+1,0)



### FIXED CODE ###

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

L=[]
R=[]
for i in range(m):
    l,r=map(int,input().split( ))
    L.append(l)
    R.append(r)

print(max(min(R)-max(L)+1,0))
s = list(input())
k = int(input())
num = len(s)
for i in range(num):
    a = 122-ord(s[i])+1
    if a <= k:
        k -= a
        s[i] = 'a'
if k > 0:
    s[-1] = chr(ord(s[-1])+k)
print(*s, sep='')
        


### FIXED CODE ###

s = list(input())
k = int(input())
num = len(s)

for i in range(num):
    a = 122-ord(s[i])+1
    if a <= k and s[i] != 'a':
        k -= a
        s[i] = 'a'
if k > 0:
    s[-1] = chr(ord(s[-1])+k%26)
print(*s, sep='')
n = int(input())
A = [ int(input()) for i in range(n) ]
c = 0
temp = 1
s = {1}
while temp not in s:
  temp = A[temp-1]
  c += 1
  i temp == 2:
    print(c)
    exit()
  s.add(temp)
print(-1)

  

### FIXED CODE ###

n = int(input())
A = [ int(input()) for i in range(n) ]
c = 0
temp = 1
s = set()
while temp not in s:
  s.add(temp)
  temp = A[temp-1]
  c += 1
  if temp == 2:
    print(c)
    exit()
print(-1)
tmp = input()
tmp = tmp.split(" ")
x,y = map(int,tmp)
if x == y:
	print("a == b")

elif x > y:
	print("a > b")

else:
	print("a < b")

### FIXED CODE ###

tmp = input()
tmp = tmp.split(" ")
tmp = list(map(int,tmp))
if tmp[0] < tmp[1] and tmp[1] < tmp[2]:
	print("Yes")

else :
	print("No")
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
MOD = 10**9 + 7
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###


N = ii()

print('1' + ''.join(['0'] * (N-1)))




### FIXED CODE ###

###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
MOD = 10**9 + 7
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###


X = ii()

for t in range(1, 1000000):
  if (t**2 + t) // 2 >= X:
    print(t)
    exit()
s = input().split()

n = int(s[0])
m = int(s[1])

ld = {}
root = []

for i in range(m):
    t = input().split()
    if int(t[0]) in ld:
       ld[int(t[0])].add(int(t[1]))
    else:
       ld[int(t[0])] = {int(t[1])}
    if int(t[1]) in ld:
        ld[int(t[1])].add(int(t[0]))
    else:
        ld[int(t[1])] = {int(t[0])}
    root.append({int(t[0]),int(t[1])})


if sum(ld.keys()) < int(((n + 1) * n ) / 2):
    print("No")
else:
    goal = [1]
    result = {}

    for i in range(n):
        count = 0
        for j in range(m-len(goal)):
            if goal[i] in root[j-count]:
                result[int(list(root[j-count] - {goal[i]})[0])] = goal[i]
                goal.append(int(list(root[j-count] - {goal[i]})[0]))
                #print(root[j-count])
                del root[j-count]
                count += 1
        if len(goal) >= n:
            break

    print("Yes")
    for i in range(2,n+1):
        print(result[i])

    #print(goal)
    #print(result)


### FIXED CODE ###

import collections

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

coriddorList = [set() for i in range(n+1)]
deepList = [-1 for i in range(n+1)]


for i in range(m):
    a,b = list(map(int,input().split()))
    coriddorList[a].add(b)
    coriddorList[b].add(a)

checkList = [0] * (n + 1)
ansList = [0] * (n + 1)
checkList[1] = 1
q = collections.deque()
q.appendleft(1)

while len(q) > 0:
    value = q.pop()
    for k in coriddorList[value]:
        if checkList[k] == 0:
            checkList[k] = 1
            ansList[k] = value
            q.appendleft(k)

print("Yes")
for i in range(2,n+1):
    print(ansList[i])
N = int(input())
S = input()

if N%2 == 0:
    jdg_1 = S[0:N/2]
    jdg_2 = S[N/2:N]
    if jdg_1==jdg_2:
      out = 'Yes'
    else:
      out = 'No'
else:
  out = 'No'

print(out)

### FIXED CODE ###

N = int(input())
S = input()

if N%2 == 0:
    jdg_1 = S[0:int(N/2)]
    jdg_2 = S[int(N/2):int(N)]
    if jdg_1==jdg_2:
      out = 'Yes'
    else:
      out = 'No'
else:
  out = 'No'

print(out)
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

# N, M, X = list(map(int, sys.stdin.readline().split()))
# A = np.array(list(map(int, sys.stdin.readline().split())))
#
# print(min(len(A[A > X]), len(A[A<X])))

A, B, K = list(map(int, sys.stdin.readline().split()))

arr = list(range(A, B + 1))

print('\n'.join(map(str, list(sorted(set(arr[:K] + arr[-K:]))))))


### FIXED CODE ###

import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

# N, M, X = list(map(int, sys.stdin.readline().split()))
# A = np.array(list(map(int, sys.stdin.readline().split())))
#
# print(min(len(A[A > X]), len(A[A<X])))

A, B, K = list(map(int, sys.stdin.readline().split()))

a = list(range(A, min(B, A + K)))
b = list(range(max(A, B - K + 1), B + 1))



print('\n'.join(map(str, list(sorted(set(a + b))))))
#D - Grid Repainting
#最短距離のルートを記録してあとはすべて黒く塗る
import copy
import sys
from collections import deque]
#幅優先のロジックを作成する
H,W = (int(i) for i in input().split())
s_tmp = []
for _ in range(H):
    s_tmp.append(list(input()))
d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
q = deque()
q_old = deque()
s = copy.deepcopy(s_tmp)
q.append([0,0,0])
s[H-1][W-1] = 'g'
s[0][0] = 's'
flg = False
while len(q) > 0:
    #print(q)
    node = q.popleft()#qから左端を取り出す(幅優先)
    if node is not None:
        y = node[0]
        x = node[1]
        z = node[2]
        s[y][x] = '#'
        #上下を探索して移動できるところをスタックする
        for dx, dy in d:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < W and 0 <= ny < H) or s[ny][nx] == '#':
                continue
            else:
                tmp = [ny,nx,z+1]
                if s[ny][nx] != 'y':
                    q.append(tmp)
                if s[ny][nx] == 'g' and flg == False:
                    print(z+1)
                    flg = True
                    sys.exit()
                s[ny][nx] = 'y'
cnt = 0
for j in range(W):
    for i in range(H):
        if s_tmp[i][j] =='.':
            cnt += 1
if flg == False:
    print(-1)
else :
    print(cnt-z-2)

### FIXED CODE ###

#D - Grid Repainting
#最短距離のルートを記録してあとはすべて黒く塗る
import copy
import sys
from collections import deque
#幅優先のロジックを作成する
H,W = (int(i) for i in input().split())
s_tmp = []
for _ in range(H):
    s_tmp.append(list(input()))
d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
q = deque()
s = copy.deepcopy(s_tmp)
q.append([0,0,0])
s[H-1][W-1] = 'g'
s[0][0] = 's'
flg = False

def result():
    cnt = 0
    for j in range(W):
        for i in range(H):
            if s_tmp[i][j] =='.':
                cnt += 1
    if flg == False:
        print(-1)
    else :
        print(cnt-z-2)
        
while len(q) > 0:
    #print(q)
    node = q.popleft()#qから左端を取り出す(幅優先)
    if node is not None:
        y = node[0]
        x = node[1]
        z = node[2]
        s[y][x] = '#'
        #上下を探索して移動できるところをスタックする
        for dx, dy in d:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < W and 0 <= ny < H) or s[ny][nx] == '#':
                continue
            else:
                tmp = [ny,nx,z+1]
                if s[ny][nx] != 'y':
                    q.append(tmp)
                if s[ny][nx] == 'g' and flg == False:
                    #print(z+1)
                    flg = True
                    result()
                    sys.exit()
                s[ny][nx] = 'y'
if flg == False:
        print(-1)
s = list(map(int,input().split()))
cnt=0
for i in range(3):
    if s[i]==1:
        cnt+=1
print(cnt)

### FIXED CODE ###

S = input()
cnt = 0
for i in range(3):
    if S[i] == "1":
        cnt += 1
print(cnt)
#coding:utf-8
import math

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

A = [int(y) for y in input().split()]

Ma = max(A)
mi = 0

ans = Ma

def execute(f):
    count = 0
    for i in A:
        count += (i - 0.01) // f
    if count <= K:
        return True
    else:
        return False

while True:
    median = (Ma + mi) // 2
    
    bobo = execute(median)
    
    if bobo:
        ans = min(ans,median)
        Ma = median
    else:
        mi = median + 1
    
    if Ma == mi:
        break

print("{}".format(ans))

### FIXED CODE ###

#coding:utf-8
import math

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

A = [int(y) for y in input().split()]

Ma = max(A)
mi = 1

ans = Ma

def execute(f):
    count = 0
    for i in A:
        count += math.ceil(i / f) - 1
    if count <= K:
        return True
    else:
        return False

while True:
    median = (Ma + mi) // 2
    
    bobo = execute(median)
    
    if bobo:
        ans = min(ans,median)
        Ma = median
    else:
        mi = median + 1
    
    if Ma == mi:
        break

print("{}".format(ans))
import math

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

myans = (A * B) // math.gcd(A, B)


print(myans)

### FIXED CODE ###

import fractions

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

myans = (A * B) // fractions.gcd(A, B)


print(myans)