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

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


memo = {}

def countbit(x):
    i = 0
    cnt = 0
    while x >= 1<<i:
        if x & (1<<i):
            cnt += 1
        i += 1
    return cnt


def count(x, c):
    s = 1
    x = x % c
    while x != 0:
        s += 1
        x = x % countbit(x)
    return s

def main():
    n = int(input())
    x = int(input(), 2)
    c = countbit(x)
    for i in range(n):
        y = x ^ (1<<(n-i-1))
        cc = (x >> (n-i-1)) & 1
        s = count(y, c - 1 if cc else c + 1)
        print(s)


main()


### FIXED CODE ###

from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


memo = {}

def countbit(x):
    i = 0
    cnt = 0
    while x >= 1<<i:
        if x & (1<<i):
            cnt += 1
        i += 1
    return cnt


def count(x):
    # if c == 0:
    #     return 0
    # s = 1
    # x = x % c
    s = 0
    while x != 0:
        s += 1
        x = x % countbit(x)
    return s

def main():
    n = int(input())
    xs = list(input())
    c = len([i for i in xs if i == '1'])
    dp = {}
    dps = {}
    for i in range(-1, 2):
        cc = c + i
        if cc == 0:
            continue
        dp[cc] = [-1] * n
        base = 1 % cc
        dpstmp = 0
        for i in range(n):
            dp[cc][i] = base
            if xs[-i-1] == '1':
                dpstmp += base
            base = base * 2 % cc
        dps[cc] = dpstmp % cc

    for i in range(n):
        cc = c
        if xs[i] == '1':
            cc -= 1
        else:
            cc += 1
        if cc == 0:
            print(0)
            continue
        res = dps[cc]
        if xs[i] == '1':
            res = (res - dp[cc][-i-1]) % cc
        else:
            res = (res + dp[cc][-i-1]) % cc
        s = count(res) + 1
        print(s)


main()
line = map(int, input().split())
line.sort()

print(line[0] + line[1])


### FIXED CODE ###

line = list(map(int,input().split()))
line.sort()

print(line[0] + line[1])
N = int(input())
INF = 10**6
dp = [INF] * (max(9, N)+1)
for i in range(10):
  if  0 < i < 6:
    dp[i] = i
  elif i < 9:
    dp[i] = i%6+1
  else:
    dp[i] = 1
for i in range(N):
  n = m = 1
  for j in range(1, 6):
    dp[i+j] = min(dp[i+j], dp[i] + j)
  while i+9**n <= N:
    dp[i+9**n] = min(dp[i+9**n], dp[i] + 1)
    n += 1
  while i+6**m <= N:
    dp[i+6**m] = min(dp[i+6**m], dp[i] + 1)
    m += 1
print(dp[N])


### FIXED CODE ###

N = int(input())
INF = 10**6
dp = [INF] * (max(9, N)+1)
dp[0] = 0
for i in range(N):
  n = m = 0
  while i+9**n <= N:
    dp[i+9**n] = min(dp[i+9**n], dp[i] + 1)
    n += 1
  while i+6**m <= N:
    dp[i+6**m] = min(dp[i+6**m], dp[i] + 1)
    m += 1
print(dp[N])
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
ans=L
L=N*M//gcd(N,M)

U=[]
V=[]

#1個目
for i in range(N):
  U.append( [i*(L//N),S[i]])
#2個目
for i in range(M):
  V.append( [i*(L//M),T[i]])
#print(U)
#print(V)
for i in U:
  for j in V:
    if i[0]==j[0] and i[0]!=j[1]:
      print(-1(
      exit


#  U[i*(L//N)]=S[i]
#  if U[j*(L//M)]!="#" and U[j*(L//M)]!=T[j]:
print(ans)

### FIXED CODE ###

from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
L=N*M//gcd(N,M)
p=[]
q=[]

if S[::L//M]==T[::L//N]:
  print(L)
else:
  print(-1)
x = list(map(int, input().split()))

ans_ind = 0
for i in range(5):
    if x[i] == 0:
        ans_ind = i + 1

print(ans_ind)

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

ans_ind = 0
for i in range(5):
    if x[i] == 0:
        ans_ind = i + 1

print(ans_ind)



### FIXED CODE ###

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

ans_ind = 0
for i in range(5):
    if x[i] == 0:
        ans_ind = i + 1

print(ans_ind)
from math import log2,floor
N = int(input())
A = list(map(int,input().split()))
L = max([floor(log2(x)) for x in A])+1
bits = [0]*L
for x in A:
    for i in range(L):
        if (x>>i)&1:
            bits[i] += 1
mod = 10**9+7
ans = 0
for i in range(L):
    b = bits[i]
    ans = (ans+b*(N-b)*(2**i))%mod
print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
 
mod = 10**9 + 7
 
def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))
 
def main():
    n = ni()
    a = na()
    ans = 0
    for i in range(61):
        cnt = 0
        for ai in a:
            if (ai >> i) & 1:
                cnt += 1
        ans += ((cnt * (n - cnt)) * 2**i) % mod
    ans %= mod
    print(ans)
 
 
if __name__ == "__main__":
    main()
i=input()
i.splitlines()
ls=list(range(1,3))
ls.remove(i[0])
ls.remove(i[1])
print(ls.pop())

### FIXED CODE ###

i=int(input())
j=int(input())
a=6-(i+j)
print(str(a))
n, y = map(int, input().split())
s = min(n, y // 10000)
t = min(n, y // 5000)
u = min(n, y // 1000)

ans =[-1, -1, -1]
for i in range(s, -1, -1):
    for j in range(t, -1, -1):
        for u in range(u, -1, -1):
            if i * 10000 + j * 5000 + k * 1000 == y and i + j + k == n:
                ans = [i, j, k]
                break
print(' '.join(map(str, ans)))

### FIXED CODE ###

n, y = map(int, input().split())
 
ans =[-1, -1, -1]
for i in range(n + 1):
    for j in range(n + 1 - i):
            if i * 10000 + j * 5000 + (n - i - j) * 1000 == y:
                ans = [i, j, n - i - j]
                break
print(' '.join(map(str, ans)))
import fractions
N = int(input())
A = list(map(int, input().split()))
AB = 1
for i in A:
    AB = AB*i//fractions.gcd(AB,i)
sumB = 0
for i in A:
    sumB += AB/i
print(int(sumB%(10**9+7)))

### FIXED CODE ###

import fractions
N = int(input())
A = list(map(int, input().split()))
AB = 1
for i in A:
    AB = AB*i//fractions.gcd(AB,i)
sumB = 0
for i in A:
    sumB += AB//i
print(int(sumB%(10**9+7)))
a=int(input())
if a==2:
  print(a)
else:
  sosuu=1
  a=a-1
  while sosuu==1:
    a+=1
    b=2
    while a!=b:
      sosuu=0
      if a%b==0:
        sosuu=1//割り切れた
        break
      else:
        b+=1
  print(a)

### FIXED CODE ###

a=int(input())
if a==2:
  print(a)
else:
  sosuu=1
  a=a-1
  while sosuu==1:
    a+=1
    b=2
    while a!=b:
      if a%b==0:
        sosuu=1
        break
      else:
        b+=1
        sosuu=0
  print(a)
S = input()
ans = True
for i in range(0,len(S),2):
  if S[i] != "h" or S[i+1] != "i":
    ans = False
    break
if ans:
  print("Yes")
else:
  print("No")
 

### FIXED CODE ###

S = input()
ans = True
for i in range(0,len(S)-1,2):
  if S[i] != "h" or S[i+1] != "i":
    ans = False
    break
if not ans or len(S)%2 == 1:
  print("No")
else:
  print("Yes")
from math import floor
from decimal import Decimal

S = int(input())

if S[2] == S[3] and S[4] === S[5]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from math import floor
from decimal import Decimal

S = input()

if S[2] == S[3] and S[4] == S[5]:
    print("Yes")
else:
    print("No")
#coding utf-8

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

x = [a*b, a/b, a+b, a-b]

print(max(x))


### FIXED CODE ###

#coding utf-8

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

x = [a*b, a+b, a-b]

print(max(x))
import fractions
n = int(input())
A = list(map(int, input().split()))
work = A[0]
for i in range(1, N):
    work = fractions.gcd(work, A[i])
print(work)

### FIXED CODE ###

import fractions
n = int(input())
A = list(map(int, input().split()))
work = A[0]
for i in range(1, n):
    work = fractions.gcd(work, A[i])
print(work)
n=int(input())
ai = list(map(int,input().split()))
sum = 0
i=0
k=1
while i<n-1:
    while k<n-i:
    sum += ai[i]*ai[i+k]
    k++
  i++
sum %= 1000000007
print(sum)

### FIXED CODE ###

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

for i in range(N):
    ans += A[i]*A[i]
last += sum(A)*sum(A)
last -= ans
last //= 2
print(last % 1000000007)
N, H = map(int,input().split())
L = []
maxi = 0
for _ in range(N):
    a,b = map(int,input().split())
    maxi = max(maxi, a)
    L.append(b)
from itertools import accumulate
accumulated =  list(accumulate(\
    sorted([x for x in L if x > maxi],reverse=True) ))
from bisect import bisect_right
from math import ceil
if H - accumulated[-1]  > 0 :
    print(ceil((H - accumulated[-1]) / maxi) + len(accumulated))
else:
    index = bisect_right(accumulated,H)
    print(index)
    


### FIXED CODE ###

N, H = map(int,input().split())
L = []
maxi = 0
for _ in range(N):
    a,b = map(int,input().split())
    maxi = max(maxi, a)
    L.append((a,b))
cand = []
throw = 0
cnt = 0
for l in L:
    if maxi <  l[1]:
        throw += l[1]
        cand.append(l[1])
        cnt += 1
import math
if H - throw > 0: 
    print(math.ceil((H - throw)/maxi) + cnt )
else:
    throw = 0
    cnt = 0
    cand.sort()
    for x in cand[::-1]:
        throw += x
        cnt += 1
        if throw >= H:
            print(cnt)
            quit()
n, k = map(int, input().split())
a = (list)(map(int, input().split()))

# print(-(-(n-1)//(k-1)))
print((n + (k - 1)) / k


### FIXED CODE ###

from functools import reduce
n = (int)(input())
a = (list)(map(int, input().split()))


def gcd(a, b):
    # a>b
  while(b):
    c = a % b
    a = b
    b = c
  return a


def calcMod(a, m):
  return sum([m % v for v in a])


def lcm(a, b):
  return a*b/gcd(a, b)


def lcm_list(l):
  g = reduce(lcm, l)
  return g


def mul(a, b):
  return a*b


#print(calcMod(a, (int)(lcm_list(a)-1)))
print(calcMod(a, reduce(mul, a)-1))
H,W = list(map(lambda x:int(x),input().split("")))
if H*W%2==0:
  ans=H*W/2
else:
  ans=(H*W+1)/2

print(ans)

### FIXED CODE ###

H,W = list(map(lambda x:int(x),input().split(" ")))
if H==1 or W==1:
  ans=1
elif H*W%2==0:
  ans=H*W/2
else:
  ans=(H*W+1)/2

print(int(ans))
n,m=map(int, input().split())
a_list=[]
b_list=[]
for i in range(n):
  a,b=map(int, input().split())
  a_list.append(a)
  b_list.append(b)
c_list=[]
d_list=[]
for i in range(m):
  c,d=map(int, input().split())
  c_list.append(c)
  d_list.append(d)
for i in range(n):
  min=0
  min_number=0
  for j in range(m):
    d=abs(a[i]-c[j])+abs(b[i]-d[j])
    if d<min:
      min=d
      min_number=j
  print(min_number)

### FIXED CODE ###

n,m=map(int, input().split())
a_list=[]
b_list=[]
for i in range(n):
  a,b=map(int, input().split())
  a_list.append(a)
  b_list.append(b)
c_list=[]
d_list=[]
for i in range(m):
  c,d=map(int, input().split())
  c_list.append(c)
  d_list.append(d)
for i in range(n):
  min=2*(10**8)
  min_number=0
  for j in range(m):
    d=abs(a_list[i]-c_list[j])+abs(b_list[i]-d_list[j])
    if d<min:
      min=d
      min_number=j
  print(min_number+1)
N = int(input())
an = list(map(int, input()))

cost = 10000
ans = 10000
for i in range(-100,100+1):
    cost = sum([(j - i)**2 for j in range(1, N+1)])
    ans = min(ans, cost)

print(ans)

### FIXED CODE ###

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

cost = 10000*N
ans = 10000*N
for i in range(-100,100+1):
    cost = sum([(j - i)**2 for j in an])
    ans = min(ans, cost)

print(ans)
a,b,c=map(int,input().split())
print(min(a*b,c)

### FIXED CODE ###

a,b,c=map(int,input().split())
print(min(a*b,c))
if __name__ == '__main__':
	N, M=map(int, input().split())
	a=[]
	b=[]
	for i in range(M):
		x,y=[int(i) for i in input().split()]
		a.append(x)
		b.append(y)
		n=[]
		for j in range(N):
			n.append(0)

	for i in range(N):
		n[a[i]-1]+=1
		n[b[i]-1]+=1

	flag = 0
	for i in range(N):
		if(n[i]%2==1):
			flag +=1

	if(flag<2):
		print('YES')
	else:
		print('NO')

### FIXED CODE ###

if __name__ == '__main__':
	N, M=map(int, input().split())

	n=[]
	for j in range(N):
		n.append(0)

	for i in range(M):
		a,b=[int(i) for i in input().split()]
		n[a-1]+=1
		n[b-1]+=1

	flag = 0
	for i in range(N):
		if(n[i]%2==1):
			flag +=1

	if(flag<2):
		print('YES')
	else:
		print('NO')
n, m = list(map(int, input().split()))
a = []
for i in range(m):
	a.append(int(input()))
a.sort()
f0 = 1
if a[0] == 1:
	f1 = 0
else:
	f1 = 1
k = 0
for i in range(2, n + 1):
	while k < len(a) and a[k] < i:
		k += 1
	if k == len(a) or a[k] != i:
		f = (f0 + f1) % 1000000007
	else:
		f = 0
	f0 = f1
	f1 = f
	if f0 == f1 == 0:
		break
print(f1)

### FIXED CODE ###

n, m = list(map(int, input().split()))
a = []
for i in range(m):
	a.append(int(input()))
a.sort()
f0 = 1
if len(a) > 0 and a[0] == 1:
	f1 = 0
else:
	f1 = 1
k = 0
for i in range(2, n + 1):
	while k < len(a) and a[k] < i:
		k += 1
	if k == len(a) or a[k] != i:
		f = (f0 + f1) % 1000000007
	else:
		f = 0
	f0 = f1
	f1 = f
	if f0 == f1 == 0:
		break
print(f1)
f = open("input.txt", "r")
a, b, c, d = list(map(int, f.readline().split()))

if b <= 0 and d <= 0:
    print(a*c)
elif b < 0 and d >= 0:
    print(max(c, 1)*b)
elif b >= 0 and d < 0:
    print(max(a, 1)*d)
else:
    print(b*d)

### FIXED CODE ###

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

ans = []

if b <= 0 and d <= 0:
    ans.append(a*c)
if b < 0 and d >= 0:
    ans.append(max(c,1)*b)
if b >= 0 and d < 0:
    ans.append(max(a,1)*d)

ans.append(max(b*d, a*c))

print(max(ans))
import queue


def up(y, x, d):
    return y-1, x, d


def down(y, x, d):
    return y+1, x, d


def left(y, x, d):
    return y, x-1, d


def right(y, x, d):
    return y, x+1, d


def put_all(q, y, x, d):
    q.put((up(y, x, d)))
    q.put((down(y, x, d)))
    q.put((left(y, x, d)))
    q.put((right(y, x, d)))
    return


def put_not_all(q, y, x, d, distances):
    if distances[y-1][x] != -1:
        q.put((y-1, x, d))
    if distances[y+1][x] != -1:
        q.put((y+1, x, d))
    if distances[y][x-1] != -1:
        q.put((y, x-1, d))
    if distances[y][x+1] != -1:
        q.put((y, x+1, d))


def solve(maze, init_y, init_x, distances, H, W):
    if maze[init_y][init_x] == "#":
        return 0

    distances[init_y][init_x] = 0

    q = queue.Queue()
    put_all(q, init_y, init_x, 1)

    farthest = [0, init_y, init_x]
    while not q.empty():
        y, x, d = q.get()
        # print(x, y)
        if x < 0 or x >= W or y < 0 or y >= H:
            # print("continue")
            continue
        if maze[y][x] == "#":
            distances[y][x] = 0
            continue
        distance = distances[y][x]
        if distance == -1:
            distances[y][x] = d
            put_all(q, y, x, d+1)
            if d > farthest[0]:
                farthest = [d, y, x]

    return farthest


def main():
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    flag = False
    y = 0
    x = 0
    for i in range(H):
        for j in range(W):
            initial_map = [[-1 for _ in range(W)] for _ in range(H)]
            distance, y, x = solve(maze, i, j, initial_map, H, W)
            if distance > 0:
                flag = True
                break
        if flag:
            break
    initial_map = [[-1 for _ in range(W)] for _ in range(H)]
    max_distance, y, x = solve(maze, x, y, initial_map, H, W)

    print(max_distance)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def d_maze_master(INF=float('inf')):
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Maze = [list(input()) for _ in range(H)]

    def bfs(start_row, start_col):
        diff = ((-1, 0), (0, 1), (1, 0), (0, -1))

        def is_inside(row, col):
            return 0 <= row < H and 0 <= col < W

        queue = deque([(start_row, start_col)])
        dist = [[INF for _ in range(W)] for _ in range(H)]
        dist[start_row][start_col] = 0
        while queue:
            row, col = queue.pop()
            for dr, dc in diff:
                nr, nc = row + dr, col + dc
                if is_inside(nr, nc) and Maze[nr][nc] != '#' and dist[nr][nc] == INF:
                    queue.appendleft((nr, nc))
                    dist[nr][nc] = dist[row][col] + 1
        return dist

    ans = 0
    for start_row in range(H):
        for start_col in range(W):
            if Maze[start_row][start_col] == '#':
                continue
            dist = bfs(start_row, start_col)
            for row in range(H):
                for col in range(W):
                    if Maze[row][col] != '#':
                        ans = max(ans, dist[row][col])
    return ans

print(d_maze_master())
# E - Colorful Blocks
MOD = 998244353
N,M,K = map(int,input().split())
inv_M = pow(M-1,-1,MOD)
ans = 0
tmp = pow(M-1,N-1,MOD)
comb = 1
for i in range(K+1):
    ans = (ans+M*comb*tmp)%MOD
    if i==K:
        break
    tmp = (tmp*inv_M)%MOD
    comb = (comb*(N-1-i)*pow(i+1,-1,MOD))%MOD
print(ans)

### FIXED CODE ###

# E - Colorful Blocks
import sys
sys.setrecursionlimit(10**8)

MOD = 998244353
N,M,K = map(int,input().split())
inv_M = pow(M-1,-1,MOD) if M>1 else 0
ans = 0
tmp = pow(M-1,N-1,MOD) if M>1 else 0
comb = 1
for i in range(K+1):
    ans = (ans+M*comb*tmp)%MOD
    if i==K:
        break
    tmp = (tmp*inv_M)%MOD
    comb = (comb*(N-1-i)*pow(i+1,-1,MOD))%MOD
if M==1 and K==N-1:
    ans += 1
print(ans)
s=input()
if len(s)<6:
  print("No")
else:
  if s[2]==s[3] and s[4]==s[5]:
    print("Yes")
    else:
      print("No")

### FIXED CODE ###

s=input()
if len(s)<6:
    print("No")
else:
    if s[2]==s[3] and s[4]==s[5]:
        print("Yes")
    else:
        print("No")
a = int(input())
print(a > 29 and 'Yes' or 'No)

### FIXED CODE ###

a = int(input())
res = a > 29 and 'Yes' or 'No'
print(res)
N = int(input())

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

dp = {}

for i in range(N):
    for j in range(min(X), max(X)):
        if j in dp:
            dp[j] += (X[i] - j)**2
        else:
            dp[j] = (X[i] - j)**2

print(min(dp.values()))



### FIXED CODE ###

N = int(input())

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

dp = {}

for i in range(N):
    for j in range(min(X), max(X)+1):
        if j in dp:
            dp[j] += (X[i] - j)*(X[i] - j)
        else:
            dp[j] = (X[i] - j)*(X[i] - j)

print(min(dp.values()))
s = str(input())
ans = ['YYMM','MMYY','AMBIGUOUS','NA']
#print(s[:2],s[-2:])
if 0<int(s[:2])<=12 and 0<int(s[-2:])<=12:
    print(ans[3])
elif 0<int(s[:2])<=12:
    print(ans[2])
elif 0<int(s[-2:])<=12:
    print(ans[1])
else:
    print(ans[4])
    

### FIXED CODE ###

s = str(input())
ans = ['YYMM','MMYY','AMBIGUOUS','NA']
#print(s[:2],s[-2:])
if (0==int(s[:2]) or 13<=int(s[:2])) and (0==int(s[-2:]) or 13<=int(s[-2:])):
    print(ans[3])
if 0<int(s[:2])<=12 and 0<int(s[-2:])<=12:
    print(ans[2])
elif 0<int(s[:2])<=12:
    print(ans[1])
elif 0<int(s[-2:])<=12:
    print(ans[0])
import sys
# sys.setrecursionlimit(200005)

# はぁー・・

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, q = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    a, b = na()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

ps = [0] * n
for i in range(q):
    p, x = na()
    p -= 1
    ps[p] += x

ans = [0] * n

def dfs(cur, pre, g, curv):
    global ps, ans
    curv += ps[cur]
    ans[cur] = curv
    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, curv)

dfs(0, -1, g, 0)

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


### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, q = na()
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = na()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

ps = [0] * n
for i in range(q):
    p, x = na()
    p -= 1
    ps[p] += x

stack = [0] * (n+1)
inds = [0] * (n+1)

sp = 0
stack[sp] = 0
sp += 1

while sp > 0:
    cur = stack[sp-1]
    if inds[sp-1] == len(g[cur]):
        sp -= 1
        continue
    if inds[sp-1] == 0 and sp > 1:
        ps[cur] += ps[stack[sp-2]]
    if sp == 1 or stack[sp-2] != g[cur][inds[sp-1]]:
        stack[sp] = g[cur][inds[sp-1]]
        inds[sp] = 0
        inds[sp-1] += 1
        sp += 1
        continue
    inds[sp - 1] += 1

print(" ".join(map(str, ps)))
import math

N = int(input())
print(math.factorial(N) % MOD)

### FIXED CODE ###

N = int(input())

print(800 * N - (N // 15) * 200)
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(20000000)
n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

nums = [deque() for _ in range(3)]
# 0-2: amari
for i in range(1, n+1):
    nums[i%3].append(i)

ans = [0 for _ in range(n)]
def dfs(step, idx, pre_2, pre_1):
    pre_2_mod = pre_2 % 3
    if pre_2 == -1:
        for i in [1, 2, 0]:
            if len(nums[i]) > 0:
                out = nums[i].pop()
                break
    else:
        if pre_2_mod != 0:
            if len(nums[3 - (pre_2_mod)]) > 0:
                out = nums[3 - (pre_2_mod)].pop()
            else:
                if len(nums[0]) > 0:
                    out = nums[0].pop()
                else:
                    print(-1)
                    exit()
        else:
            if len(nums[1]) > len(nums[2]):
                out = nums[1].pop()
            else:
                out = nums[2].pop()
    ans[idx-1] = out
    for k in edges[idx].keys():
        if ans[k-1] == 0:
            dfs(step+1, k, pre_1, out)

dfs(1, 1, -1, -1)
print(" ".join(list(map(str, ans))))



### FIXED CODE ###

from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

nums = [deque() for _ in range(3)]
for i in range(1, n+1):
    nums[i%3].append(i)

color = [-1 for _ in range(n)]
cnts = [0 for _ in range(2)]
def coloring(num, pre_color):
    if pre_color:
        col = 0
    else:
        col = 1
    color[num-1] = col
    cnts[col] += 1
    for k in edges[num].keys():
        if color[k-1] == -1:
            coloring(k, col)

coloring(1, 1)

ans = [0 for _ in range(n)]
def solve(v):
    for i in range(n):
        if color[i] == v:
            ans[i] = nums[0].pop()
        else:
            for j in [1, 2, 0]:
                if len(nums[j]) > 0:
                    ans[i] = nums[j].pop()
                    break

if cnts[0] <= n // 3:
    # print("A")
    solve(0)
elif cnts[1] <= n // 3:
    # print("B")
    solve(1)
else:
    # print("C")
    for i in range(n):
        if color[i]:
            if len(nums[1]) > 0:
                ans[i] = nums[1].pop()
            else:
                ans[i] = nums[0].pop()
        else:
            if len(nums[2]) > 0:
                ans[i] = nums[2].pop()
            else:
                ans[i] = nums[0].pop()

print(" ".join(list(map(str, ans))))
N,M=map(int,input().split())
mp=[[] for i in range(N+1)]
for i in range(M):
  L,R,D=map(int,input().split())
  mp[L].append([R,D])
  mp[R].append([L,-D])

dist=[None]*(N+1)

def dfs(n):
  for np,nd in mp[n]:
    if dist[np]==None:
      dist[np]=dist[n]+nd
      if not dfs(np):
        return False
    elif dist[np]!=dist[n]+nd:
      return False
  return True

ans=True
for i in range(1,N+1):
  if dist[i]==None:
    dist[i]=0
    if not dfs(i):
      ans=False
      break
if ans:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import sys
sys.setrecursionlimit(200002)

N,M=map(int,input().split())
mp=[[] for i in range(N+1)]
for i in range(M):
  L,R,D=map(int,input().split())
  mp[L].append([R,D])
  mp[R].append([L,-D])

dist=[None]*(N+1)

def dfs(n):
  for np,nd in mp[n]:
    if dist[np] is None:
      dist[np]=dist[n]+nd
      if not dfs(np):
        return False
    else:
      if dist[np]!=dist[n]+nd:
        return False
  return True
ans=True
for i in range(1,N+1):
  if dist[i] is None:
    dist[i]=0
    if not dfs(i):
      ans=False
      break
if ans:
  print("Yes")
else:
  print("No")