Harryxun/stf_run huggingface dataset:
N,Q=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N-1)]
B=[list(map(int,input().split())) for i in range(Q)]

#行先
C=[[]*i for i in range(N)]
#合計値
D=[0]*N
#足跡
E=[False]*N

for i in range(N-1):
  C[A[i][0]-1].append(A[i][1])
  C[A[i][1]-1].append(A[i][0])


def f(a,b):
  D[a-1]+=b
  E[a-1]=True
  x=len(C[a-1])
  if x>0:
    for k in C[a-1]:
      if a<k:
        f(k,b)

for l in range(Q):
  f(B[l][0],B[l][1])
  
  
print(*D)

### FIXED CODE ###

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

l = [[] for i in range(N)]

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

used = [False] * N
r = [0] * N

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

stack = [0]
while stack:
  i = stack.pop()
  used[i] = True
  for to in l[i]:
    if not used[to]:
      stack.append(to)
      r[to] += r[i]

print(*r)
At = int(input())
Ba = int(input())
K = int(input())

for i in range(K):
    if At >= 1:
        At -= 1
    elif Ba >= 1:
        Ba -= 1
    
print(At)
print(Ba)

### FIXED CODE ###

At,Ba,K = (int(x) for x in input().split())

if K <= At:
    print(At - K)
    print(Ba)
elif K <= At + Ba:
    print(0)
    print(Ba - (K - At))
else :
    print(0)
    print(0)
"""
can do it by subproblems. for a given i, the only information you need from the previous values
is the min value of previous values.
the first i=0 is guaranteed to satisfy the constraint. (counting from zero).
"""
import sys


def count_low_elements(N, P):
    count = 0
    min_so_far = sys.maxsize
    for val in P:
        if val <= min_so_far:
            count += 1
            min_so_far = val
    return count


if __name__ == "__main__":
    test1 = \
"""5
4 2 5 1 3"""
    test2 = \
"""4
4 3 2 1"""
    test3 = \
"""6
1 2 3 4 5 6"""
    test4 = \
"""8
5 7 4 2 6 8 1 3"""
    test5 = \
"""1
1"""
    test = test5
    # N, P_string = test.split("\n")
    # P = list(map(int, P_string.split()))
    N = int(input())
    P = list(map(int, input().split()))
    print(count_low_elements(N, P))
`

### FIXED CODE ###

"""
can do it by subproblems. for a given i, the only information you need from the previous values
is the min value of previous values.
the first i=0 is guaranteed to satisfy the constraint. (counting from zero).
"""
import sys


def count_low_elements(N, P):
    count = 0
    min_so_far = sys.maxsize
    for val in P:
        if val <= min_so_far:
            count += 1
            min_so_far = val
    return count


if __name__ == "__main__":
    test1 = \
"""5
4 2 5 1 3"""
    test2 = \
"""4
4 3 2 1"""
    test3 = \
"""6
1 2 3 4 5 6"""
    test4 = \
"""8
5 7 4 2 6 8 1 3"""
    test5 = \
"""1
1"""
    test = test5
    # N, P_string = test.split("\n")
    # P = list(map(int, P_string.split()))
    N = int(input())
    P = list(map(int, input().split()))
    print(count_low_elements(N, P))
N = int(input())
A = list(map(int,input().split()))
if A[0] == 0 or A[N-1] == 0:
  A_tmp = A[0]
  A_ = A[1:N]
  A_.append(A_tmp)
  A = A_
  flag = 1
else:
  flag = 0
if A[0]<A[N-1]:
  start = A[0]
else:
  start = A[N-1]
for i in range(2*start,1,-2):
  ans = [i]
  A_tmp = A[:]
  A_tmp[0] -= ans[0]//2
  A_tmp[N-1] -= ans[0]//2 
  for j in range(1,N):
    if A_tmp[j-1]<A_tmp[j]:
      ans.append(A_tmp[j-1]*2)
      A_tmp[j] -= ans[j]//2
      A_tmp[j-1] -= ans[j]//2
    else:
      ans.append(A_tmp[j]*2)
      A_tmp[j] -= ans[j]//2
      A_tmp[j-1] -= ans[j]//2
  if sum(A_tmp)==0:
    break
if flag == 1:
  tmp = [0]*N
  tmp[1:] = ans[:N-1]
  tmp[0] = ans[N-1]
  ans = tmp
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
S = sum(A)//2
S = 2*(S - sum(A[1::2]))
ans = [S]
for i in range(1,N):
  ans.append(2*A[i-1]-ans[i-1])
print(' '.join(map(str,ans)))
S = input()
L = 0
max_L = 0

for i in len(S):
  s = S[i]
  TF = any(['A'==s, 'C'==s, 'G'==s, 'T'==s])
  if TF:
    L += 1
  elif L >= max_L:
    max_L = L
    L = 0

print(max_L)

### FIXED CODE ###

S = input()
L = 0
max_L = 0
 
for i in range(len(S)):
  s = S[i]
  TF = any(['A' in s, 'C' in s, 'G' in s, 'T' in s])
  if TF:
    L += 1
    if L >= max_L:
        max_L = L
  elif L >= max_L:
    max_L = L
    L = 0

print(max_L)
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

MAX_VALUE = 1e4


def min_cost_sort():
    ans = 0
    for i in range(array_length):
        if check_order[i]:
            continue
        current_index = i
        _sum, min_value, circle_size = 0, MAX_VALUE, 0
        while True:
            check_order[current_index] = True
            circle_size += 1
            current_value = array[current_index]
            min_value = min(min_value, current_value)
            _sum += current_value
            current_index = kv_reverse[current_value]
            if check_order[current_index]:
                break
        ans += min(_sum + (circle_size - 2) * min_value, _sum + min_value + (circle_size + 1) * _sum)
    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    # assert len(array) == array_length

    check_order = [False] * array_length
    kv_reverse = [-1] * (array_length + 1)
    compare_ans = sorted(array)
    for j in range(array_length):
        kv_reverse[compare_ans[j]] = j
    print(min_cost_sort())

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

MAX_VALUE = int(1e4 + 1)


def min_cost_sort():
    ans = 0
    for i in range(array_length):
        if check_order[i]:
            continue
        current_index = i
        circle_sum, circle_min, circle_size = 0, MAX_VALUE, 0
        while True:
            check_order[current_index] = True
            circle_size += 1
            current_value = array[current_index]
            circle_min = min(circle_min, current_value)
            circle_sum += current_value
            current_index = value_to_index[current_value]
            if check_order[current_index]:
                break
        ans += min(circle_sum + (circle_size - 2) * circle_min,
                   circle_sum + circle_min + (circle_size + 1) * min_value)
    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    # assert len(array) == array_length

    check_order = [False] * array_length
    value_to_index = dict()
    compare_ans = sorted(array)
    min_value = compare_ans[0]
    for j in range(array_length):
        value_to_index[compare_ans[j]] = j
    print(min_cost_sort())
import sys

class Node():
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None

    def prewalk(self):
        nodeList = [self.key]
        if self.left:
            nodeList += self.left.prewalk()
        if self.right:
            nodeList += self.right.prewalk()
        return nodeList

    def inwalk(self):
        nodeList = []
        if self.left:
            nodeList += self.left.inwalk()
        nodeList += [self.key]
        if self.right:
            nodeList += self.right.inwalk()
        return nodeList

    def print(self):
        print('', ' '.join(map(str, self.root.inwalk())))
        print('', ' '.join(map(str, self.root.prewalk())))

class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        Nz = Node(key)
        Ny = None #???????£?
        Nx = self.root
        while Nx:
            Ny = Nx
            if Nz.key < Ny.key:
                Nx = Nx.left
            else:
                Nx = Nx.right

        Nz.parent = Ny
        if Ny == None:
            self.root = Nz
        elif Nz.key < Ny.key:
            Ny.left = Nz
        else:
            Ny.right = Nz

tree = Tree()

n = sys.stdin.readline()
for line in sys.stdin:
    if line[0] == 'i':
        tree.insert(int(line.split()[1]))
    else:
        tree.print()

### FIXED CODE ###

import sys

class Node():
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None

    def prewalk(self):
        nodeList = [self.key]
        if self.left:
            nodeList += self.left.prewalk()
        if self.right:
            nodeList += self.right.prewalk()
        return nodeList

    def inwalk(self):
        nodeList = []
        if self.left:
            nodeList += self.left.inwalk()
        nodeList += [self.key]
        if self.right:
            nodeList += self.right.inwalk()
        return nodeList

class Tree():
    def __init__(self):
        self.root = None

    def insert(self, key):
        Nz = Node(key)
        Ny = None #???????£?
        Nx = self.root
        while Nx:
            Ny = Nx
            if Nz.key < Ny.key:
                Nx = Nx.left
            else:
                Nx = Nx.right
        Nz.parent = Ny
        if Ny == None:
            self.root = Nz
        elif Nz.key < Ny.key:
            Ny.left = Nz
        else:
            Ny.right = Nz

    def print(self):
        print('', ' '.join(map(str, self.root.inwalk())))
        print('', ' '.join(map(str, self.root.prewalk())))

tree = Tree()

n = sys.stdin.readline()
for line in sys.stdin:
    if line[0] == 'i':
        tree.insert(int(line.split()[1]))
    else:
        tree.print()
import numpy as np

r = float(input())
print ('{0:.6f} {1:.6f}'.format(r*r*np.pi, 2*r*np.pi))


### FIXED CODE ###

# coding : utf-8
import math as m
r = float(input())
print ('{0:.6f} {1:.6f}'.format(r*r*m.pi, 2*r*m.pi))
import sys
INF = 10**9
sys.setrecursionlimit(INF)
import math


def main():
    x, = map(int, open(0).read().split())

    """
    x=a^5-b^5=(a-b)(a^4+a^3b+a^2b^2+ab^3+b^4)
    x//(a-b)=int>0
    a-b>0
    """

    tmp_a = round(x**(1 / 5))
    for i in range(-tmp_a * 2, tmp_a * 2 + 1):
        tmp_bbbbb = i**5 - x
        # print(i, i**5 - x, tmp_bbbbb)
        is_b_positive = True
        if tmp_bbbbb < 0:
            tmp_bbbbb *= -1
            is_b_positive = False
        tmp_b = tmp_bbbbb**(1 / 5)
        if tmp_b == int(tmp_b):
            a = i
            tmp_b = int(tmp_b)
            if is_b_positive:
                b = tmp_b
            else:
                b = -tmp_b
            break

    ans = f'{a} {b}'
    print(ans)
    return(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
INF = 10**9
sys.setrecursionlimit(INF)
import math


def main():
    x, = map(int, open(0).read().split())

    """
    x=a^5-b^5=(a-b)(a^4+a^3b+a^2b^2+ab^3+b^4)
    x//(a-b)=int>0
    a-b>0
    x=O(a^4)
    """

    for i in range(-1000, 1000 + 1):
        for j in range(-i + 1, i):
            if i**5 - j**5 == x:
                a = i
                b = j
                break

    ans = f'{a} {b}'
    print(ans)
    return(ans)


if __name__ == '__main__':
    main()
s = input()
l = len(s)
limit = [max(i+1,l-i-1) for i in range(l-1) if s[i] != s[i+1]]
print(min(limit))


### FIXED CODE ###

s = input()
l = len(s)
limit = [max(i+1,l-i-1) for i in range(l-1) if s[i] != s[i+1]]
limit.append(l)
print(min(limit))
n = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(n[k+1])

### FIXED CODE ###

n = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())-1
print(n[k])
S = input()
T = input()

dic = {}
dic_rev = {}


def solve():
    for s, t in zip(S, T):
        if t in dic.keys():
            if s != dic[t]:
                print('No')
                return
        else:
            dic[t] = s
    for s, t in zip(S, T):
        if t in dic_rev.keys():
            if t != dic_rev[s]:
                print('No')
                return
        else:
            dic_rev[s] = t
    print('Yes')
    return


solve()


### FIXED CODE ###

S = input()
T = input()

dic = {}
dic_rev = {}


def solve():
    for s, t in zip(S, T):
        if t in dic.keys():
            if s != dic[t]:
                print('No')
                return
        else:
            dic[t] = s
    for s, t in zip(S, T):
        if s in dic_rev.keys():
            if t != dic_rev[s]:
                print('No')
                return
        else:
            dic_rev[s] = t
    print('Yes')
    return


solve()
if k==1:
    return 0
elif n==k:
    return 0
else:
    max_dif=(n-k-1)-1
    return max_dif

### FIXED CODE ###

n,k= [int(i) for i in input().split()]
if k==1:
    print (0)
else:
    print (n-k)
from math import gcd
from functools import reduce


def lcm_base(x, y):
    return (x * y) // gcd(x, y)
def lcm(numbers):
    return reduce(lcm_base, numbers, 1)


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

mod = []
for m in range(lcm(a)):
    k = [m % a[i] for i in range(N)]
    mod.append(sum(k))
print(max(mod))



### FIXED CODE ###

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

f = sum(a)-N
print(f)
N, K = map(int, input().split())

def okikae(t):
    if N%K==0:
        print("0")
    elif K/2 >= t and t <= K:
        print(t)
    else:
        okikae(abs(t-K))

okikae(N)

### FIXED CODE ###

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

def okikae(t, k):
    if k==0:
        print(t)
    elif int(k/2)+1 > t:
        print(t)
    elif t%k==0:
        print(0)
    elif t>k and t%k > 0:
        t = k+(t%k)
        okikae(abs(t-k), k)
    else:
        okikae(abs(t-k), k)

okikae(N, K)
import math
A = []
N = int(input())
maxdiff = 0
for n in range(N):
    A.append(int(input()))
S = tuple(A)
Smax = ((S[i]-min(S[:i])) for i in range(1, N) if S[i] > S[i-1])
print(max(Smax))

### FIXED CODE ###

import math
A = []
N = int(input())
maxdiff = 0
for n in range(N):
    A.append(int(input()))
R = tuple(A)

Dmax = R[1] -R[0]
Rmin = R[0]

for i in range(1, N):
    if R[i] >= R[i-1]:
        if R[i] - Rmin > Dmax:
            Dmax = R[i] -Rmin
    if R[i] < Rmin:
        Rmin = R[i]
#    print(R[i], Dmax, Rmin)

print(Dmax)
def gcd(_a,_b):
    a=max([_a, _b]); b=min([_a, _b])
    while True:
        if not b==0:
            m=a%b
        if m==0:
            return b
        a=b

a,b,k=(int(x) for x in input().split())
g=gcd(a,b)
cd=[]
i=g
while True:
    if g%i==0:
        cd.append(i)
        i=i//2
        if i==1 or i==0:
            break
    else:
        i-=1
print(cd[k-1])

### FIXED CODE ###

def gcd(t):
    b,a=sorted(t)
    while True:
        m=a%b
        if m==0:
            return b
        a=b;b=m
a,b,k=(int(x) for x in input().split())
g=gcd((a,b))
cd=[]
for i in range(g+1)[::-1]:
    if i==0:
        break
    if g%i==0:
        cd.append(i)
print(cd[k-1])
n, m =map(int,input().split())
s = list(map(int,input().split()))
a = [input() for __ in range(n)]

n =int(input())
s = list(map(int,input().split()))
l =[0]*n
print(l)
while i < n-2 :
     l[s[i]-1] += 1
     i += 1
for _ in range(n):
     print(l[_])

### FIXED CODE ###

n =int(input())
s = list(map(int,input().split()))
l =[0]*n
i = 0
while i < n-1 :
     l[s[i]-1] += 1
     i += 1
for _ in range(n):
     print(l[_])
import sys
from collections import deque

def main():
    input = sys.stdin.readline

    s = input()[:-1]
    q = int(input())
    tmp = [input().split() for _ in range(q)]

    flag = 0
    ans = deque([s])
    for t in tmp:
        if len(t) == 1:
            flag = ~flag 
        else:
            f = int(t[1])
            c = t[2]
            if (f == 1 and flag == 0) or (f ==2 and fag == -1):
                ans.appendleft(c)
            else:
                ans.append(c)
    if flag == 0:
        print(''.join(ans))
    else:
        print(''.join(ans[::0]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque

def main():
    input = sys.stdin.readline

    s = input()[:-1]
    q = int(input())
    tmp = [input().split() for _ in range(q)]

    flag = 0
    ans = deque([s])
    for t in tmp:
        if len(t) == 1:
            flag = ~flag 
        else:
            f = int(t[1])
            c = t[2]
            if (f == 1 and flag == 0) or (f ==2 and flag == -1):
                ans.appendleft(c)
            else:
                ans.append(c)
    if flag == 0:
        print(''.join(ans))
    else:
        print(''.join(ans)[::-1])

if __name__ == '__main__':
    main()
N, Q = map(int, input().split())
ab = [[0, 0]] * (N - 1)
for i in range(N - 1):
    ab[i] = list(map(int, input().split()))
ab = sorted(ab, key=lambda x: x[0])
px = [[0, 0]] * (N - 1)
for i in range(Q):
    px[i] = list(map(int, input().split()))
px = sorted(px, key=lambda x: x[0])
nodes = [0] * (N)
for p, x in px:
    nodes[p - 1] += x
for a, b in ab:
    nodes[b - 1] += nodes[a - 1]
print(' '.join(map(str, nodes)))


### FIXED CODE ###

N,Q = map(int,input().split())
parents = {1:0}
for _ in range(N-1):
    a,b = map(int,input().split())
    key,val = max(a,b), min(a,b)
    parents[key] = val
counts = [0]*(N+1)
for _ in range(Q):
    p,x = map(int,input().split())
    counts[p] += x
results = [0]*(N+2)
for i in range(1,N+1):
    results[i] = counts[i]+results[parents[i]]
    print(results[i], end=' ')
s = input().split('i')

h = s[:len(s)-1]
space = s[len(s)-1]

for j in h:
  if j =='h' and space == '':
    ans = 'Yes'
  else:
    ans = 'No'
  
print(ans)

### FIXED CODE ###

h = input()

result = 'Yes'

if len(h)%2 != 0:
  result ='No'
  
for a in range(0,len(h)-1,2):  
  b = h[a:a+2]
  if b != 'hi':
    result = 'No'
    break
    
print(result)
import sys

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

A = int(input())
n = 1

dp = [0]*(N+1)
if N == 1:
    if 1 == A:
        print('0')
        sys.exit()
    else:
        print('1')
        sys.exit()
if 1 == A:
    dp[1] = 0
    if M != n:
        A = int(input())
        n += 1
else:
    dp[1] = 1
dp[0] = 1
for i in range(2, N+1):
    if i == A:
        dp[i] = 0
        if M != n:
            A = int(input())
            n += 1
    else:
        dp[i] = dp[i-1]%1000000007 + dp[i-2]%1000000007

print(dp[N]%1000000007)

### FIXED CODE ###

import sys

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

dp = [-1]*(N+1)
dp[0] = 1
dp[1] = 1
for i in range(M):
    num = int(input())
    dp[num] = 0

for i in range(2, N+1):
    if dp[i] == 0:
        continue
    dp[i] = dp[i-1]%1000000007 + dp[i-2]%1000000007

print(dp[N]%1000000007)
n, m = map(int, raw_input().split())
c = map(int, raw_input().split())
memo = [-1] * (n+1)
def dfs(rest):
    if memo[rest] != -1:
        return memo[rest]
    if rest == 0:
        return 0
    res = n+1
    for i in xrange(m):
        if c[i] <= rest:
            res = min(res, 1 + dfs(rest - c[i]))
    memo[rest] = res
    return res
print dfs(n)

### FIXED CODE ###

n, m = map(int, raw_input().split())
c = map(int, raw_input().split())
dp = [n+1] * (n+1)
dp[n] = 0
for rest in xrange(n, 0, -1):
    for i in xrange(m):
        if c[i] <= rest:
            dp[rest - c[i]] = min(dp[rest - c[i]], 1 + dp[rest])
print dp[0]
a, b, c = map(int, input().split())
cnt = 0
for i in range(a, b+1):
    if(!(c % i)):
        cnt += 1
print(cnt)


### FIXED CODE ###

a, b, c = map(int, input().split())
cnt = 0
for i in range(a, b+1):
    if(not(c % i)):
        cnt += 1
print(cnt)
a = int(input())

b = int(input())

ans = int(0)

for i in range(1,21):
    if b > a*i-i+1:
            ans += 1
    else:
            ans += 1
            break

print(ans)


### FIXED CODE ###

s = list(input())

t = list(input())

ans = int(0)

for i in range(3):
    if s[i]==t[i]:
            ans += 1 
        
print(ans)
import unittest
import abc082d as tester

def ioByFile(fn='inputFile.txt'):
	with open(fn) as f:
		for line in f:
			yield line

def getCorrect(fn='correct.txt'):
	with open(fn) as f:
		return f.read()

class InputTests(unittest.TestCase):
	def _calFUT(self, io):
		return str(tester.main(io))+'\n'
		
	def test_it(self):
		testInput=ioByFile()
		io=lambda : next(testInput)
		actual = self._calFUT(io)
		
		self.assertEqual(actual,getCorrect())

if __name__ == "__main__":
	unittest.main()

### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

def io_generator():
	return input()

#+++++++++++++++++++

def isBitOn(value, n):
	return (value & (2 ** n)) > 0
	
def isMake(l,v):
	if len(l)==0 and v ==0:
		return True
		
	for i in range(2 ** len(l)):
		r=sum([v * (1-2*isBitOn(i,j)) for j,v in enumerate(l)])
		if r == v:
			return True
	return False
	
def move_next(v,i):
	rv = (v | 2 ** (i))
	ri = i+1
	return rv, ri
	
def buck(v,i):
	#111,3->101,3
	#101,3->010,2
	for j in range(i-1):
		n=i-1-j
		d=(v & 2** (n - 1))
		if d > 0:
			nv=(v & (2**(n-1) - 1))
			nnv,ni = move_next(nv, n)
			return True,nnv,ni
	return False, -1, -1
	
def isMake3(l,a_target):
	tree=0
	ii=0
	l.sort(reverse = True)
	est=lambda al,av:sum([v * isBitOn(av,j) for j,v in enumerate(l)])
	cc=True
	
	while cc:
		ccv=est(l, tree)
		#print(bin(tree),ii, est(l,tree),a_target)
		while ccv < a_target:
			tree, ii = move_next(tree,ii)
			#print(bin(tree),ii, est(l,tree),a_target)
			if ii > len(l):
				return False, -1
			ccv += l[ii-1]
			
		if ccv == a_target:
			return True, tree
		else:
			cc,tree,ii=buck(tree, ii)
			
	return False, -1
	
def isMake2(l, a_target):
	off=sum(l)
	if abs(a_target) > off:
		return False
	elif abs(a_target) == off:
		return True
	
	ll=[2*i for i in l]
	ret, _ = isMake3(ll, off + a_target)
	return ret
	
def isMakeDp(l, a_target):
	ss=set()
	ss.add(0)
	for v in l:
		next_ss=set()
		for p in list(ss):
			next_ss.add(p+v)
			next_ss.add(p-v)
		ss=next_ss
	return a_target in ss
		

def next(a_xy):
	return (a_xy+1)%2
	
def main(io):
	ft=io()
	goal = list(map(int, io().split()))
	
	isFirstMove=True
	init_pos=[0,0]
	xy=0
	mm=0
	ml=[[],[]]
	for c in ft:
		if isFirstMove and c=='F':
			init_pos[0]+=1
		elif isFirstMove and c=='T':
			isFirstMove=False
			xy = next(xy)
			mm=0
		elif c == 'F':
			mm+=1
		elif c== 'T':
			if mm > 0:
				ml[xy].append(mm)
			xy=next(xy)
			mm=0
	if mm>0:
		ml[xy].append(mm)

	is_debug=False
	if is_debug:
		print(ml)
		print(init_pos)
		print(goal)
	for i in range(2):
		if not isMakeDp(ml[i], goal[i] - init_pos[i]):
			return 'No'
	return 'Yes'

#++++++++++++++++++++

if __name__ == "__main__":
	io= lambda : io_generator()
	print (main(io))
h,w=map(int,input().split())
ms=[]
for i in range(h):
    m=input()
    ms.append(list(m))
count=0
for i in range(h):
    for j in range(w):
        if ms[i][j]==".":
            if i>0 and j>0:
                if ms[i-1][j-1]=="#":
                    count+=1
            if i>0 :
               if ms[i-1][j]=="#":
                    count+=1
            if i>0 and w-1>j:
                if ms[i-1][j+1]=="#":
                    count+=1
            if j>0 :
                if ms[i][j-1]=="#":
                    count+=1
            if w-1>j :
                if ms[i][j+1]=="#":
                    count+=1
            if h-1>i and j>0 :
                if ms[i+1][j-1]=="#":
                    count+=1
            if h-1>i:
                if ms[i+1][j]=="#":
                    count+=1
            if h-1>i and h-1>j:
                if ms[i+1][j+1]=="#":
                    count+=1
            ms[i][j]=str(count)
            count=0

for i in range(h):
    temp="".join([ms[i][j] for j in range(w)])
    print(temp)



### FIXED CODE ###

h,w=map(int,input().split())
ms=[]
for i in range(h):
    m=input()
    ms.append(list(m))
count=0
for i in range(h):
    for j in range(w):
        if ms[i][j]==".":
            if i>0 and j>0:
                if ms[i-1][j-1]=="#":
                    count+=1
            if i>0 :
               if ms[i-1][j]=="#":
                    count+=1
            if i>0 and w-1>j:
                if ms[i-1][j+1]=="#":
                    count+=1
            if j>0 :
                if ms[i][j-1]=="#":
                    count+=1
            if w-1>j :
                if ms[i][j+1]=="#":
                    count+=1
            if h-1>i and j>0 :
                if ms[i+1][j-1]=="#":
                    count+=1
            if h-1>i:
                if ms[i+1][j]=="#":
                    count+=1
            if h-1>i and w-1>j:
                if ms[i+1][j+1]=="#":
                    count+=1
            ms[i][j]=str(count)
            count=0

for i in range(h):
    temp="".join([ms[i][j] for j in range(w)])
    print(temp)