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

x, y, z, k = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
c = list(map(int, input().split(' ')))
ab = []
for i in a:
    for j in b:
        ab.append(i+j)
ab.sort(reverse = True)
abc = []
ab = ab[:k+1]
k_1 = min([len(ab), k])
for i in ab:
    for j in c:
        abc.append(i+j)
abc.sort(reverse = True)
for i in range(k):
    print(abc[i])

### FIXED CODE ###

import heapq
import sys
x, y, z, k = map(int, input().split())

a, b, c = (sorted(map(int, sys.stdin.readline().split()), reverse=True) for _ in range(3))

abc = {(0,0,0)}

stu = [[-a[0]-b[0]-c[0], 0,0,0]]
heapq.heapify(stu)
result = []
while k > 0:
    out_p, n, m, l = heapq.heappop(stu)
    if n+1<x and not((n+1,m,l) in abc):
        abc.add((n+1,m,l))
        heapq.heappush(stu, [-a[n+1]-b[m]-c[l], n+1, m, l])
    if m+1<y and not((n,m+1,l) in abc):
        abc.add((n,m+1,l))
        heapq.heappush(stu, [-a[n]-b[m+1]-c[l], n, m+1, l])
    if l+1<z and not((n,m,l+1) in abc):
        abc.add((n,m,l+1))
        heapq.heappush(stu, [-a[n]-b[m]-c[l+1], n, m, l+1])
    result.append(-out_p)
    k -= 1
result.sort(reverse=True)
for i in result:
    print(i)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
s = read().rstrip().decode()
cnt = 0
for i in range(1000):
    num = ''
    if i < 100:
        num += '0'
        if i < 10:
            num += '0'
    num += str(i)
    index = 0
    for ss in s:
        if ss == num[index]:
            index += 1
            if index == 3:
                cnt += 1
                break
print(cnt)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
s = input()
ans = 0

for i in range(1000):
    cnt = 0
    if i < 100:
        if i < 10:
            match = '00' + str(i)
        else:
            match = '0' + str(i)
    else:
        match = str(i)

    for S in s:
        if S == match[cnt]:
            cnt += 1

        if cnt == 3:
            ans += 1
            break

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

n = int(input())
l = list(map(int, input().split()))
count = 0
while all(i % 2 == 0 for i in l):
    a = [i/2 for i in l]
    count += 1
print(count)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
cnt = 0
while all(i % 2 == 0 for i in a):
    a = [i/2 for i in a]
    cnt += 1
print(cnt)
### BUGGY CODE ###

def resolve():
  N = int(input())
  X = input()
  base_1_count = X.count("1")
  X_int = int(X, 2)

  for i in range(N):
    first_1_count = base_1_count
    if X[i] == "1":
      first_1_count -= 1
      Xi = X_int - 2**(N-i-1)
    else:
      first_1_count += 1
      Xi = X_int + 2**(N-i-1)
    count = 0
    num_of_1 = first_1_count
    while Xi != 0:
      Xi = Xi % num_of_1
      num_of_1 = bin(Xi).count("1")
      count += 1
    print(count)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
  N = int(input())
  X = input()

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = pow(2, N-i-1, base_1_count-1)
      if X_int_m <= pow_2:
        Xi = X_int_m - pow_2 + base_1_count-1
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + pow(2, N-i-1, base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    print(count)

if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

# import sys
# import math
# import decimal
# import queue
# import bisect
# import heapq # priolity-queue
# import time
# import itertools
# import collections # queue
# from operator import itemgetter
# from fractions import Fraction

mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

def main():
    n = int(input())
    a = list(map(int,input().split()))
    mp = {}
    for i in range(n):
        if a[i] in mp.keys():
            mp[a[i]] += 1
        else:
            mp[a[i]] = 1
    for i in range(n):
        ans = 0
        for k in mp.keys():
            x = mp[k]
            if k==a[i]:
                x -= 1
            ans += x * (x - 1) // 2
        print(ans)
    return

if __name__=='__main__':
    main()


### FIXED CODE ###

# import sys
# import math
# import decimal
# import queue
# import bisect
# import heapq # priolity-queue
# import time
# import itertools
# import collections # queue
# from operator import itemgetter
# from fractions import Fraction

mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

def main():
    n = int(input())
    a = list(map(int,input().split()))
    mp = {}
    for i in range(n):
        if a[i] in mp.keys():
            mp[a[i]] += 1
        else:
            mp[a[i]] = 1
    res = 0
    b = [0] * (n + 1)
    for k in mp.keys():
       x = mp[k] * (mp[k] - 1) // 2
       res += x
       b[k] = x - (mp[k] - 1) * (mp[k] - 2) // 2
    for i in range(n):
        print(res - b[a[i]])
    return

if __name__=='__main__':
    main()
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))

q=[]

for i in p:
  q+=[(i+1)/2]

ans=0

for i in range(n-k+1):
  ans=max(ans,sum(q[i:i+k]))
  
print(ans)


### FIXED CODE ###

import itertools

n,k=map(int,input().split())
a=list(map(int,input().split()))
a=list(map(lambda x:(x+1)/2,a))

a=[0]+list(itertools.accumulate(a))
ans=0

for i in range(n-k+1):
  ans=max(ans,a[i+k]-a[i])
  
print(ans)
### BUGGY CODE ###

from sys import stdin

N = int(stdin.readline())
A = list(map(int, stdin.readline().split()))

ans = 1

if 0 in A:
    ans = 0

if ans:
    for a in A:
        ans *= a
        if ans > pow(10, 18):
            ans = -1

print(ans)

### FIXED CODE ###

from sys import stdin

N = int(stdin.readline())
A = list(map(int, stdin.readline().split()))

ans = 1

if 0 in A:
    ans = 0

if ans:
    for a in A:
        ans *= a
        if ans > pow(10, 18):
            ans = -1
            break

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

import numpy as np
import itertools

k,s = map(int, input().split())
l = np.arange(k+1)

p = np.array(list(itertools.product(l,repeat=3)))

print(np.count_nonzero(np.sum(p,axis=1)==s))

### FIXED CODE ###

k,s = map(int, input().split())
ans = 0

for x in range(k+1):
  for y in range(k+1):
    if 0<=s-x-y and s-x-y <=k:
      ans+=1
print(ans)
### BUGGY CODE ###

s=input()
a=s.find("A")
z0=s.count("Z")
for i in range (z0-1):
    s=s[:s.find("Z")]+"a"+s[s.find("Z")+1:]
z=s.find("Z")
print(z-a+1)
    

### FIXED CODE ###

s=input()
for i in range(len(s)):
    if s[i]=="A":
        a=i
        break
for j in range(len(s)):
    if s[-j-1]=="Z":
        z=(len(s)-j)
        break
print(z-a)
### BUGGY CODE ###

# coding: utf-8
N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [float('inf')]*N
dp[0] = 0

for i in range(1, N):
    dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i-K, 0), i))

print(dp[N-1])


### FIXED CODE ###

def test():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    dp = [float('inf')]*N
    dp[0] = 0

    for i in range(1, N):
        dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i-K, 0), i))

    print(dp[-1])

if __name__ == '__main__':
    test()
### BUGGY CODE ###

n = int(input())
val = 1
for num in range(0,n):
    val *= num+1
else:
    print (val % (10**9 + 7))

### FIXED CODE ###

import math
n = int(input())
val = math.factorial(n)
print (val % (10**9 + 7))
### BUGGY CODE ###

#coding: utf-8
from math import ceil, floor
X = int(input())
a = floor(X**(1/5))
while True:
    b = (a**5 - X)
    if a**5 - b**5 == X:
        print(a,b)
        exit()
    # if (a**5 - X) < 0:
    #     pass
    # elif int((a**5 - X)**(1/5)) == (a**5 - X)**(1/5):
    #     print(a, int((a**5 - X)**(1/5)))
    #     exit()
    a += 1



### FIXED CODE ###

#coding: utf-8
X = int(input())
for a in range(-118, 120, 1):
    for b in range(-118, 120, 1):
        if a ** 5 - b ** 5 == X:
            print(a, b)
            exit()
### BUGGY CODE ###

N=int(input())
A=[int(input())-1 for _ in range(N)]
B=[]
i=0
while(1):
    if i not in B:
        B.append(i)
        i=A[i]
        if i==1:
            print(len(B))
            break
    else:
        print(-1)
        break

### FIXED CODE ###

N=int(input())
a=[int(input()) for _ in range(N)]
flag=0
b=1
for i in range(N):
    b=a[b-1]
    if b==2:
        print(i+1)
        flag=1
        break
if flag==0:
    print(-1)
### BUGGY CODE ###

x = int(input())
a = 0
b = 0
for i in range(-1000, 1000):
    for j in range(-1000, 1000):
        if (i ** 5) - (j ** 5) == x:
            a = i
            b = j
            break
print("{} {}".format(a, b))


### FIXED CODE ###

x = int(input())
a = 0
b = 0
for i in range(-500, 500):
    for j in range(-500, 500):
        if (i ** 5) - (j ** 5) == x:
            a = i
            b = j
            break
print("{} {}".format(a, b))
### BUGGY CODE ###

n = int(input())
b = list(map(str, input().split()))
''.join(b)
ans = []
def dfs(b):
    if len(b) == 1:
        if int(b[0]) == 1:
            return True
    else:
        for i in range(len(b)):
            if int(b[i]) == i + 1:
                if i == 0:
                    if dfs(b[1:]):
                        ans.append(i + 1)
                        return True
                else:
                    if dfs(b[:i] + b[i+1:]):
                        ans.append(i + 1)
                        return True
        return False
if dfs(b):
    ans.insert(0, 1)
    for i in range(len(ans)):
        print(ans[i])
else:
    print(-1)


### FIXED CODE ###

n = int(input())
b = list(map(int, input().split()))
ans = []
while(len(b) != 1):
    count = 0
    for i in range(len(b) - 1, -1, -1):
        if b[i] == i + 1:
            b.pop(i)
            ans.append(i + 1)
            count = 0
            break
        else:
            count += 1
    if count == len(b):
        print(-1)
        exit()
if b[0] == 1:
    ans.append(1)
    ans = list(reversed(ans))
    for i in range(len(ans)):
        print(ans[i])
else:
    print(-1)
### BUGGY CODE ###

import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]

while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) & ( p[1] == y2):break
  for i in range(4):
    for ki in range(1,k+1):
      nx = p[0] + dx[i]*ki
      ny = p[1] + dy[i]*ki
      if (nx<0) | (nx>(h-1))| (ny<0) | (ny>(w-1)):break
      if dp[nx][ny] == -1:break
      if 0 < dp[nx][ny] <= dp[p[0]][p[1]]:break
      dp[nx][ny] = dp[p[0]][p[1]] + 1
      if (nx == x2) & ( ny == y2):exit(print(dp[x2][y2]-1))
      heapq.heappush(que, (dp[nx][ny], [nx,ny]))

if dp[x2][y2] != 0:
  print(dp[x2][y2]-1)
else:
  print(-1)


### FIXED CODE ###

#import heapq
from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
dp = [[-1]*w for _ in range(h)]
#que = []
que = deque()
c = [input() for _ in range(h)]

dp[x1][y1] = 0
#heapq.heappush(que, (dp[x1][y1], [x1,y1]))
que.append((x1,y1))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  x,y=que.popleft()
  if x==x2 and y==y2:
    exit(print(dp[x][y]))
  for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      xx=x+dx*i
      yy=y+dy*i
      if not(0<=xx<h and 0<=yy<w) or c[xx][yy]=="@":break
      if 0<=dp[xx][yy]<=dp[x][y]:break
      if dp[xx][yy]==-1:que.append((xx,yy))
      dp[xx][yy]=dp[x][y]+1
print(-1)
### BUGGY CODE ###

import collections
def bfs(G,l):
    l.append([1,1])
    visited = [[0] * len(G[0]) for i in range(len(G))]
    chk = 0
    G[1][1] = 0
    while(len(l)):
        now = l.popleft()
        visited[now[0]][now[1]] = 1
        if now == [len(G)-2,len(G[0])-2]:
            chk = 1

        if G[now[0]][now[1]+1] != "#" and visited[now[0]][now[1]+1] == 0:
            l.append([now[0],now[1]+1])
            G[now[0]][now[1]+1] = min(G[now[0]][now[1]] + 1,G[now[0]][now[1]+1])

        if G[now[0]][now[1]-1] != "#" and visited[now[0]][now[1]-1] == 0:
            l.append([now[0],now[1]-1])
            G[now[0]][now[1]-1] = min(G[now[0]][now[1]] + 1,G[now[0]][now[1]-1])

        if G[now[0]+1][now[1]] != "#" and visited[now[0]+1][now[1]] == 0:
            l.append([now[0]+1,now[1]])
            G[now[0]+1][now[1]] = min(G[now[0]][now[1]] + 1,G[now[0]+1][now[1]])

        if G[now[0]-1][now[1]] != "#" and visited[now[0]-1][now[1]] == 0:
            l.append([now[0]-1,now[1]])
            G[now[0]-1][now[1]] = min(G[now[0]][now[1]]+1,G[now[0]-1][now[1]])
    return chk

[h,w] = [int(i) for i in input().split()]
s = [["#"] * (w+2)]
whites = 0
for i in range(h):
    ls = ["#"]
    tmp = input()
    for j in range(len(tmp)):
        if tmp[j] == ".":
            ls.append(200)
        else:
            ls.append(tmp[j])
    ls.append("#")
    whites += tmp.count(".")
    s.append(ls)
s.append(["#"] * (w+2))
l = collections.deque()

if bfs(s,l):
    print(whites - s[h][w]-1)
    """
    for i in range(h+2):
        for j in range(w+2):
            print(s[i][j],end = ",")
        print()
    """
else:
    print(-1)
#print(s)


### FIXED CODE ###

import collections
import time
def bfs(G,l):
    l.append([1,1])
    visited = [[0] * len(G[0]) for i in range(len(G))]
    chk = 0
    G[1][1] = 0
    while(len(l)):
        [n0,n1] = l.popleft()
        if visited[n0][n1] == 1:
            continue
        else:
            visited[n0][n1] = 1
        if [n0,n1] == [len(G)-2,len(G[0])-2]:
            chk = 1
            break
        if G[n0][n1+1] != "#" and visited[n0][n1+1] == 0:
            l.append([n0,n1+1])
            G[n0][n1+1] = min(G[n0][n1] + 1,G[n0][n1+1])

        if G[n0][n1-1] != "#" and visited[n0][n1-1] == 0:
            l.append([n0,n1-1])
            G[n0][n1-1] = min(G[n0][n1] + 1,G[n0][n1-1])

        if G[n0+1][n1] != "#" and visited[n0+1][n1] == 0:
            l.append([n0+1,n1])
            G[n0+1][n1] = min(G[n0][n1]+1,G[n0+1][n1])

        if G[n0-1][n1] != "#" and visited[n0-1][n1] == 0:
            l.append([n0-1,n1])
            G[n0-1][n1] = min(G[n0][n1]+1,G[n0-1][n1])
        #print(n0,n1)
    return chk

[h,w] = [int(i) for i in input().split()]
st = time.time()
s = [["#"] * (w+2)]
whites = 0
for i in range(h):
    ls = ["#"]
    tmp = input()
    for j in range(len(tmp)):
        if tmp[j] == ".":
            ls.append(200)
        else:
            ls.append(tmp[j])
    ls.append("#")
    whites += tmp.count(".")
    s.append(ls)
s.append(["#"] * (w+2))
l = collections.deque()
#print(time.time() - st)
if bfs(s,l):
    print(whites - s[h][w]-1)

else:
    print(-1)
#print(time.time() - st)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Oct 20 10:21:00 2018
ABC077C
@author: maezawa
"""
import bisect

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

a.sort()
b.sort()
c.sort()

cnt = 0
for ci in c:
    j = bisect.bisect_left(b, ci)
    for bi in b[:j]:
        k = bisect.bisect_left(a, bi)
        #print(ci, bi, k, cnt)
        cnt += k
print(cnt)
    

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Oct 20 10:21:00 2018
ABC077C
@author: maezawa
"""
import bisect

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

a.sort()
b.sort()
c.sort()

bcnt = [0]*n
for i, bi in enumerate(b):
    j = bisect.bisect_left(a, bi)
    if i == 0:
        bcnt[i] = j
    else:
        bcnt[i] = bcnt[i-1] + j
cnt = 0
for i, ci in enumerate(c):
    j = bisect.bisect_left(b, ci)
    if j == 0:
        continue
    else:
        cnt += bcnt[j-1]
    #print(ci, j, bcnt[j-1], cnt)
    
print(cnt)
### BUGGY CODE ###

K,X,Y = (int(x) for x in input().split())
# distance = [[0] * K for i in range(K-1)]
distance = [0] *( K *(K-1))
ct = 0
for i in range(1,K):
    for j in range (i+1,K+1):
        if i < j:
            distance[ct] = min(j-i,abs(i-X)+abs(j-Y)+1)
            ct += 1
for k in range (1,K):
    print(distance.count(k))

### FIXED CODE ###

K,X,Y = (int(x) for x in input().split())
ans = [0] * K
ct = 0
for i in range(1,K):
    for j in range (i+1,K+1):
            ans[min(j-i,abs(i-X)+abs(j-Y)+1)] += 1
for k in range (1,K):
    print(ans[k])
### BUGGY CODE ###

#!/usr/bin/env python3

from typing import Iterable


def main() -> None:
    N = ri()
    A = rmi()
    max_A = max(A)
    num = tuple(range(1, N + 1))
    cand = 0
    for a in range(N):
        a_height = A[a]
        for b in range(min(a + 1 + a_height, N), N):
            diff_num = b - a
            sum_height = A[a] + A[b]
            if diff_num == sum_height:
                cand += 1
    w(cand)


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> int:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(data: Iterable) -> None:
    print(' '.join(list(map(str, data))))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

from typing import Iterable


def main() -> None:
    N = ri()
    A = rmi()
    num = tuple(range(1, N + 1))
    cand = 0
    log = {}
    for i in range(0, N):
        if i + 1 - A[i] in log:
            cand += log[i + 1 - A[i]]
        if i + 1 + A[i] in log:
            log[i + 1 + A[i]] += 1
        else:
            log[i + 1 + A[i]] = 1
    w(cand)


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> int:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(data: Iterable) -> None:
    print(' '.join(list(map(str, data))))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
S = input()
Q = int(input())

for i in sys.stdin:
    if i[0] == '1':
        S = S[::-1]
    
    elif i[2] == '1':
        S = i[4] + S
    else:
        S = S + i[4]

print(S)

### FIXED CODE ###

import sys
S = input()
Q = int(input())
key = 1

for i in sys.stdin:
    if i[0] == '0':
        break

    if i[0] == '1':
        key = -key
    
    elif key == 1:
        if i[2] == '1':
            S = i[4] + S
        else:
            S = S + i[4]

    else:
        if i[2] == '2':
            S = i[4] + S
        else:
            S = S + i[4]


print(S[::key])
### BUGGY CODE ###

S = input()

S = S.replace("dream",'/*/').replace('erase','/+/')
S = S.split('/')
while '' in S:
    S.remove('')
for i in range(len(S)):
    if S[i] == '*' or S[i] == '+':
        continue
    if S[i] == 'r':
        if i != 0 and S[i-1] == '+':
            continue
    elif S[i] == 'er':
        if i != 0 and S[i-1] == '*':
            continue
    print('NO')
    exit()
print('YES')
            

### FIXED CODE ###

S = input()

S = S.replace("dream",'/*/').replace('erase','/+/')
S = [i for i in S.split('/') if i != '']
for i in range(len(S)):
    if S[i] == '*' or S[i] == '+':
        continue
    if S[i] == 'r':
        if i != 0 and S[i-1] == '+':
            continue
    elif S[i] == 'er':
        if i != 0 and S[i-1] == '*':
            continue
    print('NO')
    exit()
print('YES')
### BUGGY CODE ###

import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

dp = [N] * (N + 1)
dp[0] = 0
for i in range(N):
    dp[i + 1] = min(dp[i + 1], dp[i] + 1)
    six = 6
    nine = 9
    for p in range(20):
        if i + six <= N:
            dp[i + six] = min(dp[i + six], dp[i] + 1)
        if i + nine <= N:
            dp[i + nine] = min(dp[i + nine], dp[i] + 1)
        six *= six
        nine *= nine

print(dp[N])

### FIXED CODE ###

import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

dp = [N] * (N + 1)
dp[0] = 0
for i in range(N):
    dp[i + 1] = min(dp[i + 1], dp[i] + 1)
    six = 6
    nine = 9
    for p in range(10):
        if i + six <= N:
            dp[i + six] = min(dp[i + six], dp[i] + 1)
        if i + nine <= N:
            dp[i + nine] = min(dp[i + nine], dp[i] + 1)
        six *= 6
        nine *= 9

print(dp[N])
### BUGGY CODE ###

from collections import defaultdict

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

h = defaultdict(int)
w = defaultdict(int)
boms = set()

for _ in range(M):
    x, y = map(int, input().split())
    h[x] += 1
    w[y] += 1
    boms.add((x, y))

h_max = max(h.values())
w_max = max(w.values())

h_idx = [x for (x, y) in h.items() if y == h_max]
w_idx = [x for (x, y) in w.items() if y == w_max]

minus = []
for x in h_idx:
    for y in w_idx:
        if (x, y) in boms:
            minus.append(-1)
        else:
            minus.append(0)

print(h_max + w_max + max(minus))

### FIXED CODE ###

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

h = [0] * H
w = [0] * W
boms = set()

for _ in range(M):
    x, y = map(int, input().split())
    h[x - 1] += 1
    w[y - 1] += 1
    boms.add((x, y))

h_max = max(h)
w_max = max(w)

h_idx = [x + 1 for x, y in enumerate(h) if y == h_max]
w_idx = [x + 1 for x, y in enumerate(w) if y == w_max]

minus = -1
for x in h_idx:
    for y in w_idx:
        if not (x, y) in boms:
            minus = 0
            break

print(h_max + w_max + minus)
### BUGGY CODE ###

import sys
import itertools
ans=0
N=int(sys.stdin.readline())
S=sys.stdin.readline()

for i in itertools.combinations(range(N),3):
  if (i[0]+i[2])/2 ==i[1]:
    continue
  L=(S[i[0]],S[i[1]],S[i[2]])
  if len(set(L))!=3:
    continue
  ans+=1
  
print(ans)    


### FIXED CODE ###

N=int(input())
S=input()

r_cnt=S.count('R')
g_cnt=S.count('G')
b_cnt=S.count('B')

ans=r_cnt*g_cnt*b_cnt

for i in range(N):
  for d in range(N):
    j=i+d
    k=j+d
    if k>=N:break
#等号がないと範囲外参照になる、0-indexだからk=S[N]は無い      
    if S[i]!=S[j] and S[i]!=S[k] and S[k]!=S[j]:
      ans-=1
      
print(ans)