Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###



import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

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

def get_key(l):
    return ','.join(map(str, l))

def calc(l):
    if len(l) <= 1:
        dp[get_key(l)] = 0
        return 0

    if get_key(l) in dp:
        return dp[get_key(l)]

    x = abs(l[0]-l[1]) + calc(l[1:])
    dp[get_key(l)] = x
    return x

# 0 3 5 -1 0 みたいに
L = [0] + A + [0]
dp = {}
for i in range(1, N+1):
    l = L[0:i] + L[i+1:]
    print(calc(l))

### FIXED CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

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

def calc(l):
    count = 0
    for i in range(len(l)-1):
        count += abs(l[i]-l[i+1])

    return count

# 0 3 5 -1 0 みたいに
L = [0] + A + [0]
max_L = calc(L)
#print(max_L)

# 左右引いて、左右通しで計算すればいい
for i in range(1, N+1):
    diff_minus = abs(L[i-1]-L[i])+abs(L[i]-L[i+1])
    diff_plus = abs(L[i-1]-L[i+1])
    print(max_L-diff_minus+diff_plus)
### BUGGY CODE ###

MOD = 10**9+7
def fact(n, factors, l):
    rtn = factors
    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
            if i in rtn:
                k = rtn[i]
                rtn[i] = max(rtn[i],cnt)
                l *= pow(i,max(0,cnt-k),MOD)
            else:
                rtn[i] = cnt
                l *= pow(i,cnt,MOD)

    if temp!=1:
        if temp in rtn:
            k = rtn[temp]
            rtn[temp] = max(rtn[temp],1)
            l *= pow(i,max(0,1-k),MOD)
        else:
            rtn[temp] = 1
            l *= pow(temp,1,MOD)

    return rtn,l

def main():
    N = int(input())
    A = list(map(int, input().split()))
    # 方針.A全体のlcmをLとすると、ans=Σ(i=[0,N])x/Ai
    ans = 0
    LCM = 1
    factors = {}
    for a in A:
        factors,LCM = fact(a,factors,LCM)
    for a in A:
        ans += (LCM//a)%MOD
        ans %= MOD
    print(ans)

main()


### FIXED CODE ###

def factorization(n):
    arr = []
    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.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

def main():
    n=int(input())
    a=list(map(int,input().split()))
    mod=pow(10,9)+7
    lcma={}
    for ai in a:
      f=factorization(ai)
      for fi in f:
        if fi[0] in lcma:
          lcma[fi[0]]=max(lcma[fi[0]],fi[1])
        else:
          lcma[fi[0]]=fi[1]
    l=1
    for k,v in lcma.items():
      l*=pow(k,v,mod)
      l%=mod
    ans=0
    for ai in a:
      ans+=l*pow(ai,mod-2,mod)
      ans%=mod
    print(ans)

main()
### BUGGY CODE ###

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

boxes=[0]*n #if ball in boxes[i-1]=boxes no.i
b=[]
#m=len(b)
i=n #iの番号が書いた箱、インデックスはa[i-1]について
while i>=1:
	count=a[i-1]
	for j in range(i+1,n+1):
		if j%i==0:
			count+=boxes[j-1]
	boxes[i-1]=count%2
	if boxes[i-1]:
		b.append(i)
	i-=1
#print(boxes)

print(len(b))
print(*b) #space区切り

### FIXED CODE ###

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

boxes=[0]*n #if ball in boxes[i-1]=boxes no.i
'''
b=[]
#m=len(b)
i=n #iの番号が書いた箱、インデックスはa[i-1]について
while i>=1:
	count=a[i-1]
	for j in range(i+1,n+1):
		if j%i==0:
			count+=boxes[j-1]
	boxes[i-1]=count%2
	if boxes[i-1]:
		b.append(i)
	i-=1
#print(boxes)

print(len(b))
print(*b) #space区切り
'''
for i in reversed(range(n)):
	boxes[i]=(a[i]+sum(boxes[i::i+1]))%2

print(sum(boxes))
for i in range(n):
	if boxes[i]:
		print(i+1,end=" ")
### BUGGY CODE ###

x = int(input())
a = 0
b = 0

for a_ in range(-1000, 1000):
    for b_ in range(-1000, 1000):
        if a_**5 - b_**5 ==x:
            print(a_, b_)
   

### FIXED CODE ###

x = int(input())
a = 0
b = 0

for a_ in range(-500, 500):
    for b_ in range(-500, 500):
        if a_**5 - b_**5 ==x:
            a = a_
            b = b_
            break
            
print(a, b)
### BUGGY CODE ###

N = int(input())
nums = [int(i) for i in input().split()]

l = 0
for i in range(len(nums)):
    for j in range(len(nums)):
        if i == j: continue
        if nums[i]%nums[j] == 0 :
            l += 1
            break
print(N-l)

### FIXED CODE ###

M = 10 ** 6 + 1
N = int(input())
A = list(map(int, input().split()))
 
A.sort()
not_divisible = [True] * (M)
# print(A)

result = 0
for i in range(N):
    target = A[i]
    if not_divisible[target]:
        if i+1 <= N-1 and A[i+1] == A[i]:
            pass
        else:
            result += 1
        for j in range(target, M, target):
            not_divisible[j] = False
print(result)
### BUGGY CODE ###

import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

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

for i in range(1,N):
    a_lcm=lcm(a_lcm,A[i])

result=0
for i in range(N):
    result+=a_lcm//A[i]
    result%=1000000007
print(result%1000000007)

### FIXED CODE ###

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

 #最小公倍数
def lcm(a,b):
    return a*b//gcd(a,b)

N=int(input())
A=list(map(int,input().split()))
a_lcm=A[0]
Mod=10**9+7

for i in range(1,N):
    a_lcm=lcm(a_lcm,A[i])

a_lcm%=Mod

result=0
for i in range(N):
    result+=a_lcm*pow(A[i],Mod-2,Mod)
print(result%1000000007)
### BUGGY CODE ###

S = input()
L = len(S)
cnt = 0

for i in range(0,L-3):
    for j in range(i+4,L+1):
        integer = int(S[i:j])
        if integer % 2019 == 0:
            cnt += 1

print(cnt)


### FIXED CODE ###

from collections import Counter

S = input()
n = len(S)

dp = [0]*(n+1)

dp[n-1] = int(S[-1])

for i in range(n-2,-1,-1):
    dp[i] = (dp[i+1]+pow(10,n-i-1,2019)*int(S[i]))%2019

ans = Counter(dp)
cnt = 0
for i in ans.values():
    cnt += i*(i-1)//2
    
print(cnt)
### BUGGY CODE ###

import os
import sys
from collections import defaultdict

from functools import lru_cache

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

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, M = list(map(int, sys.stdin.readline().split()))
UV = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
S, T = list(map(int, sys.stdin.readline().split()))

graph = defaultdict(set)
for u, v in UV:
    graph[u].add(v)

memo = [[None] * (N+1) for _ in range(3)]


def dest(v, count):
    if memo[count - 1][v] is not None:
        return memo[count - 1][v]

    if count <= 1:
        memo[count - 1][v] = graph[v]
        return graph[v]
    ret = set()
    for u in graph[v]:
        ret |= dest(u, count - 1)
    memo[count - 1][v] = ret
    return ret


checked = set()
vs = {S}
i = 0
prev = 0
while True:
    i += 1
    s = set()
    for v in vs:
        s |= dest(v, 3)
    checked |= vs
    if T in s:
        print(i)
        break
    if len(checked) == prev:
        print(-1)
        break
    vs = s - checked
    prev = len(checked)


### FIXED CODE ###

import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

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

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, M = list(map(int, sys.stdin.readline().split()))
UV = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
S, T = list(map(int, sys.stdin.readline().split()))

graph = [[] for _ in range(N + 1)]
for u, v in UV:
    graph[u].append(v)

que = deque()
que.append((S, 0))
reached = np.zeros((N + 1, 3), dtype=bool)
reached[S, 0] = True

while que:
    u, step = que.popleft()
    for v in graph[u]:
        s = step + 1
        if not reached[v, s % 3]:
            reached[v, s % 3] = True
            que.append((v, s))
        if v == T and s % 3 == 0:
            print(s // 3)
            exit()
print(-1)
### BUGGY CODE ###

h,w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
b = [list(map(int, input().split())) for _ in range(h)]
g = [[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    g[i][j] = abs(a[i][j] - b[i][j])
a = b = 0
dp = [[[False]*6400 for _ in range(w+1)] for _ in range(h+1)]
dp[0][1][0] = True
dp[1][0][0] = True
for i in range(1,h+1):
  for j in range(1,w+1):
    for x in range(6400):
      if dp[i-1][j][x] or dp[i][j-1][x]:
        dp[i][j][abs(x-g[i-1][j-1])] |= True
        if x + g[i-1][j-1] < 6400:
            dp[i][j][x+g[i-1][j-1]] |= True
for x in range(6400):
  if dp[h][w][x]:
    print(x)
    break


### FIXED CODE ###

def fold(x,m):
    y = 0
    for _ in range(m):
        y |= x&1
        y <<= 1
        x >>= 1
    return x|y

lmi = lambda: list(map(int, input().split()))

h,w = lmi()
a = [lmi() for _ in range(2*h)]
g = [[abs(a[i][j] - a[i+h][j]) for j in range(w)] for i in range(h)]

mask = (1<<12801) - 1

dp = [[0]*(w+1) for _ in range(h+1)]
dp[0][0] = 1
for i in range(h):
  for j in range(w):
    cur,par = g[i][j],dp[i][j]
    pos = (par<<cur)|fold(par,cur)
    pos &= mask
    dp[i+1][j] |= pos
    dp[i][j+1] |= pos
for i in range(12801):
  if dp[-1][-2]&(1<<i):
    print(i)
    break
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
A = 10**12
B = 10**6
d = [INF] * (h*w)

stack = deque([(ch-1)*A + (cw-1)*B + 0])
stack_append = stack.append
stack_popleft = stack.popleft

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

T = ((-1,0), (1,0), (0,1), (0,-1))
while stack:
    x = stack_popleft()
    curh = (x // A)
    x -= curh * A
    curw = (x // B)
    cnt = x - curw * B

    if d[curh * w + curw] <= cnt:
        continue
    else:
        d[curh * w + curw] = cnt

    for dh, dw in T:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            stack_append(nh*A + nw*B + cnt)

    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            stack_append(nh*A + nw*B + cnt+1)

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])


### FIXED CODE ###

import heapq
class Dijkstra:
    INF = 10**18
    threshold = 10**9

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append(cost * self.threshold + Y)

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, st)
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p // self.threshold
            node = p - cost * self.threshold
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to // self.threshold
                to_node = to - to_cost * self.threshold
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, to_cost * self.threshold + to_node)

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

S = [input() for _ in range(h)]

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '#': continue
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '#': continue
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == 10**18: print(-1)
else: print(ans)
### BUGGY CODE ###

h, w=map(int, input().split())
a=[]
need_visited=[[0 for i in range(w)] for j in range(h)]
stack=[]
for i in range(h):
    a.append(list(input()))

for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            stack.append([i, j])



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


while len(stack)!=0:
    now_point=stack.pop(0)
    now_y=now_point[0]
    now_x=now_point[1]
    for i in range(4):
        if 0<=now_x+dx[i]<=w-1 and 0<=now_y+dy[i]<=h-1:
            if a[now_y+dy[i]][now_x+dx[i]]==".":
                need_visited[now_y+dy[i]][now_x+dx[i]]=need_visited[now_y][now_x]+1
                a[now_y+dy[i]][now_x+dx[i]]="#"
                stack.append([now_y+dy[i], now_x+dx[i]])
max_list=[]
for i in range(h):
    max_list.append(max(need_visited[i]))
print(max(max_list))


### FIXED CODE ###

from collections import deque

H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]

painted = deque()
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            painted.append([h, w, 0])

ans = 0
while len(painted) > 0:
    blackcell = painted.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = blackcell[0] + dy
        nw = blackcell[1] + dx
        d = blackcell[2]
        if 0 <= nh < H and 0 <= nw < W and cell[nh][nw] == '.':
            cell[nh][nw] = '#'
            painted.append([nh, nw, d + 1])
        ans = d

print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
o = 0

for _ in range(q):
    qu = list(input().split())
    if len(qu) == 1:
        o = -1 if o == 0 else 0
    if len(qu) == 3:
        if qu[1] == '1':
            s = ''.join([qu[2], s]) if o == 0 else ''.join([s, qu[2]])
        if qu[1] == '2':
            s = ''.join([s, qu[2]]) if o == 0 else ''.join([qu[2], s])

print(s) if o == 0 else print(s[::-1])


### FIXED CODE ###

from collections import deque
S = list(input()) 
d = deque()
for s in S:
    d.append(s)
q = int(input())
o = 0

for _ in range(q):
    qu = list(input().split())
    if len(qu) == 1:
        o = -1 if o == 0 else 0
    if len(qu) == 3:
        if qu[1] == '1':
            d.appendleft(qu[2]) if o == 0 else d.append(qu[2])
        if qu[1] == '2':
            d.append(qu[2]) if o == 0 else d.appendleft(qu[2])

r = ''
if o == 0:
    for _ in range(len(d)):
        r += d.popleft()
else:
    for _ in range(len(d)):
        r += d.pop()

print(r)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from collections import deque,defaultdict


def main():
  ## input
  N,Q = map(int, input().split())
  STX = deque()
  for i in range(N):
    s,t,x = map(int, input().split())
    STX.append([x,s-x,t-x])
  Dn = [int(input()) for _ in range(Q)]+[10**10]

  ans = {}
  for x,s,t in sorted(list(STX)):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      ans[Dn[l]] = x
      Dn.pop(l)
  for d in Dn[:-1]:
    ans[d] = -1

  return ans


if __name__ == "__main__":
  ans = main()
  for d in sorted(list(ans.keys())):
    print(ans[d])
    

### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

N=int(input())
s=[]
for i in range(N):
	s.append(input())

for i in range(N):
	s[i]=sorted(s[i])

t=[]
flag=0
for i in range(N):
	for j in range(len(t)):
		flag=0
		if s[i]==t[j][0]: #tは二次元リストで定義していたことに気を付けよう
			t[j][1] += 1
			flag=1
			break
	if flag==0:
		t.append([s[i],1])

count=0
for i in range(len(t)):
	if t[i][1]>=2:
		count += int(t[i][1]*(t[i][1]-1)/2)

print(count)


### FIXED CODE ###

N = int(input())
S = [list(input()) for _ in range(N)]

for i in range(N):
	S[i].sort()

for i in range(N):
	S[i] = "".join(S[i])

S.sort()
S.append(None)

pt,count,C = 1,0,[]
while pt <= N:
	if S[pt-1] == S[pt]:
		count += 1
	else:
		if count > 0:
			C.append(count+1)
			count = 0
	pt += 1

ans = 0
for i in range(len(C)):
	ans += C[i]*(C[i]-1) // 2

print(ans)
### BUGGY CODE ###

import numpy as np

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

for k in range(0, min(100, K)):
    work = np.zeros_like(A)
    for i in range(0, N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])
        work[l] += 1
        if (r + 1 < N):
            work[r + 1] -= 1
    work = np.cumsum(work)
    A = work

print(" ".join(A.astype(str)))

### FIXED CODE ###

import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))
### BUGGY CODE ###

n,k = map(int,input().split())
r,s,p = map(int,input().split())
d={"r":p,"s":r,"p":s}
li=[]
s=input()
ans=0
for i,j in enumerate(s):
    if i<k:
        ans+=d[j]
        li.append(j)
    else:
        if li[0]!=j:
            ans+=d[j]
            li=li[1:]+[j]
        else:
            li=li[1:]+["#"]
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
r,s,p = map(int,input().split())
d={"r":p,"s":r,"p":s}
s=input()
memo=s[:k]
ans=0
for i,j in enumerate(s):
    if i<k:
        ans+=d[j]
    else:
        if memo[0]!=j:
            ans+=d[j]
            memo=memo[1:]+j
        else:
            memo=memo[1:]+"#"
print(ans)
### BUGGY CODE ###

n=int(input())
d=list(map(int,input().split()))
c=[0]*(n+1)
ans=1
for i in range(0,n):
  c[d[i]]+=1

if d[0]!=0 or c[0]!=1:
  print(0)
  
else:
  for j in range(1,n):
    if c[j]==0 and c[j+1]==0:
      ans+=0
    else:
      ans*=c[j-1]**c[j]
      
  print(ans%998244353)  
    
  



### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
x=max(d)
li=[0]*(x+1)
for i in range(n):
    li[d[i]]+=1
if d[0]!=0 or li[0]!=1:
    print(0) 
else:
    ans=1
    for i in range(2,len(li)):
        ans*=pow(li[i-1],li[i],998244353)   
    print(ans%998244353)
### BUGGY CODE ###

N=int(input())
A=[]
int_max=0
str_max=[]
for i in range(N):
    A.append(input())
B=list(set(A))
for i in range(len(B)):
    if int_max<A.count(B[i]):
        str_max=[B[i]]
        int_max=A.count(B[i])
    elif int_max==A.count(B[i]):
        str_max.append(B[i])
str_max.sort()
for i in str_max:
    print(i)

### FIXED CODE ###

from collections import OrderedDict
N=int(input())
d=dict()
A=[]
ma=0
for i in range(N):
  s=input()
  if s not in d:
    d[s]=0
  d[s]+=1
d=OrderedDict(sorted(d.items(), key=lambda x:x[1], reverse=True))
for i in d:
  if ma<=d[i]:
    ma=d[i]
  if ma!=d[i]:
    break
  A.append(i)
print(*sorted(A),sep="\n")
### BUGGY CODE ###

from collections import deque

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

r = [[] for i in range(N+1)]

for i in range(M):
    a,b = map(int,input().split())
    r[a].append(b)
    r[b].append(a)

miteru = deque([1])
mita = {1}
res = [-1]*(N+1)

while  len(miteru) != 0: 
    now = miteru.popleft()
    x =set( r[now])
    x = x - mita
    for i in x:
        miteru.append(i)
        if res[i] == -1:res[i] =now
    mita.add(now)
    
print("Yes")
for i in res[2:]:
    print(i)
#print("\n".join(res))


### FIXED CODE ###

from collections import deque
N,M = map(int,input().split())

root = [set()for i in range(N+1)]
ans = [0 for i in range(N+1)]

for i in range(M):
    a,b = map(int,input().split())
    root[a].add(b)
    root[b].add(a)

task = deque([1])
itta = {1}

while len(task) > 0:
    now = task.popleft()
    additionanl = root[now] - itta #到達済みを排除している
    for i in additionanl: #ノードチェック
        ans[i] = now 
        itta.add(i)
    task.extend(list(additionanl)) #チェックしたノードを追加
print("Yes")
for i in range(2,N+1):
    print(ans[i])
### BUGGY CODE ###

def main():
    s = [c for c in input()]
    q = int(input())
    is_fwd = True
    for i in range(q):
        fields = [i for i in input().split()]
        t = int(fields[0])
        if t == 1:
            is_fwd = not is_fwd
        elif t == 2:
            f = int(fields[1])
            c = fields[2]
            if (f == 1) == is_fwd:
                s = [c] + s
            else:
                s.append(c)

    if is_fwd:
        print(''.join(s))
    else:
        print(''.join(reversed(s)))

main()


### FIXED CODE ###

def main():
    s = input()
    q = int(input())
    is_fwd = True
    before = ''
    after = ''

    for i in range(q):
        fields = [i for i in input().split()]
        t = int(fields[0])
        if t == 1:
            is_fwd = not is_fwd
        elif t == 2:
            f = int(fields[1])
            c = fields[2]
            if (f == 1) == is_fwd:
                before += c
            else:
                after += c

    res = before[::-1] + s + after
    if is_fwd:
        print(res)
    else:
        print(res[::-1])

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
n, q = map(int, input().split())
cnt = [0] * n
tree = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)

for i in range(q):
    p, x = map(int, input().split())
    cnt[p - 1] += x

def dfs(cur, par):
    for chi in tree[cur]:
        if chi == par:
            continue
        cnt[chi] += cnt[cur]
        dfs(chi, cur)
dfs(0, -1)
print(*cnt)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
n, q = map(int, input().split())
cnt = [0] * n
tree = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)

for i in range(q):
    p, x = map(int, input().split())
    cnt[p - 1] += x

def dfs(cur, par):
    for chi in tree[cur]:
        if chi == par:
            continue
        cnt[chi] += cnt[cur]
        dfs(chi, cur)
dfs(0, -1)
print(*cnt)