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

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

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

#print(tree_list)

score_list = [0] * N
for j in range(Q):
    p, x = [int(n) for n in input().split()]
    score_list[p-1] += x

reached = [False] * N

def dfs(v):
    reached[v] = True

    for next_v in tree_list[v]:
        if reached[next_v] == True:
            continue

        score_list[next_v] += score_list[v]
        dfs(next_v)

dfs(0)

print(*score_list)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
N, Q = [int(n) for n in input().split()]
tree_list = [[] for _ in range(N)]

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

score_list = [0] * N
for j in range(Q):
    p, x = [int(n) for n in input().split()]
    score_list[p-1] += x

reached = [False] * N
def dfs(v):
    reached[v] = True
    for next_v in tree_list[v]:
        if reached[next_v] == True:
            continue
        score_list[next_v] += score_list[v]
        dfs(next_v)
dfs(0)
print(*score_list)
s = print()
p = print()

s *= 2
if s.find(p) ! = =1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input()
p = input()

s *= 2
if s.find(p) != -1:
    print("Yes")
else:
    print("No")
x,a,b=map(int,input().split())
c=x-a
print(c%b)

### FIXED CODE ###

x,a,b=[int(input()) for i in range(3)]
c=x-a
print(c%b)
N = int(input())
H = list(map(int, input().split()))
max_count = 0
for i in range(N-1):
  tmp_count = 0
  for j in range(i, N-2):
  	if H[j] >= H[j+1]:
      tmp_count=tmp_count+1

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
tmp = 0
s = 0
for i in range(N-1):
  if H[i] >= H[i+1]:
    tmp += 1
    s = max(s, tmp)
  else:
    tmp = 0
    
print(s)
#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define all(c) c.begin(), c.end()
#define rall(c) c.end(), c.begin()
#define INF (int)1e9
#define MOD 1000000007
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef map<int, int> MPII;
typedef set<int> SETI;

const int mxN = 2e5;
int a[mxN];

int sum(vector<int> v)
{
    int s = 0;
    for (int i = 0; i < v.size(); ++i)
    {
        s += v[i];
    }
    return s;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vi v(n);
    for (auto &x : v)
        cin >> x;

    int t;
    cin >> t;

    int s = sum(v);
    map<int, int> m;
    for (auto x : v)
        if (m.find(x) != m.end())
            m[x] += 1;
        else
            m[x] = 1;
    while (t--)
    {
        int b, c;
        cin >> b >> c;
        if (m.find(c) != m.end())
            m[c] += m[b];
        else
            m[c] = m[b];
        s += ((c - b) * m[b]);
        m[b] = 0;
        cout << s << "\n";
    }

    return 0;
}

### FIXED CODE ###

from collections import Counter
n = int(input())
ar = list(map(int, input().split()))

t = int(input())
c = Counter(ar)
s = sum(ar)
for i in range(t):
    a, b = list(map(int, input().split()))
    if b in c:
        c[b] += c[a]
    else:
        c[b] = c[a]
    s += ((b-a)*c[a])
    print(s)
    c[a] = 0
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    d = collections.defaultdict(int)
    for c in a:
        d[c] += 1
    t = sorted(list(d.keys()))
    if t[-1] - t[0] > 1:
        return 'No'
    if len(t) == 1:
        if t[0] == n - 1:
            return 'Yes'
        if t[0] > n / 2.0:
            return 'No'
        return 'Yes'
    b = t[1] - d[t[0]]
    n2 = d[t[1]]
    if n2 == 2 and b == n2 - 1:
        return 'Yes'
    if b < 1:
        print(1/0)
        return 'No'
    if b >= n2 - 2:
        return 'No'

    return 'Yes'


print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    d = collections.defaultdict(int)
    for c in a:
        d[c] += 1
    t = sorted(list(d.keys()))
    if t[-1] - t[0] > 1:
        return 'No'
    if len(t) == 1:
        if t[0] == n - 1:
            return 'Yes'
        if t[0] > n / 2.0:
            return 'No'
        return 'Yes'
    b = t[1] - d[t[0]]
    n2 = d[t[1]]
    if n2 == 2 and b == n2 - 1:
        return 'Yes'
    if b < 1:
        return 'No'
    if b >= n2 - 2:
        return 'No'
    if b > n2 / 2.0:
        return 'No'

    return 'Yes'


print(main())
s = [input() for i in range(int(input()))]
t = [input() for i in range(int(input()))]
l = list(set(s))
  print(max(0, max(s.count(l[i] - t.count(l[i])) for i in l)))

### FIXED CODE ###

s = [input() for i in range(int(input()))]
t = [input() for i in range(int(input()))]
l = list(set(s))
print(max(0, max(s.count(l[i]) - t.count(l[i]) for i in range(len(l)))))
N = int(input())
s = 0
for i in range(0,N):
  if (i+1) % 3 1= 0 or (i+1) % 5 != 0:
    s = s + (i+1)
print(s)

### FIXED CODE ###

K = int(input())
S = 0

def gcd(a,b):
   while b != 0:
       a, b = b, a % b
       if b ==0:
           return a
A1 = [0,0]
A2 = [0,0,0]
for i in range(1, K+1):
    S = S + i

if K > 1:
    for j in range(1, K):
        A1[0] =  j
        for k in range(j+1,K+1):
            A1[1] = k
            S += 6 * gcd(A1[1],A1[0])

if K > 2:
    for i1 in range(1, K-1):
        A2[0] = i1
        for k1 in range(i1+1, K):
            A2[1] = k1
            for j1 in range(k1+1,K+1):
                A2[2] = j1
                G3 = gcd(A2[2],A2[1])
                if G3 >= A2[0]:
                    S += 6 * gcd(G3,A2[0])
                else:
                    S += 6 * gcd(A2[0],G3)
print(S)
x, n = map(int, input().split())
if (n != 0):
  p = list(map(int, input().split()))
else:
  print(x)
  exit()

kouho = list(range(1, max(p) + n))
# print(kouho)

for i in range(len(p)):
  if p[i] != x:
    del kouho[kouho.index(p[i])]

kouho_num = kouho.index(x)
right = kouho_num + 1
left = kouho_num - 1


if kouho[right] - kouho[kouho_num] > kouho[kouho_num] - kouho[left]:
  print(kouho[left])
elif kouho[right] - kouho[kouho_num] == kouho[kouho_num] - kouho[left]:
  print(kouho[left])
else:
  print(kouho[right])


### FIXED CODE ###

x, n = map(int, input().split())
if (n != 0):
  p = list(map(int, input().split()))
else:
  print(x)
  exit()

kouho = list(range(-200, 200))


for i in range(len(p)):
  if p[i] != x:
    del kouho[kouho.index(p[i])]

kouho_num = kouho.index(x)
right = kouho_num + 1
left = kouho_num - 1

if (x not in p):
  print(x)
elif abs(kouho[right] - kouho[kouho_num]) > abs(kouho[kouho_num] - kouho[left]):
  print(kouho[left])
elif abs(kouho[right] - kouho[kouho_num]) == abs(kouho[kouho_num] - kouho[left]):
  print(kouho[left])
else:
  print(kouho[right])
[h,w,k]=list(map(int,input().split()))
cake=[]
for i in range(h):
	cake.append(list(input()))
ans=[[0 for i in range(w)]for j in range(h)]
num=1
ichigo=[]
for i in range(h):
	for j in range(w):
		if cake[i][j]=="#":
			ans[i][j]=num
			ichigo.append([i,j,num])
			num+=1
for i in range(len(ichigo)):
	yoko=ichigo[i][1]+1
	while True:
		if yoko==h:
			break
		elif ans[ichigo[i][0]][yoko]==0:
			ans[ichigo[i][0]][yoko]=ichigo[i][2]
			yoko+=1
		else:
			break
for i in range(len(ichigo)):
	left=ichigo[i][1]-1
	while True:
		if left<0:
			break
		elif ans[ichigo[i][0]][left]==0:
			ans[ichigo[i][0]][left]=ichigo[i][2]
			left-=1
		else:
			break

for i in reversed(range(ichigo[0][0])):
	for j in range(w):
		if ans[i][j]==0:
			ans[i][j]=ans[i+1][j]

for i in range(ichigo[0][0],h):
	for j in range(w):
		if ans[i][j]==0:
			ans[i][j]=ans[i-1][j]

for i in range(h):
	for j in range(w):
		print(ans[i][j], end=" ")
	print( )
	

### FIXED CODE ###

[h,w,k]=list(map(int,input().split()))
cake=[]
for i in range(h):
	cake.append(list(input()))
ans=[[0 for i in range(w)]for j in range(h)]
num=1
ichigo=[]
for i in range(h):
	for j in range(w):
		if cake[i][j]=="#":
			ans[i][j]=num
			ichigo.append([i,j,num])
			num+=1
for i in range(len(ichigo)):
	yoko=ichigo[i][1]+1
	while True:
		if yoko==w:
			break
		elif ans[ichigo[i][0]][yoko]==0:
			ans[ichigo[i][0]][yoko]=ichigo[i][2]
			yoko+=1
		else:
			break
for i in range(len(ichigo)):
	left=ichigo[i][1]-1
	while True:
		if left<0:
			break
		elif ans[ichigo[i][0]][left]==0:
			ans[ichigo[i][0]][left]=ichigo[i][2]
			left-=1
		else:
			break

for i in reversed(range(ichigo[0][0])):
	for j in range(w):
		if ans[i][j]==0:
			ans[i][j]=ans[i+1][j]

for i in range(ichigo[0][0],h):
	for j in range(w):
		if ans[i][j]==0:
			ans[i][j]=ans[i-1][j]

for i in range(h):
	for j in range(w):
		print(ans[i][j], end=" ")
	print( )
S = input()
T = input()
ruijimax = 0

for first in range(len(S)-len(T)):
    ruiji = 0
    for i in range(len(T)):
        if S[first+i] == T[i]:
            ruiji += 1
    if ruijimax <= ruiji:
        ruijimax = ruiji

print(len(T)-ruijimax)

### FIXED CODE ###

d,t,s = map(int, input().split())

if d/t<=s:
    print("Yes")
else:
    print("No")
day = ["SUN","MON","TUE","WED","THU","FRY","SAT"]
num = [7,6,5,4,3,2,1]
dic = {x:y for x,y in zip(day,num)}
s = input()
print(dic[s])

### FIXED CODE ###

day = ["SUN","MON","TUE","WED","THU","FRI","SAT"]
num = [7,6,5,4,3,2,1]
dic = {x:y for x,y in zip(day,num)}
s = input()
print(dic[s])
n = int(input())
a = int(input())
b = int(input())
print("Hello World" if n == 1 else a+b)

### FIXED CODE ###

n = int(input())
if n == 1:
    print("Hello World")
else:
    a = int(input())
    b = int(input())
    print(a+b)
dig, cnt = map(int, input().split())
ans = [-1]*dig

for i in range(cnt):
  place, num = map(int, input().split())
  place -= 1
  if ans[place] != -1:
    if ans[place] != num:
      print(-1)
      exit()
  elif place == 0 and num == 0:
    print(-1)
    exit()
  else:
    ans[place] = num
    
for i in range(cnt):
  if ans[i] == -1:
    if i == 0:
      ans[i] = 1
    elif ans[i] == -1:
      ans[i] = 0
  print(ans[i], end="")

### FIXED CODE ###

dig, cnt = map(int, input().split())
ans = [-1]*dig
 
for i in range(cnt):
  place, num = map(int, input().split())
  place -= 1
  if ans[place] != -1:
    if ans[place] != num:
      
      print(-1)
      exit()
  elif place == 0 and num == 0 and dig > 1:
    print(-1)
    exit()
  else:
    ans[place] = num
    
for i in range(dig):
  if ans[i] == -1:
    if dig > 1 and i == 0:
      ans[i] = 1
    else:
      ans[i] = 0
  print(ans[i], end="")
h w = input()
if h*w == 0:
  print(h*w/2)
 else:
  print(h*w//2+1)

### FIXED CODE ###

H,W=map(int, input().split())

if H == 1 or W == 1:
    print(1)
elif H * W % 2 == 0:
    print(int(H * W / 2))
elif H * W % 2 != 0:
    print(int(H * W // 2 + 1))
alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
m = int(input())
list = str(input())
n = len(list)
for i in range(n):
	if int(alpha.index(list[i])) + m < 26:
		list[i] = alpha[int(alpha.index(list[i])) + m]
	else:
		list[i] = alpha[int(alpha.index(list[i])) + m -26] 
print(list)

### FIXED CODE ###

alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
m = int(input())
list = input()
newlist = []
n = len(list)
for i in range(n):
	if int(alpha.find(list[i])) + m < 26:
		newlist.append(alpha[int(alpha.find(list[i])) + m])
	else:
		newlist.append(alpha[int(alpha.find(list[i])) + m -26]) 
moji = ''.join(newlist)
print(moji)
a,b,c = (int(x) for x in input().split())


if a==b:
    if a!=c:
        res = "Yes"
    else:
        res = "No"
if c==b:
    if a!=c:
        res = "Yes"
    else:
        res = "No"
if a==c:
    if a!=b:
        res = "Yes"
    else:
        res = "No"
        
print(res)

### FIXED CODE ###

a,b,c = (int(x) for x in input().split())

res = "No"
if a==b:
    if a!=c:
        res = "Yes"
    else:
        res = "No"
if c==b:
    if a!=c:
        res = "Yes"
    else:
        res = "No"
if a==c:
    if a!=b:
        res = "Yes"
    else:
        res = "No"
        
print(res)
import sys

args = sys.args[1::]
ints = [int(s) for s in args]

return sorted(ints) == [5, 5, 7]


### FIXED CODE ###

import sys

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

if sorted(args) == [5, 5, 7]:
  print('YES')
else:
  print('NO')
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

    
def main():
    n=int(input())
    x=[]
    y=[]
    h=[]
    ans=[0,0,0]
    for _ in range(n):
        xx,yy,hh=inpm()
        x.append(xx)
        y.append(yy)
        h.append(hh)
    for xc in range(101):
        for yc in range(101):
            a=[]
            H=0
            for i in range(n):
                d = abs(xc-x[i]) + abs(yc-y[i])
                if h[i]==0:
                    continue
                H=h[i]+d
                if len(a)>=1:
                    if H!=a[0]:
                        break
                    elif i==n-1:
                        ans=[str(xc),str(yc),str(H)]
                        break
                else:
                    a.append(H)
    print(' '.join(ans))
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

    
def main():
    n=int(input())
    xyh=[]
    for _ in range(n):
        x,y,h=inpm()
        xyh.append([x,y,h])
    xyh.sort(key=lambda x: x[2], reverse=True)
    for xc in range(101):
        for yc in range(101):
            x=xyh[0][0]
            y=xyh[0][1]
            h=xyh[0][2]
            d=abs(xc-x)+abs(yc-y)
            H=h+d
            for i in range(1,n):
                x=xyh[i][0]
                y=xyh[i][1]
                h=xyh[i][2]
                d = abs(xc-x) + abs(yc-y)
                if h!=max(0,H-d):
                    break
                if i == n-1:
                    print(xc,yc,H)
                    return
if __name__ == "__main__":
    main()
v=[-1,2,5,5,4,5,6,3,7,6]

N,M=map(int, input().split())
A=sorted(map(int, input().split()), reverse=True)

dp=[0]*(N+1)
mp=[[] for _ in range(N+1)]

for a in reversed(A):
	dp[v[a]] = 1
	mp[v[a]] = [a]

for i in range(N+1):
	for a in A:
		if i-v[a] >= 0 and dp[i-v[a]] > 0 and dp[i] < 1 + dp[i-v[a]]:
			dp[i] = 1 + dp[i-v[a]]
			mp[i] = [a] + mp[i-v[a]]

print("".join(map(str, mp[N])))


### FIXED CODE ###

v=[-1,2,5,5,4,5,6,3,7,6]

N,M=map(int, input().split())
A=sorted(map(int, input().split()), reverse=True)

dp=[0]*(N+999)
mp=[[] for _ in range(N+999)]

for a in reversed(A):
	dp[v[a]] = 1
	mp[v[a]] = [a]

for i in range(N+1):
	for a in A:
		if i-v[a] >= 0 and dp[i-v[a]] > 0 and dp[i] < 1 + dp[i-v[a]]:
			dp[i] = 1 + dp[i-v[a]]
			mp[i] = [a] + mp[i-v[a]]

print("".join(map(str, mp[N])))
# coding: utf-8
N = int(input())
D = list(map(int, input().split()))
l = [0] * (N-1)
top = max(D)
mod = 998244353

for i in range(N):
    l[D[i]] += 1
# print(*l)
ans = 1
for i in range(1, top+1):
    if l[i] != 0:
        ans *= l[i-1] ** l[i]
    if l[i] == 0:
        print(0)
        exit()
    ans = ans % mod
if D[0] != 0:
    ans = 0
if l[0] != 1:
    ans = 0
    

print(ans)

### FIXED CODE ###

# coding: utf-8
N = int(input())
if N % 2 == 0:
    print(N // 2 - 1)
else:
    print(N // 2)
def takahashi(n, k, x, y):
    if n > k:
        return (n-k+1)*x + (k-1)*y
    else:
        return n*x
    


n,k,x,y = list(map(int, input().split()))
takahashi(n,k,x,y)

### FIXED CODE ###

n=int(input())
k=int(input())
x=int(input())
y=int(input())

if n > k:
    print(k*x + (n-k)*y)
else:
    print(n*x)
n = int(input())
if n in 1:
    print("Hello World")
else:
    a = int(input())
    b = int(input())
    print(a+b)


### FIXED CODE ###

n = int(input())
if n == 1:
    print("Hello World")
else:
    a = int(input())
    b = int(input())
    print(a+b)
n = input()
i = 0
for number in n:
    if number == '1':
        m[i] = '9'
        i = i + 1
    elif number == '9':
        m[i] = '1'
        i = i + 1
    else:
        m[i] = n[i]
        i = i + 1

print(n)

### FIXED CODE ###

n = list(input())
i = 0

while i < 3:
    if n[i] == '1':
        n[i] = '9'
        i = i + 1
    else:
        n[i] = '1'
        i = i + 1

print(''.join(n))
n=int(input())
line1=list(map(int,input().split()))
line2=list(map(int,input().split()))
line=[line1,line2]
point=0
place=0
def judge(i):
  status1=0
  status2=0
  possible=1
  for k in range(n-i-1):
    status1+=line[0][i+k+1]
    status2+=line[1][i+k]
    if status1>=status2:
      possible=0
      break
  return possible
for i in range(n):
  point+=line[place][i]
  if palce==0 and judge(i)==1:
    place=1
    point+=line[place][i]
print(point)


### FIXED CODE ###

n=int(input())
line1=list(map(int,input().split()))
line2=list(map(int,input().split()))
line=[line1,line2]
point=0
place=0
def judge(i):
  status1=0
  status2=0
  possible=1
  for k in range(n-i-1):
    status1+=line[0][i+k+1]
    status2+=line[1][i+k]
    if status1>=status2:
      possible=0
      break
  return possible
for i in range(n):
  point+=line[place][i]
  if place==0 and judge(i)==1:
    place=1
    point+=line[place][i]
print(point)
import numpy as np
import math 
A, B, H, M = map(int, input().split())

pai = math.pi
angle = 2*pai*((H+M/60)/12 - M/60)

distance = np.sqrt(A**2+B**2-2*A*B*np.cos(angle))
print(distance)


### FIXED CODE ###

i = int(input())
s = i % 10
if s in [2, 4, 5, 7, 9]:
  print("hon")
elif s in [0, 1, 6, 8]:
  print("pon")
else:
  print("bon")
a, b = input.split()
print str(a*b), str((a+b)*2)

### FIXED CODE ###

a, b = map(int, raw_input().split())
print str(a*b), str((a+b)*2)
H, A = map(int, input().split())

x = 0
while True:
H = H - A
  if H < 0:
    break
  else:
    x += 1
print(x)

### FIXED CODE ###

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

x = 0
while True:
  if H <= 0:
    break
  if H > 0:
    H -= A
    x += 1
print(x)
N , L = map(int,input().sqlit())
S.list()
for i in range(N):
  S.append(input())
S.sort()
for i in range(S):
  print(i)

### FIXED CODE ###

N , L = map(int,input().split())
str = []
for i in range(N):
    str.append(input())
str.sort()
result = ""
for j in str:
    result += j
print(result)
N = int(input())
K = int(input())

# 桁数調べる
# tmp = N
# digit = 1
# while tmp >= 10:
#     tmp //= 10
#     digit += 1
# print(digit)

if K > len(str(N)):
    print(0)
    exit()

if K == 1:  # done
    N = str(N)
    ans = (len(N)-1) * 9
    ans += int(N[0])
    print(ans)

elif K == 2:
    N = str(N)
    # 最上位を避けた, (n-1)C2 * 9の二乗
    ans = (len(N)-1) * (len(N)-2) * 9 * 9 // 2
    # 最上位の桁2つのみ, 最上位がN[0]のパターン, N[0]の1通りと, N[1]通り
    ans += 1 * int(N[1])
    # 最上位の桁2つののみ, 最上位!=N[0]のパターン
    ans += (int(N[0])-1) * 9
    # 最上位とその他(二桁目は選ばない)
    ans += int(N[0]) * (len(N)-2) * 9
    print(ans)
elif K == 3:
    print(AAA)
    N = str(N)
    # 最上位を避けた選び方, n-1C3 * 9の三乗
    ans = (len(N)-1) * (len(N)-2) * (len(N)-3) * 9 * 9 * 9 // 6
    # 上位二桁とその他, 最上位がN[0]の場合
    ans += 1 * int(N[1]) * (len(N)-2) * 9
    # 上位二桁とその他, 最上位!=N[0]の場合, int(N[0])-1なのはN[0]のパターンを除くため
    ans += (int(N[0])-1) * 9 * (len(N)-2)*9
    # 最上位とその他 (二桁目は選ばない)
    ans += int(N[0]) * (len(N)-2) * (len(N)-3) * 9 * 9 // 2
    print(ans)


### FIXED CODE ###

N = str(input())
K = int(input())
# dp[i][j][k] :=  i桁目まで決めたとき、非ゼロの個数がj個で、
# k->0: そこまでの桁はNと完全一致, k->1: そこまでの桁ですでにN未満であることが確定
# しているときのパターン数
# kは0or1の二通り, jは0~KのK+1通り, iは0~NのN+1通り
dp = [[[0]*2 for _ in range(K+1)] for _ in range(len(N)+1)]
dp[0][0][0] = 1
for i in range(len(N)):
    x = int(N[i])  # Nは文字列であることに注意
    for j in range(K):
        dp[i+1][j+1][1] += dp[i][j][1]*9  # すでにN未満が確定している世界線で、jの数を増やすから9倍される
        dp[i+1][j][1] += dp[i][j][1]  # すでにN未満が確定している世界線で、jの数は変えない
        if x > 0:
            dp[i+1][j][1] += dp[i][j][0]  # 新しい桁に0を埋め込んで、N以下になる道を選んだ世界線
            dp[i+1][j+1][1] += dp[i][j][0]*(x-1)  # 新しい桁に1~(x-1)のx-1通りを埋め込んでN以下になる道を選んだ世界線
            dp[i+1][j+1][0] += dp[i][j][0]  # 新しい桁にxを埋め込んでNのままであり続ける世界線
        else:
            dp[i+1][j][0] += dp[i][j][0]  # xが0の時は、Nのままであり続ける世界線は0しか入れようがない
    dp[i+1][K][1] += dp[i][K][1]
    dp[i+1][K][x>0] += dp[i][K][0]
print(sum(dp[len(N)][K]))
a = int(input())
s = input()
if a < 3200:
    print("red")
else:
  	print(b)

### FIXED CODE ###

a = int(input())
s = input()
if a < 3200:
    print("red")
else:
  	print(s)
n, k = map(int, input().split())
A = list(map(int, input().split()))
c = 1
P = [1]
for i in range(1,k+1):
    c = A[c-1]
    if c in P:
        roop_start = P.index(c)
        roop_num = i- roop_start
        break
    P.append(c)
    if i == k:
        roop_start = '8'
        roop_num = 'b'
if roop_start == '8':
    a = k
    roop_start = 0
else:
    a = (k - roop_start) %  roop_num
b = P[a + roop_start]
print(b)

### FIXED CODE ###

s = input()
t = input()
if s == t[:-1]:
    print('Yes')
else:
    print('No')
import numpy as np
a = input()
a, b, c, d = [int(i) for i in a.split(" ")]
num = np.arange(a, b)
print((num % (c * d) == 0).sum())

### FIXED CODE ###

import fractions

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

a = input()
a, b, c, d = [int(i) for i in a.split(" ")]
dc = (b // c) - ((a-1) // c)
dd = (b // d) - ((a-1)  // d)
dcd = (b // lcm(c, d)) - ((a-1) // lcm(c, d))
print((b - a) + 1 - (dc + dd - dcd))