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

import sys
sys.setrecursionlimit(1000000)

n,q = map(int,input().split())
p = []
x = []
arr = [[] for i in range(n)]
ans = [0 for i in range(n)]
omosa = [0 for i in range(n)]

for i in range(n-1):
    a,b = map(int,input().split())
    arr[a-1].append(b-1)
    arr[b-1].append(a-1)
for i in range(q):
    tmpp,tmpx = map(int,input().split())
    p.append(tmpp-1)
    x.append(tmpx)

for i in range(q):
    omosa[p[i]] +=x[i]

def dfs(start, oya, weight): #weightは自分より上のノードの重さの和
    ans[start] = weight + omosa[start]
    for child in arr[start]:
        if child != oya:
            dfs(child, start, ans[start])
 
dfs(0,-1,0)
print(*ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
readline = sys.stdin.readline #文字列入力のときは注意

n,q = [int(i) for i in readline().split()]
p = []
x = []
arr = [[] for i in range(n)]
ans = [0 for i in range(n)]
omosa = [0 for i in range(n)]

for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    arr[a-1].append(b-1)
    arr[b-1].append(a-1)
for i in range(q):
    tmpp,tmpx = [int(i) for i in readline().split()]
#    p.append(tmpp-1)
#    x.append(tmpx)
    omosa[tmpp-1] += tmpx

#for i in range(q):
#    omosa[p[i]] +=x[i]

def dfs(start, oya, weight): #weightは自分より上のノードの重さの和
    ans[start] = weight + omosa[start]
    for child in arr[start]:
        if child != oya:
            dfs(child, start, ans[start])
 
dfs(0,-1,0)
print(*ans)
### BUGGY CODE ###

N = int(input())
S = []
for _ in range(N):
    S.append(input())
#2-3-1. 最初にすべて読み込む必要がある場合 - 行列、グリッド

[x for x in set(S) if S.count(x) > 1]
#重複した要素を抽出し、新たなリストを生成

print(len(set(S)))

### FIXED CODE ###

N = int(input())
S = []
for _ in range(N):
    S.append(input())
#2-3-1. 最初にすべて読み込む必要がある場合 - 行列、グリッド

print(len(set(S)))
### BUGGY CODE ###

n, k = map(int,input().split())
li = list(map(int,input().split()))
ans = [1]

for i in range(n):
    now = ans[-1]
    nex = li[now-1]
    if ans.count(nex) > 0: #循環判定
        a = ans.index(nex) #開始点
        b = ans.index(now)-a+1 #循環周期
        break
    ans.append(li[now-1])

if k <= a:
    print(ans[k])
else:
    x = (k-a)%b
    print(ans[a+x])

### FIXED CODE ###

n, k = map(int,input().split())
li = list(map(int,input().split()))
ans = [1]
nex = 1
f = [1]+[0]*(n-1)

for i in range(n):
    now = nex #今の場所
    nex = li[now-1] #テレポート先の場所
    #print(now,nex)
    if f[nex-1] == 1: #循環判定
        a = ans.index(nex) #開始点
        b = ans.index(now)-a+1 #循環周期
        break
    f[now-1] = 1
    ans.append(li[now-1])

#print(ans)
#print(f)
if k <= a:
    print(ans[k])
else:
    x = (k-a)%b
    print(ans[a+x])
### BUGGY CODE ###

import math
N=int(input())

n=math.floor(math.sqrt(N))

for n in range(1,N+1):
    ans=0
    flag=False
    for x in range(1,n ):
        for y in range(1, n):
            for z in range(1, n):
                a=x**2+y**2+z**2+x*y+y*z+z*x
                if a==n:
                    ans+=1
                if a>n:
                    break
  
                    
    print(ans)

### FIXED CODE ###

n=int(input())
ans=[0 for _ in range(10001)]

for x in range(1,101):
  for y in range(1,101):
    for z in range(1,101):
      v=x*x+y*y+z*z+x*y+y*z+z*x
      if v<10001:
        ans[v]+=1

for i in range(n):
  print(ans[i+1])
### BUGGY CODE ###

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

sum_num = 0
for i in range(N-1):
  for j in range(i+1, N):
    sum_num += int_list[i] * int_list[j]
    
print(sum_num % (10 ** 9 + 7))

### FIXED CODE ###

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

sum_num = 0
sum_temp = sum(int_list[1:])

for i in range(N-1):
  sum_num += int_list[i] * sum_temp
  sum_temp -= int_list[i+1]
    
print(sum_num % (10 ** 9 + 7))
### BUGGY CODE ###

# 本当はBITやセグメントツリーを用いた解法を使いたいところ...(理解不足)

import bisect
from collections import defaultdict

N = int(input())
# 書き換える時に文字列だと不便なのでリスト化しておく
S = list(input())
Q = int(input())

# setは順序を保証しない、setで管理するとクエリ2で（リスト化した後に）ソートする必要がある
# 最初からlistで管理して、クエリ1ではソート済になるように挿入する
dict = defaultdict(list)
for i in range(N):
    dict[S[i]].append(i)

ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)

    if a == 1:
        b = int(b) - 1
        # 書き換える必要がない場合
        if S[b] == c:
            continue
        else:
            # クエリ2が飛んできた時に毎回ソートしていては間に合わない
            # クエリ1の時点でソート済にしておく
            # 二分探索の際、同じ数字が既にあることはないので、leftでもrightでも良い
            dict[S[b]].remove(b)
            idx = bisect.bisect(dict[c], b)
            dict[c].insert(idx, b)
            # 文字列の書き換え
            S[b] = c

    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        # 文字が何種類あるか
        char_cnt = 0
        for key, value in dict.items():
            # left,rightを指定する必要がある
            x1 = bisect.bisect_left(value, b)
            x2 = bisect.bisect_right(value, c)
            if x2 - x1 > 0:
                char_cnt += 1
        ans.append(char_cnt)

for i in ans:
    print(i)


### FIXED CODE ###

# test!!!!!!!!!!!

from bisect import bisect_left, bisect_right

N = int(input())

S = list(input())

Q = int(input())

memo = {chr(ord('a') + i): [] for i in range(26)}

for key,val in enumerate(S):
    memo[val].append(key)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1])-1, query[2]
        now = S[i]
        if now == x:
            continue
        memo[now].remove(i)
        next_i = bisect_left(memo[x], i)
        memo[x].insert(next_i, i)
        S[i] = x
    else:
        start, end = int(query[1])-1, int(query[2])-1
        tmp_cout = 0
        for alf_array in memo.values():
            if len(alf_array) == 0:
                continue
            ss = bisect_left(alf_array, start)
            gg = bisect_right(alf_array, end)
            if gg- ss > 0:
                tmp_cout += 1
        print(tmp_cout)
### BUGGY CODE ###

import fractions
import numpy as np
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N = int(input())
A = [int(x) for x in input().split()]
a = 1
MOD = 10**9+7
for i in A:
  if a%i==0:
    continue
  a = lcm(a,i)
ans = 0
A =np.array(A)
ans = np.sum(a//A)
print(ans%MOD)

### FIXED CODE ###

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N = int(input())
A = [int(x) for x in input().split()]
a = 1
MOD = 10**9+7
for i in A:
  a = lcm(a,i)
ans = 0
for i in A:
  ans += (a//i)
print(ans%MOD)
### BUGGY CODE ###

N, X, Y = map(int, input().split())
d_list = []
for i in range(1, N+1):
    for j in range(i+1, N+1):
        distance = min([abs(i-j), abs(X-i)+1+abs(j-Y), abs(Y-i)+1+abs(j-X)])
        d_list.append(distance)

for i in range(1,N):
    print(d_list.count(i))


### FIXED CODE ###

N, X, Y = map(int, input().split())
d_list = [0]*N
for i in range(1, N+1):
    for j in range(i+1, N+1):
        distance = min([abs(i-j), abs(X-i)+1+abs(j-Y), abs(Y-i)+1+abs(j-X)])
        d_list[distance]+=1

for i in range(1,N):
    print(d_list[i])
### BUGGY CODE ###

N=int(input())
H=list(map(int, input().split()))
c=0
for i in range(N-1):
  if H[i]-min(H[i+1:])>1:
    c=1
    break
print('Yes' if c==0 else 'No')

### FIXED CODE ###

N=int(input())
H=list(map(int, input().split()))
for i in range(N-1):
  if H[N-i-2]-H[N-i-1]==1:
    H[N-i-2]-=1
  elif H[N-i-2]-H[N-i-1]>1:
    print('No')
    exit()
print('Yes')
### BUGGY CODE ###

H, W, K = map(int, input().split())
S = [list(input()) for _ in range(H)]

res = 10**9

for i in range(2**(H-1)):
    yoko = []
    for j in range(H-1):
        if (i>>j) & 1:
            yoko.append(j+1)
    yoko.append(H)
    
    sen = len(yoko)-1

    rS = [[0]*W for _ in range(sen+1)]

    flag = False

    for w in range(W):
        b = 0
        for j in range(sen+1):
            t = b
            b = yoko[j]
            for h in range(t, b):
                if S[h][w] == "1":
                    rS[j][w] += 1
            if rS[j][w] > K:
                flag = True
                break
        if flag:
            break
    
    if flag:
        continue
    
    x = [r[0] for r in rS]
    for w in range(1, W):
        for h in range(len(yoko)):
            x[h] += rS[h][w]
            if x[h] > K:
                x = [r[w] for r in rS]
                sen += 1
                break
    
    res = min(sen, res)
    if res == 0:
        break

print(res)

### FIXED CODE ###

H, W, K = map(int, input().split())
S = [list(input()) for _ in range(H)]

res = 10**9

for i in range(2**(H-1)):
    yoko = []
    for j in range(H-1):
        if (i>>j) & 1:
            yoko.append(j+1)
    yoko.append(H)
    
    sen = len(yoko)-1

    rS = [[0]*W for _ in range(sen+1)]

    flag = False

    for w in range(W):
        b = 0
        for j in range(sen+1):
            t = b
            b = yoko[j]
            for h in range(t, b):
                if S[h][w] == "1":
                    rS[j][w] += 1
            if rS[j][w] > K:
                flag = True
                break
        if flag:
            break
    
    if flag:
        continue
    
    x = [r[0] for r in rS]
    for w in range(1, W):
        for h in range(len(yoko)):
            x[h] += rS[h][w]
            if x[h] > K:
                x = [r[w] for r in rS]
                sen += 1
                break
    
    res = min(sen, res)
    if res == 0:
        break

print(res)
### BUGGY CODE ###

# import numpy as np
from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[input() for _ in range(H)]
# 後の条件分岐を簡略化するためワープしても迷路外に出ないように壁で囲む
S = ['##{}##'.format(row) for row in S]
S.insert(0, '##{}##'.format('#' * W))
S.insert(0, '##{}##'.format('#' * W))
S.append('##{}##'.format('#' * W))
S.append('##{}##'.format('#' * W))


MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W+4)] for _ in range(H+4)]
# Cost = np.full((H,W),MAX_COST)

# print(S)

ans = -1

cost0 = deque()

cost0.append((CH+1,CW+1,0))
Cost[CH+1][CW+1] = 0;

# used = set()
walk=[(1,0),(0,1),(-1,0),(0,-1)]
warp = [ (i,j) for i in range(-2,3,1) for j in range(-2,3,1) ]
# print(warp)

cost1 = deque()

while 0 < len(cost0):
	h,w,c=cost0.popleft()
	cost1.append((h,w,c))

	for i,j in walk:
		if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
			Cost[h+i][w+j] = c
			# print("updl ", i,j,h+i,w+j,c)
			cost0.appendleft((h+i,w+j,Cost[h+i][w+j]))

	if len(cost0) == 0:

		while 0 < len(cost1):
			h,w,c=cost1.popleft()
			# print(h,w,c)
			for i,j in warp:
				# print(i,j)
				if S[h+i][w+j] == '.':
					if c + 1 < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c + 1
						cost0.append((h+i,w+j,Cost[h+i][w+j]))


if Cost[DH+1][DW+1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH+1][DW+1])

### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

walk=[(1,0),(0,1),(-1,0),(0,-1)]

# used = set()

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in walk:
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
				Cost[h+i][w+j] = c
				# print("updl ", i,j,h+i,w+j,c)
				deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
	for i in range(-2,3,1):
		for j in range(-2,3,1):
			# print(i,j)
			if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
				if S[h+i][w+j] == '.':
					if c + 1 < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c + 1
						deq.append((h+i,w+j,Cost[h+i][w+j]))
						# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])
### BUGGY CODE ###

L,R = map(int,input().split())
ans = 2019
for j in range(R+1):
    for i in range(L,j):
        ans = min(ans,(i*j)%2019)
        if ans == 0:
            break
print(ans)


### FIXED CODE ###

L,R = map(int,input().split())
ans = 2018
for i in range(L,R):
    for j in range(i+1,R+1):
        ans = min(ans,(i*j)%2019)
        if ans == 0:
            print(0)
            exit()
print(ans)
### BUGGY CODE ###

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

i=0
r="YES"

while(i<l):
  j=i
  while(j<l):
    if(i!=j):
      if(list[i]==list[j]):
        r="NO"
    j+=1
  i+=1

print(r)

### FIXED CODE ###

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

def has_duplicates(seq):
    return len(seq) != len(set(seq))

r=has_duplicates(list)

if(str(r)=="False"):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

import sys
import collections
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nl()
A=nl()

for i in range(M):
    inds=A.index(max(A))
    A[inds]=A[inds]//2

print(sum(A))    

### FIXED CODE ###

import sys
import heapq
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nm()
A=nl()
h=[]
for i in A:
    heapq.heappush(h,-1*i)

for i in range(M):
	maxval=heapq.heappop(h)
	heapq.heappush(h,-(-maxval//2))
    
print(-sum(h))
### BUGGY CODE ###

K,S = [int(i) for i in input().split()]
count = 0
for x in range(0,K+1):
	for y in range(0,K+1):
		for z in range(0,K+1):
			if x > y:
				continue
			elif y > z:
				continue
			elif x > z:
				continue
			else:
				if x + y + z == S:
					if  x == y and y == z:
						count += 1
					elif (x-y)*(y-z)*(z-x) == 0:
						count += 3
					else:
						count += 6

						
print(count)

### FIXED CODE ###

K,S = [int(i) for i in input().split()]
count = 0
for z in range(0,K+1):
	for y in range(0,K+1):
			if 0 <= S-y-z <= K:
				count += 1
print(count)
### BUGGY CODE ###

import numpy as np
N, Q = map(int, input().split())
# print(N, Q)
S = input()
AC_array = np.array([
    1 if (S[i] == "A" and S[i + 1] == "C") else 0 for i in range(N - 1)
])
lr_array = [list(map(int, input().split())) for i in range(Q)]
# print(lr_array)
# print(AC_array)
for lr in lr_array:
    print(np.sum(AC_array[lr[0]-1:lr[1]-1]))

### FIXED CODE ###

N, Q = map(int, input().split())
# print(N, Q)
S = input()
lr_array = [list(map(int, input().split())) for i in range(Q)]
AC_array = []
AC_count = 0

# print(S)
for i, s in enumerate(S):
    if i == 0:
        s_old = s
        continue
    if s_old == "A" and s == "C":
        AC_count += 1
    AC_array.append(AC_count)
    s_old = s

# print(lr_array)
# print(AC_array)
ans = ""
for lr in lr_array:
    ans += str(AC_array[lr[1] - 2] -
               (AC_array[lr[0] - 2] if lr[0] > 1 else 0)) + "\n"
print(ans[:-1])
### BUGGY CODE ###

n = int(input())
ans = []


def xyz():
    count = 0
    for i in range(1, 101):
        for j in range(1, 101):
            for k in range(1, 101):
                zyx = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i
                ans.append(zyx)


xyz()
for i in range(n):
    print(ans.count(i + 1))


### FIXED CODE ###

n = int(input())
ans = [0]*10**5


def xyz():
    count = 0
    for i in range(1, 101):
        for j in range(1, 101):
            for k in range(1, 101):
                zyx = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i
                ans[zyx] += 1


xyz()
for i in range(n):
    print(ans[i+1])
### BUGGY CODE ###

#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())

graph = [[mod for i in range(N)] for i in range(N)]
for i in range(N):
    graph[i][i] = 0

roots = [[] for i in range(N)]
for i in range(N - 1):
    a, b, c = LI()
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c
    roots[a].append(b)
    roots[b].append(a)

Q, K = LI()
K -= 1
xy = [0 for i in range(Q)]
for i in range(Q):
    x, y = LI()
    x -= 1
    y -= 1
    xy[i] = [x, y]
"""
xyzで全部の通りを見つけるとN ** 3で無理
なので今回は木構造に注目してBFS or DFSで解いたらいいのでは？
"""

visited = [-1 for i in range(N)]
queue = collections.deque()
queue.append(K)
visited[K] = 0

while len(queue)> 0:
    node = queue.popleft()
    cnt = visited[node]
    for n_node in roots[node]:
        if visited[n_node] == -1:
            visited[n_node] = cnt + graph[node][n_node]
            queue.append(n_node)
for x, y in xy:
    print(visited[x] + visited[y])





### FIXED CODE ###

#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
weights = {}

roots = [[] for i in range(N)]
for i in range(N - 1):
    a, b, c = LI()
    a -= 1
    b -= 1
    roots[a].append(b)
    roots[b].append(a)
    weights[(a,b)] = c
    weights[(b,a)] = c

Q, K = LI()
K -= 1
xy = [0 for i in range(Q)]
for i in range(Q):
    x, y = LI()
    x -= 1
    y -= 1
    xy[i] = [x, y]
"""
xyzで全部の通りを見つけるとN ** 3で無理
なので今回は木構造に注目してBFS or DFSで解いたらいいのでは？
重みを単純にグラフに持つと10**5 ** 2になってしまうので注意
"""

visited = [-1 for i in range(N)]
queue = collections.deque()
queue.append(K)
visited[K] = 0

while len(queue)> 0:
    node = queue.popleft()
    cnt = visited[node]
    for n_node in roots[node]:
        if visited[n_node] == -1:
            visited[n_node] = cnt + weights[(node, n_node)]
            queue.append(n_node)

for x, y in xy:
    print(visited[x] + visited[y])
### BUGGY CODE ###


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

ans = 1
for n in range(1, M // N + 1):
    res = M - n * N
    if res % n == 0:
        ans = n

print(ans)


### FIXED CODE ###

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

divisor = []
for i in range(1, int(M ** 0.5) + 1):
    if M % i == 0:
        divisor.append(i)
        if i != M // i:
            divisor.append(M // i)

print(max(v for v in divisor if v <= M // N))
### BUGGY CODE ###

import itertools

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

ab = []
for ax, bx in itertools.product(a, b):
    ab.append(ax+bx)
ab.sort(reverse=True)
s_ab = ab[0:min(3000,len(ab))]

abc = []
for aby, cy in itertools.product(s_ab, c):
    abc.append(aby+cy)
abc.sort(reverse=True)
s_abc = abc[0:min(3000,len(abc))]

for i in range(k[3]): print(s_abc[i])


### FIXED CODE ###

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

A = sorted(a, reverse=True)[:k[3]]
B = sorted(b, reverse=True)[:k[3]]
C = sorted(c, reverse=True)[:k[3]]

ab = sorted(list(ax+bx for ax in A for bx in B), reverse=True)[:k[3]]
abc = sorted(list(aby+cy for aby in ab for cy in C), reverse=True)[:k[3]]
for i in abc: print(i)
### BUGGY CODE ###

from collections import Counter
import itertools

N = int(input())
moji_lis = list()
 
def verify_anagrams(first_word, second_word):
    def get_counter(s):
        return Counter(s.upper().replace(' ', ''))
 
    return get_counter(first_word) == get_counter(second_word)

for i in range(N):
    moji_lis.append(input())
    
p = itertools.combinations(moji_lis, 2)
ans = 0
for j in p:
    if verify_anagrams(j[0], j[1]):
        ans +=1
print(ans)

### FIXED CODE ###

N = int(input())
 
dic = {}
ans = 0
for i in range(N):
    s = tuple(sorted(input()))
    if s in dic:
        ans += dic[s]
        dic[s] += 1
    else:
        dic[s] = 1
print(ans)
### BUGGY CODE ###


N=int(input())
number_of_withdrawal=[]

def floor(float_number):
    integer = 0
    while integer < float_number:
        integer+=1
    if integer == float_number:
        return integer
    else:
        integer-=1
        return integer

for money_6 in range(0, N+1):
    money_9 = N-money_6

    i=0
    count_6_pow_number=0
    while pow(6,i)<=money_6:
        count_6_pow_number += (floor(money_6/pow(6,i)))%6
        i+=1
    j=0
    count_9_pow_number=0
    while pow(9,j)<=money_9:
        count_9_pow_number += (floor(money_9/pow(9,j)))%9
        j+=1

    # print(money_6, money_9, sum(count_6_pow_number), sum(count_9_pow_number))
    number_of_withdrawal.append(count_6_pow_number+count_9_pow_number)


print(min(number_of_withdrawal))

### FIXED CODE ###

import math

N=int(input())
number_of_withdrawal=[100000]

# def floor(float_number):
#     integer = 0
#     while integer < float_number:
#         integer+=1
#     if integer == float_number:
#         return integer
#     else:
#         integer-=1
#         return integer

for money_6 in range(0, N+1):
    money_9 = N-money_6

    i=0
    count_6_pow_number=0
    while pow(6,i)<=money_6:
        count_6_pow_number += (math.floor(money_6/pow(6,i)))%6
        i+=1
    j=0
    count_9_pow_number=0
    while pow(9,j)<=money_9:
        count_9_pow_number += (math.floor(money_9/pow(9,j)))%9
        j+=1

    # print(money_6, money_9, sum(count_6_pow_number), sum(count_9_pow_number))
    number_of_withdrawal.append(count_6_pow_number+count_9_pow_number)

print(min(number_of_withdrawal))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**7)

# input & solve
N, Q = map(int, input().split())

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

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

def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)

dfs(0)

# output
print(*ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10 ** 7)

# input & solve
input = sys.stdin.readline
N, Q = map(int, input().split())

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

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

def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)

dfs(0)

# output
print(*ans)
### BUGGY CODE ###

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a = [0]
b = [0]
for i in range(n):
    a.append(a[i] + A[i])
for i in range(m):
    b.append(b[i] + B[i])
ans = 0

for i in range(n+1):
    if a[i] > k:
        break
    for j in range(m+1):
        if a[i] + b[j] <= k:
            ans = max(ans, i+j)
        
print(ans)

### FIXED CODE ###

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a = [0]
b = [0]
for i in range(n):
    a.append(a[i] + A[i])
for i in range(m):
    b.append(b[i] + B[i])

ans = 0

for i in range(n + 1):
    if a[i] > k:
        break
    while  a[i] + b[m] > k:
        m -= 1
    ans = max(ans, i + m)

print(ans)