Harryxun/stf_run huggingface dataset:
def henkan(str)
    for s in str:
        print('1' if s = '9' else '9',end='')
        print('')
henkan(input())

### FIXED CODE ###

def henkan(str):
    for s in str:
        print('1' if s == '9' else '9',end='')
    print('')
henkan(input())
n = int(input())
h = list(map(int, input().split()))

ans = 1
if h[0] <= h[1]:
  ans += 1

isCount = True
for i in range(2,n):
  if h[0] <= h[i]:
    if h[1] <= h[i]:
      for j in range(1,i):
        if h[j] > h[i]:
          isCount = False
      if isCount:
        ans += 1
      isCount = True
print(ans)

### FIXED CODE ###

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

ans = 1
if len(h) >= 2:
  if h[0] <= h[1]:
    ans += 1
  for i in range(2,n):
    isCount = True
    if h[0] <= h[i]:
      if h[1] <= h[i]:
      	for j in range(1,i):
          if h[j] > h[i]:
          	isCount = False
      	if isCount:
          ans += 1
print(ans)
x= input()

for i in range(10000)
	print("Case i: x)

	if x == 0:
		break

### FIXED CODE ###

import sys 

cnt =1

while 1:
    x = sys.stdin.readline().strip()
    if x == "0":
        break

    print("Case %d: %s"%(cnt,x))
    cnt+=1
n, k = map(int, input().split())
s = input()
s.replace(s[k], s[k].lower())
print(s)



### FIXED CODE ###

n, k = map(int, input().split())
s = input()
print(s[:k-1]+s[k-1].lower()+s[k:])
import sys

def search(a,b,c,no,num):
	c[no-1] += num
	for k in range(len(a)):
		if a[k] == no:
			search(a,b,c,b[k],num)

n,q = map(int,input().split())
a = []
b = []
c = [0,0,0,0]

for i in range(n-1):
	a_dash, b_dash = map(int,input().split())
	a.append(a_dash)
	b.append(b_dash)
	#c.append(0)

for i in range(q):
	no,num = map(int,input().split())
	search(a,b,c,no,num)

for i in range(len(c)):
	sys.stdout.write(str(c[i]))
	sys.stdout.write(" ")

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7) #追加

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

counter = [0 for _ in range(n)]
E = [[] for _ in range(n)]

#辺の定義
#辺E(u,v)の重みがw
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  E[b].append(a)
  E[a].append(b)

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

res = 0
#行ったかどうか
color = [-1 for _ in range(n)]

#dfsで色を塗っていく
stack = [0]
color[0] = counter[0]
while stack:
  u = stack.pop()
  for v in E[u]:
    if color[v] == -1:
      stack.append(v)
      color[v] = color[u] + counter[v]

ans = [str(color[i]) for i in range(n)]
print(" ".join(ans))
def trial_division(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1: a.append(n)
        
    return a

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

L = trial_division(g)

D = {}

#print(L)

for i in L:
    if i not in D:
        D[i] = 1
print(len(D)+1)

### FIXED CODE ###

def trial_division(n):
    a = []  
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2   
    if n != 1: a.append(n)

    return a

from fractions import gcd

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

g = gcd(A,B)

L = trial_division(g)

D = {}

for i in L :
    if i not in D :
        D[i] = 1

print(len(D)+1)
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)
n,m=map(int,input().split())
s=input()
t=input()
n,m=max(n,m),min(n,m)
l=lcm(n,m)
d=[set() for i in range(l)]
f=l
for i in range(n):
    d[i*n//l].add(s[i])
for i in range(m):
    d[i*m//l].add(t[i])
for i in range(l):
    if len(d[i])==2: f=-1
print(f)


### FIXED CODE ###

def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)
n,m=map(int,input().split())
s=input()
t=input()
l=lcm(n,m)
d={}
f=l
for i in range(max(n,m)):
    o=i*(l//n)
    p=i*(l//m)
    if i<n and o not in d:
        d[o]=s[i]
    elif i<n and o in d and d[o]!=s[i]:
        f=-1
    if i<m and p not in d:
        d[p]=t[i]
    elif i<m and p in d and d[p]!=t[i]:
        f=-1
print(f)
k = int(input())
s = input()
l = len(s)
MOD = 10 ** 9 + 7
# 余事象でs が部分文字列として含まれない K + len(s)文字列の個数を求める
total = pow(26, k + l, MOD)
# dp[i][j]:k+l の長さの文字列の中で、長さi で、sのj番目の文字列まじで含む文字列の個数とする
# dp[i][j] = dp[i-1][j-1] + dp[i-1][j] * 25 となる
# これだと10**12でTLEなので、まとめる
# 答えたいのは、dp[k+l][l]で初期化はdp[1][1] = 1 dp[1][0] = 25
# l までいったら遷移の仕方が変わって*26を続けるだけで良いようになる
dp = [[0] * (l + 1) for _ in range(k + l + 1)]
dp[1][1] = 1
dp[1][0] = 25
for i in range(k + l + 1):
    for j in range(l + 1):
        if j == l:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] * 26
        else:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] * 25
        dp[i][j] %= MOD
total = total + MOD - dp[k + l][l]
print(total % MOD)



### FIXED CODE ###

k = int(input())
s = input()
l = len(s)
MOD = 10 ** 9 + 7


def comb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


p = MOD
N = 10 ** 6 * 2 + 10 # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

# Sn の位置をx = l-1,l,..,l+k-1まで全て動かす
# pow(25,x-l-1,MOD)* x-1Cl-1 * pow(26,l+k-1-x,MOD) をかければOK
ans = 0
for x in range(l - 1, l + k):
    ans += pow(25, x - l + 1, MOD) * comb(x, l - 1, MOD) * pow(26, l + k - 1 - x, MOD)
    ans %= MOD
print(ans)
"""
# dp[i][j]:k+l の長さの文字列の中で、長さi で、sのj番目の文字列まじで含む文字列の個数とする
# dp[i][j] = dp[i-1][j-1] + dp[i-1][j] * 25 となる
# これだと10**12でTLEなので、まとめる
# 答えたいのは、dp[k+l][l]で初期化はdp[1][1] = 1 dp[1][0] = 25
# l までいったら遷移の仕方が変わって*26を続けるだけで良いようになる
dp = [[0] * (l + 1) for _ in range(k + l + 1)]
dp[0][0] = 1
for i in range(1, k + l + 1):
    for j in range(l + 1):
        if j == l:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] * 26
        else:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] * 25
        dp[i][j] %= MOD
print(dp[k + l][l])
"""
import math
n = int(input())
lr = [None]*10000
rmax = 0
for i in range(n):
    lr[i]= list(map(int,input().split()))
    if lr[i][1] > rmax:
        rmax = lr[i][1]

p = [1]*(rmax+1)
p[0]=0
p[1]=0
        

for j in range(2,int(math.sqrt(rmax)+1)):
    if p[j] == 0:
        continue
    for i in range(2,rmax+1):
        if i!=j and i%j == 0:
            p[i] = 0
for i in range(rmax, 1,-2):
    if p[(i+1)//2] == 0:
        p[i] = 0
p[2] = 0
for i in range(2,rmax):
    p[i+1] += p[i]  

for i in range(n):
    print(p[lr[i][1]] - p[lr[i][0]-1])
    

    

### FIXED CODE ###

import math
n = int(input())
lr = [None]*100000
rmax = 0
for i in range(n):
    lr[i]= list(map(int,input().split()))
    if lr[i][1] > rmax:
        rmax = lr[i][1]

p = [1]*(rmax+1)
p[0]=0
p[1]=0
        

for j in range(2,int(math.sqrt(rmax)+1)):
    if p[j] == 0:
        continue
    for i in range(2,rmax+1):
        if i!=j and i%j == 0:
            p[i] = 0
for i in range(rmax, 1,-2):
    if p[int((i+1)/2)] == 0:
        p[i] = 0
p[2] = 0
for i in range(2,rmax):
    p[i+1] += p[i]  

for i in range(n):
    print(p[lr[i][1]] - p[lr[i][0]-1])
a,b = input().split()
c = a * b
d = c % 2

if d == 1:



### FIXED CODE ###

a,b = input().split()
c = int(a) * int(b)
d = c % 2
 
if d == 1:
    print("Odd")
else:
    print("Even")
a,b,c=map(int,input().split())
z=0

if a<b:
    if a<c:
        if b>c
            z=1
else:
    if a>c:
        if b<c:
            z=1

if z==1:
    print('Yes')
else:
    print('No')



### FIXED CODE ###

a,b,c=map(int,input().split())
z=0

if a<b:
    if a<c:
        if b>c:
            z=1
else:
    if a>c:
        if b<c:
            z=1

if z==1:
    print('Yes')
else:
    print('No')
s = raw_input()
k = int(raw_input())

opreq = [(ord('z') - ord(c) + 1) % 26 for c in s]

s_ = []

if len(s) > 1:
    i = 0
    while k > 0 and i < len(s) - 1:
        if opreq[i] < k:
            k = k - opreq[i]
            s_.append('a')
        else:
            s_.append(s[i])
        i += 1

# Last character
last_c = chr((k + ord(s[-1]) - ord('a')) % 26 + ord('a'))
s_.append(last_c)

print("".join(s_))

### FIXED CODE ###

s = raw_input()
print("{} {}".format(s[:4], s[4:]))
a, b, c = [int(i) for i in input().split()]
nums = 0
for i in range(a,c+1)
    if i%b ==0 :
        nums = nums + 1
    else:
        pass
   
print(nums)

### FIXED CODE ###

a, b, c = [int(i) for i in input().split()]
nums = 0
for i in range(a, b + 1):
    if c%i == 0:
        nums = nums + 1
    else:
        pass
print(nums)
import math
N, K = (int(i) for i in input().split())

pow_base = math.floor(math.log((K-1),2)) + 1
base = N * (2 ** pow_base)

res = 0
for i in range(1, N+1):
    if i >= K :
        res += (2 ** pow_base)
    else:
        power = math.floor(math.log((K-1) // i, 2)) + 1
        res += 2 ** (pow_base - power)
print(res / base)




### FIXED CODE ###

import math
N, K = (int(i) for i in input().split())

if K == 1:
    pow_base = 1
else:
    pow_base = math.floor(math.log((K-1),2)) + 1
base = N * (2 ** pow_base)

res = 0
for i in range(1, N+1):
    if i >= K :
        res += (2 ** pow_base)
    else:
        power = math.floor(math.log((K-1) // i, 2)) + 1
        res += 2 ** (pow_base - power)
print(res / base)
def dfs(v, p, dist):
    for u, w in tree[v]:
        if u == p:
            continue
        else:
            dist[u] = dist[v] + w
            dfs(u, v, dist)


n = int(input())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    tree[u - 1].append((v - 1, w))
    tree[v - 1].append((u - 1, w))

dist = [0 for _ in range(n)]
dfs(0, 0, dist)

for i in dist:
    if i % 2 == 0:
        print(0)
    else:
        print(1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)


def dfs(v, p, dist):
    for u, w in tree[v]:
        if u == p:
            continue
        else:
            dist[u] = dist[v] + w
            dfs(u, v, dist)


n = int(input())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    tree[u - 1].append((v - 1, w))
    tree[v - 1].append((u - 1, w))

dist = [0 for _ in range(n)]
dfs(0, -1, dist)

for i in dist:
    if i % 2 == 0:
        print(0)
    else:
        print(1)
N,X=map(int,input().split())
L=list(map(int,input().split()))
#i回目に跳ねる座標のリスト
D=[]
D.append(0)
for i in range(1,N+2):
  D.append(D[i-1]+L[i-1])
s=count(j for j in D if j<=X)
print(s)

### FIXED CODE ###

N,X=map(int,input().split())
L=list(map(int,input().split()))
D=[]
D.append(0)
for i in range(1,N+1):
  D.append(D[i-1]+L[i-1])
s=0
for j in range(0,N+1):
  if D[j]<=X:
    s+=1
print(s)
N=int(input())
d=list(map(int, input().split()))
C=N//2
for x in range(0,N):
    for y in range(0,N-1):
        if d[y]<d[y+1]:
            t=d[y]
            d[y]=d[y+1]
            d[y+1]=t
    N=N-1
if d[C]==d[C-1]:
    print(0)
elif:
    print(d[C-1]-d[C])


### FIXED CODE ###

N=int(input())
d=list(map(int, input().split()))
C=N//2
d.sort()
if d[C]==d[C-1]:
    print(0)
else:
    print(d[C]-d[C-1])
print ((R*6.28))

### FIXED CODE ###

R = float(input())
print(R*6.28)
N, L = (int(x) for x in input().split())
#リンゴiの味はL+i-1で与えられる。（i=1~N）
#作る予定のアップルパイの味の総和はN*(L-1) + 1/2*(N+1)*N
#出力はN-1個からアップルパイを作るとき、元の味との差が最小になる味
#味が0に最も近いものを探して、引けばよい。
aji = [L+i for i in range(N)]
#print(aji)
left = 0

while (aji[left] < 0):
    left += 1
#print(left)
ans = sum(aji) - aji[left]
print(ans)

### FIXED CODE ###

N, L = (int(x) for x in input().split())
#リンゴiの味はL+i-1で与えられる。（i=1~N）
#作る予定のアップルパイの味の総和はN*(L-1) + 1/2*(N+1)*N
#出力はN-1個からアップルパイを作るとき、元の味との差が最小になる味
#味が0に最も近いものを探して、引けばよい。
aji = [L+i for i in range(N)]
#i=1~Nなので注意
#print(aji)
#0に一番近いものを探索
left = 0
while (aji[left] < 0):
    if left < N-1:
        left += 1
    else:
        break
#print(left)
ans = sum(aji) - aji[left]
print(ans)
import collections
import math

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N,M=map(int, input().split())
l=[[0 for i in range(N)]for j in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    l[a-1][b-1]=1


a = np.array(l)
# print(type(a))
# # <class 'numpy.ndarray'>

n, labels = connected_components(a)

cc=collections.Counter(labels)
ans=max(cc.values())
print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M=map(int,input().split())
uf=UnionFind(N)
for i in range(M):
    A,B=map(int,input().split())
    uf.union(A-1,B-1)
ans=0
for i in range(N):
    ans=max(ans,uf.size(i))

print(ans)
import sympy

n = int(input())

if sympy.isprime(n):
    print(n)
else:
    res = sympy.nextprime(n, 1)
    print(res)


### FIXED CODE ###

import math

n = int(input())


def prime_checker(n):
    dest = int(math.sqrt(n))
    for i in range(2, dest):
        if n % i == 0:
            return False
    return True


while True:
    if prime_checker(n):
        print(n)
        break
    n += 1
from collections import defaultdict


def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    counter = defaultdict(int)
    for ai in A:
        counter[ai] += 1
    
    sorted_c = sorted(counter.values())
    ans = 0
    for i in range(len(counter) - K):
        ans += sorted_c[i]
    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    ans = 10 ** 9
    for i in range(N):
        cnt = 0
        ai = A[i]
        while 1:
            if ai % 2 == 0:
                ai //= 2
                cnt += 1
            else:
                break
        ans = min(ans, cnt)
    print(ans)


if __name__ == '__main__':
    solve()
import math
A,B,H,M = map(int,input().split())
if M == (H/5+M/12):
    print(abs(A-B))

elif M == (H/5+M/12) + 30 or M == (H/5+M/12) - 30:
    print(A+B)

elif H == 0:
    print(L)
    shita = math.radians(M*6)
    if shita > math.pi:
        shita = 2*math.pi - shita
    cos_shita = math.cos(shita)
    c_zizyou = A**2 + B**2 - 2 * A * B * cos_shita
    print(math.sqrt(c_zizyou))
elif M == 0:
    shita = math.radians(H*30)
    if shita > math.pi:
        shita = 2*math.pi - shita
    cos_shita = math.cos(shita)
    c_zizyou = A**2 + B**2 - 2 * A * B * cos_shita
    print(math.sqrt(c_zizyou))
else:
    H = H/12 * 60
    H = H + (1/12 * M)
    shita = math.radians(abs(H-M)*6)
    if shita > math.pi:
        shita = 2*math.pi - shita
    cos_shita = math.cos(shita)
    c_zizyou = A**2 + B**2 - 2 * A * B * cos_shita
    print(math.sqrt(c_zizyou))


### FIXED CODE ###

import math
A,B,H,M = map(int,input().split())


H = H/12 * 60
H = H + (1/12 * M)
shita = math.radians(abs(H-M)*6)
if shita > math.pi:
    shita = 2*math.pi - shita
cos_shita = math.cos(shita)
c_zizyou = A**2 + B**2 - 2 * A * B * cos_shita
print(math.sqrt(c_zizyou))
N = int(input())

for i in range(N):
  S.append(str(input()))

cnt_ar = list(set(S))
cnt_ar.sort()

length = len(cnt_ar)

ar = [0 for i in range(length)]

for i in range(length):
  ar[i] = S.count(cnt_ar[i])

max_num = max(ar)

for i in range(len(ar)):
  if ar[i] == max_num:
    print(cnt_ar[i])


### FIXED CODE ###

N = int(input())

d = {}
for _ in range(N):
    S = input()
    if S in d:
        d[S] += 1
    else:
        d[S] = 1

m = max(d.values())
for s in sorted(k for k in d if d[k] == m):
    print(s)
a, b = [int('14' if x == '1' else x) for x in input().split()
print('Alice' if a > b else 'Bob' if b > a else 'Draw')

### FIXED CODE ###

a, b = [int('14' if x == '1' else x) for x in input().split()]
print('Alice' if a > b else 'Bob' if b > a else 'Draw')
n=int(input())
mod=10**9+7
dp=[0]*(n+1)
S=[0]*(n+1)
dp[0]=1
dp[1]=1
dp[2]=1
S[0]=1
for i in range(n):
  if i+1>=3:
    dp[i+1]=2*dp[i]-dp[i-1]+dp[i-2]
  dp[i+1]%=mod
  S[i+1]=S[i]+(n-1)*dp[i]
  S[i+1]%=mod
ans=S[n]
for i in range(1,n):
  ans+=((n-1)**2)*dp[i-1]
  ans%=mod
print(ans)
#print(S)
#print(dp)

### FIXED CODE ###

n=int(input())
if n==1:
  print(1)
  exit()
mod=10**9+7
dp=[0]*(n+1)
S=[0]*(n+1)
dp[0]=1
dp[1]=1
dp[2]=1
S[0]=1
for i in range(n):
  if i+1>=3:
    dp[i+1]=2*dp[i]-dp[i-1]+dp[i-2]
  dp[i+1]%=mod
  S[i+1]=S[i]+(n-1)*dp[i]
  S[i+1]%=mod
ans=S[n]
for i in range(1,n):
  ans+=((n-1)**2)*dp[i-1]
  ans%=mod
print(ans)
#print(S)
#print(dp)
a = input()
A = int(a[0])
o = a[1]
B = int(a[2])
if o == "+":
 print(A+B)
else:
 print(A-B)

### FIXED CODE ###

a = input().split()
A = int(a[0])
o = a[1]
B = int(a[2])
if o == "+":
 print(A+B)
else:
 print(A-B)
import collections
import bisect
n,m = map(int,input().split())
p = [list(map(int,input().splilt())) for i in range(m)]
a = collections.deefaultdict(list)
for x,y in sorted(p):
  a[x]+=[y]
for x,y in p:
  z = bisect.bisect(a[x],y)
  print("%06d%06d"%(x,z))

### FIXED CODE ###

import collections
import bisect
n,m=map(int,input().split())
p=[[int(j) for j in input().split()] for i in range(m)]
a=collections.defaultdict(list)
for x,y in sorted(p):
    a[x]+=[y]
for x,y in p:
    z=bisect.bisect(a[x],y)
    print("%06d%06d"%(x,z))
a, b=map(int, raw_input().split()):
if  a > b:
print 'a > b'
elif  a < b:
print 'a < b'
else:
print 'a == b'

### FIXED CODE ###

a,b=map(int,raw_input().split())
if a > b:
    print 'a > b'
elif a < b:
    print 'a < b'
else:
    print 'a == b'
X, N = map(int, input().split())

if N == 0:
    print(X)

else:
    p = list(map(int, input().split()))
    q = [i for i in range(0, 101)]

    for r in p:
        idx = q.index(r)
        del q[idx]

    if X in q:
        print(X)

    else:
        q.sort()
        mindif = 100

        for num in q:
            dif = abs(X - num)
            if mindif <= dif:
                break
            else:
                mindif = dif
                ans = num
        print(ans)


### FIXED CODE ###

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

if N == 0:
    print(X)

else:
    p = list(map(int, input().split()))
    q = [i for i in range(-1, 102)]

    for r in p:
        idx = q.index(r)
        del q[idx]

    if X in q:
        print(X)

    else:
        q.sort()
        mindif = 1000

        for num in q:
            dif = abs(X - num)
            if mindif <= dif:
                break
            else:
                mindif = dif
                ans = num
        print(ans)
lis = []
a = raw_input()
while a != '0':
 lis.append(a)
 a = int(raw_input())

for i,v in enumerate(lis):
 print "Case %d: %d" % (i+1,v)

### FIXED CODE ###

i = 1
while True:
 a = raw_input()
 if a == '0':
  break
 print "Case %s: %s" % (i,a)
 i += 1
n,q=map(int,input().split())
tree=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a)
cnt=[0]*n
for _ in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x

def DFS(v,p_v):
    for next_v in tree[v]:
        if next_v==p_v:
            continue
        cnt[next_v]+=cnt[v]
        DFS(next_v,v)

DFS(0,-1)
print(*cnt)

### FIXED CODE ###

#「探索候補スタック」「探索済みリスト」「現在地点」の３点セットでとらえる
n,q=map(int,input().split())
mat=[set() for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    mat[a-1].add(b-1)
    mat[b-1].add(a-1) # プラスした要素
count=[0]*n
for _ in range(q):
    p,score=map(int,input().split())
    count[p-1]+=score

stack=[[0,0,-1]]
while stack:
    # print(stack)
    num,cnt,pr=stack.pop()
    count[num]+=cnt
    for k in mat[num]:
        if k==pr:
            continue
        stack.append([k,count[num],num])
print(*count)
x = input(x)

if x  == 0:
    print('1')
if x == 1:
    print('0')

### FIXED CODE ###

x = int(input())

if x  == 0:
    print('1')
if x == 1:
    print('0')
import numpy as np

N=int(input())
A=np.array([int(input()) for i in range(N)],dtype=np.int32)
B=[0 for i in range(N)]
C=sorted(A)
count=0
for i in range(N):

    if B[i]:
        continue

    else:
        temp=A[i]
        for m in range(i,N):
            if not B[m]:
                if A[m]==C[-1]:
                    B[m]=1
                    C.pop()
                    break
                else:
                    if temp<A[m]:
                        temp=A[m]
                        B[m]=1
        count+=1
    #print(i,count,B)
print(count)


### FIXED CODE ###

import bisect
import collections

N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
lst=collections.deque([])
for i in range(N):
    if A[i]==C[-1]:
        C.pop()
        if lst:
            lst.pop()
        else:
            count+=1
        continue
    idx=bisect.bisect_left(lst,A[i])-1
    #print(idx,lst,A[i])
    if idx<0:
        lst.appendleft(A[i])
        count+=1
    else:
        lst[idx]=A[i]

print(count)
import numpy as np
H,W,K = map(int,input().split())

a = [list(input()) for _ in range(H)] #listの中にlist()を標準入力する。H行分作成する。
#a = np.zeros((int(H),int(W)))
print(a)
count = 0
ans = 0
for i in range(2**W): #行の塗り方のパターン
    for j in range(2**H): #列の塗り方のパターン
        count = 0
        for s in range(H):
            for t in range(W):
                if(i >> s)&1 and (j>>t) & 1 and a[s][t] =="#":
                    count += 1
            if count == K:
                ans += 1
print(ans)

### FIXED CODE ###

N = int(input())

x = 0
while x < N:
    x = x + 1000

output = x - N
print(output)
def trial_division(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1: a.append(n)
        
    return a

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

L = trial_division(g)

D = {}

print(L)

for i in L:
    if i not in D:
        D[i] = 1
print(len(D)+1)

### FIXED CODE ###

def trial_division(n):
    a = []  
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2   
    if n != 1: a.append(n)

    return a

from fractions import gcd

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

g = gcd(A,B)

L = trial_division(g)

D = {}

for i in L :
    if i not in D :
        D[i] = 1

print(len(D)+1)