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

import sys
input=sys.stdin.readline

r,c,k=map(int,input().split())

item=[[0]*c for i in range(r)]
for i in range(k):
    R,C,v=map(int,input().split())
    item[R-1][C-1]=v

dp=[[[-10**16]*4 for i in range(c)] for j in range(r)]

if item[0][0]==0:
    dp[0][0][0]=0
else:
    dp[0][0][0]=0
    dp[0][0][1]=item[0][0]

for i in range(r):
    for j in range(c):
        if j!=c-1:
            v=item[i][j+1]
            if v==0:
                for k in range(3):
                    dp[i][j+1][k]=max(dp[i][j][k],dp[i][j+1][k])
            else:
                dp[i][j+1][0]=max(dp[i][j][0],dp[i][j+1][0])
                dp[i][j+1][1]=max(dp[i][j][0]+v,dp[i][j][1],dp[i][j+1][1])
                dp[i][j + 1][2] = max(dp[i][j][1] + v, dp[i][j][2], dp[i][j + 1][2])
                dp[i][j + 1][3] = max(dp[i][j][2] + v, dp[i][j][3], dp[i][j + 1][3])
        if i!=r-1:
            v=item[i+1][j]
            if v==0:
                dp[i+1][j][0]=max(dp[i][j][0],dp[i][j][1],dp[i][j][2],dp[i][j][3],dp[i+1][j][0])
            else:
                dp[i + 1][j][0] = max(dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3], dp[i + 1][j][0])
                dp[i + 1][j][1] = max(dp[i][j][0]+v, dp[i][j][1]+v, dp[i][j][2]+v, dp[i][j][3]+v, dp[i + 1][j][1])

ans=max(dp[r-1][c-1][0],dp[r-1][c-1][1],dp[r-1][c-1][2],dp[r-1][c-1][3])
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
    r,c,k=map(int,input().split())

    item=[[0]*c for i in range(r)]
    for i in range(k):
        R,C,v=map(int,input().split())
        item[R-1][C-1]=v

    dp0=[[-10**10]*c  for i in range(r)]
    dp1 = [[-10 ** 10] * c for i in range(r)]
    dp2 = [[-10 ** 10] * c for i in range(r)]
    dp3 = [[-10 ** 10] * c for i in range(r)]

    if item[0][0]==0:
        dp0[0][0]=0
    else:
        dp0[0][0]=0
        dp1[0][0]=item[0][0]

    for i in range(r):
        for j in range(c):
            if j!=c-1:
                v=item[i][j+1]
                if v==0:
                    dp0[i][j+1]=max(dp0[i][j],dp0[i][j+1])
                    dp1[i][j + 1] = max(dp1[i][j], dp1[i][j + 1])
                    dp2[i][j + 1] = max(dp2[i][j], dp2[i][j + 1])
                    dp3[i][j + 1] = max(dp3[i][j], dp3[i][j + 1])
                else:
                    dp0[i][j+1]=max(dp0[i][j],dp0[i][j+1])
                    dp1[i][j+1]=max(dp0[i][j]+v,dp1[i][j],dp1[i][j+1])
                    dp2[i][j + 1] = max(dp1[i][j] + v, dp2[i][j], dp2[i][j + 1])
                    dp3[i][j + 1] = max(dp2[i][j] + v, dp3[i][j], dp3[i][j + 1])
            if i!=r-1:
                v=item[i+1][j]
                if v==0:
                    dp0[i+1][j]=max(dp0[i][j],dp1[i][j],dp2[i][j],dp3[i][j],dp0[i+1][j])
                else:
                    dp0[i+1][j]=max(dp0[i][j],dp1[i][j],dp2[i][j],dp3[i][j],dp0[i+1][j])
                    dp1[i + 1][j] = max(dp0[i][j]+v, dp1[i][j]+v, dp2[i][j]+v, dp3[i][j]+v, dp1[i + 1][j])

    ans=max(dp0[r-1][c-1],dp1[r-1][c-1],dp2[r-1][c-1],dp3[r-1][c-1])
    print(ans)

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

from numba import njit


@njit(fastmath=True)
def fact(x):
    i = 1
    ret = set()
    while i * i <= x:
        if x % i == 0:
            ret.add(i)
            ret.add(x // i)
        i += 1

    return ret


def main():
    n = int(input())
    a = tuple(map(int, input().split()))

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from time import time


def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    now = time()

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        if time() - now >= 1.8:
            print(n)
            exit()

        c[e] += 1

    print(ans)


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

N = int(input())
Sn = []
result = 0
for i in range(N):
    s = input()
    if s in Sn:
        result += 1
    Sn.append(s)
print(N-result)


### FIXED CODE ###

N = int(input())
Sn = []
for i in range(N):
    s = input()
    Sn.append(s)
print(len(set(Sn)))
### BUGGY CODE ###

h, w = map(int, input().split())
diff = [list(map(int, input().split())) for _ in range(h)]
for i in range(h):
    for j, b in enumerate(list(map(int, input().split()))):
        diff[i][j] = abs(diff[i][j] - b)
dp = [[set() for j in range(w+1)] for i in range(h+1)]
dp[1][1].add(diff[0][0])
dp[1][1].add(-diff[0][0])

for i in range(1, h+1):
    for j in range(1, w+1):
        for x in dp[i-1][j]:
            dp[i][j].add(x+diff[i-1][j-1])
            dp[i][j].add(x-diff[i-1][j-1])
        for x in dp[i][j-1]:
            dp[i][j].add(x+diff[i-1][j-1])
            dp[i][j].add(x-diff[i-1][j-1])

print(min([abs(x) for x in dp[h][w]]))


### FIXED CODE ###

tdlist = lambda i, j, value=0: [[value] * j for _ in range(i)]

h, w = map(int, input().split())
D = 160*80
D2 = D*2+1

diff = [list(map(int, input().split())) for _ in range(h)]
for i in range(h):
    for j, b in enumerate(list(map(int, input().split()))):
        diff[i][j] = abs(diff[i][j] - b)

dp = tdlist(h, w)
dp[0][0] |= 1 << D+diff[0][0]
dp[0][0] |= 1 << D-diff[0][0]

for i in range(h):
    for j in range(w):
        if j:
            dp[i][j] |= dp[i][j-1] << diff[i][j]
            dp[i][j] |= dp[i][j-1] >> diff[i][j]
        if i:
            dp[i][j] |= dp[i-1][j] << diff[i][j]
            dp[i][j] |= dp[i-1][j] >> diff[i][j]

ans = float("inf")
for i in range(D2):
    if dp[h-1][w-1] >> i & 1:
        ans = min(ans, abs(i-D))
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
l = list(map(int, input().split()))
dp = [0]+[float('inf')]*(N-1)
for i in range(N):
    for k in range(1, K+1):
        if i < N-k:
            dp[i+k] = min(dp[i+k], dp[i]+abs(l[i+k]-l[i]))
print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
l = list(map(int, input().split()))
dp = [0]+[float('inf')]*(N-1)
for i in range(N):
    for k in range(1, K+1):
        if i < N-k:
            dp[i+k] = min(dp[i+k], dp[i]+abs(l[i+k]-l[i]))
print(dp[-1])
### BUGGY CODE ###

def resolve():
        n, k = map(int, input().split())
        a = list(map(int, input().split()))
        bn1 = [0] * n
        bn2 = [0] * n
        s = 0
        t = 0
        chec=0
        for _ in range(k):
            for i in range(n):
                b1 = max(i - a[i], 0)
                b2 = min(i + a[i], n - 1)
                bn1[b1] += 1
                bn2[b2] += 1
            for i in range(n):
                s += bn1[i]
                a[i] = s
            s = 0
            for i in range(1, n):
                t += bn2[i - 1]
                a[i] -= t
                if a[i]==n:
                    chec+=1

            if chec==n:
                break
            chec=0
            t = 0
            bn1 = [0] * n
            bn2 = [0] * n
        c = [str(x) for x in a]
        L = " ".join(c)
        print(L)
resolve()

### FIXED CODE ###

def resolve():
        n, k = map(int, input().split())
        a = list(map(int, input().split()))
        bn1 = [0] * n
        s = 0
        t = 0
        chec = 0
        for _ in range(k):
            for i in range(n):
                b1 = max(i - a[i], 0)
                b2 = min(i + a[i], n - 1)
                bn1[b1] += 1
                if b2<n-1:
                    bn1[b2+1] -= 1
            for i in range(n):
                s += bn1[i]
                a[i] = s
                if s==n:
                    chec+=1
            s = 0
            if chec == n:
                break
            chec = 0
            bn1 = [0] * n
        c = [str(x) for x in a]
        L = " ".join(c)
        print(L)
resolve()
### BUGGY CODE ###

import numpy as np
from collections import deque
n,m,k=map(int,input().split())
A=[0]+list(map(int, input().split()))
B=[0]+list(map(int, input().split()))
ans=0
a=np.cumsum(np.array(A)).tolist()
b=np.cumsum(np.array(B)).tolist()
for i in range(n+1):
    if k>=a[i]:
        j=m
        while b[j]>k-a[i]:
            j-=1
        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()))
ans=0
a, b=[0], [0]
for i in range(n):
    a.append(a[i]+A[i])
for i in range(m):
    b.append(b[i]+B[i])
j=m
for i in range(n+1):
    if k<a[i]:
        break
    while b[j]>k-a[i]:
        j-=1
    ans=max(ans,i+j)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(6009)
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for j in range(m+1)] for i in range(n+1)]
def lcs(i,j):
	if dp[i][j]!=0:
		return dp[i][j]
	if i*j==0:
		return 0
	if s[i-1]==t[j-1]:
		r=lcs(i-1,j-1)+1
	else:
		r=max(lcs(i,j-1),lcs(i-1,j))
	dp[i][j]=r
	return r
		
		

lcs(n,m)

i=n
j=m
st=""
while dp[i][j]:
	while dp[i-1][j]==dp[i][j]:
		i-=1
	while dp[i][j-1]==dp[i][j]:
		j=j-1
	j-=1
	st+=s[i-1]
	i-=1
print(st[::-1])
	

### FIXED CODE ###

s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1,n+1):
	for j in range(1,m+1):
		if s[i-1]==t[j-1]:
			dp[i][j]=dp[i-1][j-1]+1
		else:
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])
i=n
j=m
st=""
while dp[i][j]:
	while dp[i-1][j]==dp[i][j]:
		i-=1
	while dp[i][j-1]==dp[i][j]:
		j=j-1
	j-=1
	st+=s[i-1]
	i-=1
print(st[::-1])
### BUGGY CODE ###

N,K = map(int,input().split())
P = [int(t) - 1 for t in input().split()]
C = list(map(int,input().split()))

ans = -1e18
for si in range(N):
    x = si
    s = []
    tot = 0
    while True:
        x = P[x]
        s.append(C[x])
        tot += C[x]
        if x == si:
            break
    l = len(s)
    t = 0
    for i in range(l):
        t += s[i]
        if i+1 > K:
            break
        now = t
        if tot > 0:
            e = (K-(i+1))//l
            now += tot*e
        if ans < now:
            ans = now
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
P = [int(t) - 1 for t in input().split()]
C = list(map(int,input().split()))

ans = -1e18
for si in range(N):
    x = si
    s = []
    tot = 0
    while True:
        x = P[x]
        s.append(C[x])
        tot += C[x]
        if x == si:
            break
    l = len(s)
    t = 0
    for i in range(l):
        t += s[i]
        if i+1 > K:
            break
        now = t
        if tot > 0:
            e = (K-(i+1))//l
            now += tot*e
        if ans < now:
            ans = now
print(ans)
### BUGGY CODE ###

n = int(input())
s=input()

s1=""

for i in s:
    if i=="R":s1+="1"
    elif i=="G":s1+="2"
    elif i=="B":s1+="4"


l1=int(s1,16)
l2=int(s1,16)

ans=0

l2*=16

for i in range(2,n):
    l2*=16
    l3=int(s1,16)
    for j in range(1,i):
        l3*=16
        if j==i-j:
            continue
        tasi=l1+l2+l3
        ans+=hex(tasi).count("7")

print(ans)

### FIXED CODE ###

n = int(input())
s=input()

ans=s.count("R")*s.count("G")*s.count("B")

for start in range(n):
    for kousa in range(n):
        if start+2*kousa>n-1:
            break
        if s[start]!=s[start+kousa] and s[start+kousa]!=s[start+2*kousa] and s[start+2*kousa]!=s[start]:
            ans-=1

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

import numpy as np
N = input()
S = input()
sli = [c for c in S]

nR = sli.count('R')
nG = sli.count('G')
nB = sli.count('B')

dx = 1
ng = 0
for i, c in enumerate(sli):
    rl = []
    dx = 1

    a = int(len(sli) / 2)
    rl = [(i, i+dx, i+dx*2)
          for dx in range(len(sli)) if dx * 2 + i < len(sli)]

    for ind in rl:
        if len(set([sli[ind[0]], sli[ind[1]], sli[ind[2]]])) == 3:
            ng += 1


n = nR * nG * nB - ng
print(str(n))


### FIXED CODE ###

#!/usr/bin/env python3

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

ans = S.count('R') * S.count('G') * S.count('B')

for i in range(len(S)):
    for d in range(len(S)):
        j = i + d
        k = j + d
        if k >= N:
            break

        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ans -= 1

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

import numpy as np
N, M, Q = map(int, input().split())
X = np.zeros((N, N), dtype=int)
ends = np.zeros((M, 2), dtype=int)
queries = np.zeros((Q, 2), dtype=int)
for i in range(M):
    ends[i] = [int(item) for item in input().split()]
for i in range(Q):
    queries[i] = [int(item) for item in input().split()]
np.add.at(X, [ends[:,0] - 1, ends[:, 1] - 1], 1)
for items in queries:
    print(np.sum(X[items[0] - 1:items[1], items[0] - 1:items[1]]))


### FIXED CODE ###

import numpy as np
N, M, Q = map(int, input().split())
X = np.zeros((N, N), dtype=int)
ends = np.zeros((M, 2), dtype=int)
queries = np.zeros((Q, 2), dtype=int)
for i in range(M):
    ends[i] = [int(item) for item in input().split()]
for i in range(Q):
    queries[i] = [int(item) for item in input().split()]
np.add.at(X, [ends[:,0] - 1, ends[:, 1] - 1], 1)
B = np.cumsum(X[::-1,:], axis = 0)[::-1,:]
C = np.cumsum(B, axis = 1)
for item in queries:
    print(C[item[0] - 1, item[1] - 1])
### BUGGY CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

MOD = 10 ** 9 + 7
N, M = list(map(int, sys.stdin.readline().split()))
S = list(map(int, sys.stdin.readline().split()))
T = list(map(int, sys.stdin.readline().split()))
S = [-1] + S
T = [-1] + T

# dp[i][j]: S[i] と T[j] で終わる組み合わせの数
# S[i] != T[j] のとき 0
# S[i] == T[j] のとき、sum(dp[:i][:j])
dp = np.zeros((len(S), len(T)), dtype=int)
dp[0][0] = 1
# dp の二次元累積和
cumsum = np.ones(len(T), dtype=int)
for i in range(1, len(S)):
    for j in range(1, len(T)):
        if S[i] != T[j]:
            continue
        # dp[i][j] = dp[:i, :j].sum() % MOD
        dp[i][j] = cumsum[j - 1] % MOD
    cumsum += dp[i].cumsum()
    cumsum %= MOD
print(cumsum[-1])


### FIXED CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

MOD = 10 ** 9 + 7
N, M = list(map(int, sys.stdin.readline().split()))
S = list(map(int, sys.stdin.readline().split()))
T = list(map(int, sys.stdin.readline().split()))
S = np.array([-1] + S)
T = np.array([-1] + T)

# # dp[i][j]: S[i] と T[j] で終わる組み合わせの数
# # S[i] != T[j] のとき 0
# # S[i] == T[j] のとき、sum(dp[:i][:j])
# dp = np.zeros((len(S), len(T)), dtype=int)
# dp[0][0] = 1
# # dp の二次元累積和
# cumsum = np.ones(len(T), dtype=int)
# for i in range(1, len(S)):
#     for j in range(1, len(T)):
#         if S[i] != T[j]:
#             continue
#         # dp[i][j] = dp[:i, :j].sum() % MOD
#         dp[i][j] = cumsum[j - 1] % MOD
#     cumsum += dp[i].cumsum()
#     cumsum %= MOD
# print(cumsum[-1])


cumsum = np.ones(len(T), dtype=int)
for i in range(1, len(S)):
    cumsum[1:] += ((T == S[i])[1:] * cumsum[:-1] % MOD).cumsum()
    cumsum %= MOD
print(cumsum[-1])
### BUGGY CODE ###

n = int(input())
s = list(map(int, input().split()))
mod = 10**9 + 7
m = len(bin(max(s))) - 2
p = [0] * m
q = [0] * m

for i in s:
    for j in range(m):
        if (i >> j) & 1 == 1:
            p[j] += 1
        else:
            q[j] += 1

res = 0
r = 1
for k in range(m):
    res += p[k] * q[k] % mod * r
    res %= mod
    r = r * 2 % mod
print(res)


### FIXED CODE ###

n = int(input())
s = list(map(int, input().split()))
mod = 10**9 + 7
m = len(bin(max(s))) - 2
p = [0] * m
q = [0] * m

for i in s:
    for j in range(m):
        if (i >> j) & 1 == 1:
            p[j] += 1
        else:
            q[j] += 1

res = 0
r = 1
for k in range(m):
    res += p[k] * q[k] % mod * r
    res %= mod
    r = r * 2 % mod
print(res)
### BUGGY CODE ###

import math

def prime_numbers(numbers):
    return list(map(is_prime, numbers)).count(True)


def is_prime(n):
    if (n == 2):
        return True
    elif (n % 2 == 0):
        return False
    else:
        for i in range(3, int(n / 2), 2):
            if n % i == 0:
                return False

    return True

if __name__ == '__main__':
    n = int(input())
    numbers = []
    for i in range(0, n):
        numbers.append(int(input()))
    print(prime_numbers(numbers))



### FIXED CODE ###

import math

def prime_numbers(numbers):
    return list(map(is_prime, numbers)).count(True)


def is_prime(n):
    if (n == 2):
        return True
    elif (n % 2 == 0):
        return False
    else:
        i = 3
        while i <= math.sqrt(n):
            if n % i == 0:
                return False
            i += 2

    return True

if __name__ == '__main__':
    n = int(input())
    numbers = []
    for i in range(0, n):
        numbers.append(int(input()))
    print(prime_numbers(numbers))
### BUGGY CODE ###

n = int(input())
s = input()

rgb = [[], [], []]

for i, c in enumerate(s):
    if c == 'R':
        rgb[0].append(i)
    elif c == 'G':
        rgb[1].append(i)
    else:
        rgb[2].append(i)

comb = len(rgb[0]) * len(rgb[1]) * len(rgb[2])

summ = 0
for i in rgb[0]:
    for j in rgb[1]:
        ii = min(i, j)
        jj = max(i, j)
        d = jj - ii
        if ii - d >= 0 and ii - d in rgb[2]:
            summ += 1
        if jj + d < n and jj + d in rgb[2]:
            summ += 1
        if not d % 2 and ii + d // 2 in rgb[2]:
            summ += 1

print(comb - summ)

### FIXED CODE ###

n = int(input())
s = input()

rgb = [[], [], []]

for i, c in enumerate(s):
    rgb[(c > 'G') + (c > 'B')].append(i)

exclude = 0
for i in rgb[0]:
    for j in rgb[1]:
        ii = min(i, j)
        jj = max(i, j)
        d = jj - ii
        if ii - d >= 0 and ii - d in rgb[2]:
            exclude += 1
        if jj + d < n and jj + d in rgb[2]:
            exclude += 1
        if not d % 2 and ii + d // 2 in rgb[2]:
            exclude += 1

summ = len(rgb[0]) * len(rgb[1]) * len(rgb[2])
print(summ - exclude)
### BUGGY CODE ###

def main():
    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    a2 = [1] * (n-k+1)
    for i in range(n-k+1):
        for j in range(i,i+k):
            a2[i] *= a[j]
    #print(a2)
    for i in range(len(a2)-1):
        if a2[i] < a2[i+1]:
            print("Yes")
        else:
            print("No")

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(n-k):
        print("Yes" if a[i] < a[i+k] else "No")

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

import sys
from heapq import *

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

	N, K = list(map(int,input().split()))
	A = list(map(int,input().split()))
	F = list(map(int,input().split()))

	A.sort()
	F.sort(reverse=True)

	cost = []
	for ai, fi in zip(A,F):
		heappush(cost,(ai*fi*-1,ai,fi))

	while K>0:
		cmax, ai, fi = heappop(cost)
		if cmax==0: break
		csec = min(cost[0][0],cost[1][0])
		count = (csec-cmax)//ai + 1
		if count>K: count = K
		# print(count)
		aj = ai-count
		fj = fi
		cj = aj*fj*-1
		heappush(cost,(cj,aj,fj))
		K -= count

	ans = cost[0][0]*-1
	print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import math

input = sys.stdin.readline

N, K = list(map(int,input().split()))
A = list(map(int,input().split()))
F = list(map(int,input().split()))

A.sort()
F.sort(reverse=True)

cost = []
for ai, fi in zip(A,F):
	cost.append([ai*fi,fi])
cost.sort(reverse=True)

thmin = -1
thmax = cost[0][0]+1

while thmax-thmin!=1:
	# print(thmin,thmax)
	th = (thmin+thmax)//2
	ktmp = 0
	ind = 0
	judge = True
	while True:
		ci, fi = cost[ind]
		if ci<=th: break
		ktmp += math.ceil((ci-th)/fi)
		if ktmp>K:
			judge = False
			break
		ind += 1
		if ind==N: break
	if judge:
		thmax = th
	else:
		thmin = th

print(thmax)
### BUGGY CODE ###

k = int(input())

num = 1 
n = 7
 
while True:
  if (n%k == 0):
    print(num)
    break
  else:
    n = n*10 + 7
    num += 1

### FIXED CODE ###

def main():
    k = int(input())

    num = 1 
    n = 7
    
    if (k%2 == 0):
        print(-1)
        return
    

    for i in range(1000000):
        if (n%k == 0):
            print(num)
            return
        else:
            n = (n*10 + 7)%k
            num += 1

    print(-1)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import math
import sys
sys.setrecursionlimit(10000000)

N = int(input())
POW6 = [6**i for i in range(6, 0, -1)]
POW9 = [9**i for i in range(5, 0, -1)]

def rec(N, num, A):
    if N <= 5:
        num += N
        A.append(num)
        return A
    if N <= 8:
        num += N - 5
        A.append(num)
        return A
    for p6 in POW6:
        if p6 <= N:
            rec(N - p6, num+1, A)
    for p9 in POW9:
        if p9 <= N:
            rec(N - p9, num+1, A)
    return A

A = rec(N, 0, [])
print(min(A))

### FIXED CODE ###

import math
N = int(input())
def greed(N, a):
    if a == 6:
        L = [6**i for i in range(7, -1, -1)]
    else:
        L = [9**i for i in range(6, -1, -1)]
    num = 0
    while True:
        if N == 0:
            return num
        for l in L:
            if l <= N:
                N -= l
                break
        num += 1
A = []
for n in range(N+1):
    A.append(greed(n, 6) + greed(N-n, 9))
print(min(A))
### BUGGY CODE ###

A,B,C,D = map(int,input().split())
count = 0
for i in range(A,B+1):
  if i%C != 0 and i%D != 0:
    count = count+1
print(count)

### FIXED CODE ###

import math
A,B,C,D = map(int,input().split())
count1 = 0
count2 = 0
ans1 = B-B//C-B//D+B//((C*D)//math.gcd(C,D))
A = A-1
ans2 = A-A//C-A//D+A//((C*D)//math.gcd(C,D))
print(ans1-ans2)
### BUGGY CODE ###

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

output=""

for i in range(n):
    output+=str(1+a_lis.index(i+1))+" "

print(output)


### FIXED CODE ###

n=int(input())
a_lis=list(map(int,input().split()))
lis = sorted(range(n), key=lambda k: a_lis[k])
for i in range(n):
    lis[i]=str(lis[i]+1)
print(' '.join(lis))
### BUGGY CODE ###

n = int(input())
s = input()
dp = [[0]*(n+1) for i in range(n+1)]
for i in reversed(range(n)):
    for j in reversed(range(0, i, 1)):
        if s[i] == s[j]:
            dp[j][i] = dp[j+1][i+1] + 1
ans = 0
for i in reversed(range(n)):
    for j in reversed(range(0, i, 1)):
        ans = max(min(dp[j][i], i-j), ans)
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
dp = [[0]*(n+1) for i in range(n+1)]
for i in reversed(range(n)):
    for j in reversed(range(0, i, 1)):
        if s[i] == s[j]:
            dp[j][i] = dp[j+1][i+1] + 1
ans = 0
for i in reversed(range(n)):
    for j in reversed(range(0, i, 1)):
        ans = max(min(dp[j][i], i-j), ans)
print(ans)
### BUGGY CODE ###

h, w, a, b = map(int, input().split(' '))
MOD = 10**9 + 7
MAX = 3*10**5


def modpow(a, b):
    res = 1
    while b:
        if (b & 1):
            res = (res * a) % MOD
        a = (a * a) % MOD
        b >>= 1
    return res


def nCr(n, r):
    if r == 0 or n == r:
        return 1
    return (((f[n] * ivf[n-r]) % MOD) * ivf[r]) % MOD


f = [1] * MAX
ivf = [0] * MAX
for i in range(1, MAX):
    f[i] = (f[i-1] * i) % MOD
    ivf[i] = modpow(f[i], MOD-2)
r = 0
for i in range(b, w):
    y1 = h - a - 1
    x1 = i
    y2 = a - 1
    x2 = w - i - 1
    p = (nCr(x1 + y1, x1) * nCr(x2 + y2, x2)) % MOD
    r = (r + p) % MOD
print(int(r))


### FIXED CODE ###

from array import *
import time
h, w, a, b = map(int, input().split(' '))
MOD = 10**9 + 7
MAX = max(h+w-a-1, a+w)


def modpow(a, b):
    res = 1
    while b:
        if (b & 1):
            res = (res * a) % MOD
        a = (a * a) % MOD
        b >>= 1
    return res


def nCr(n, r):
    if r == 0 or n == r:
        return 1
    return (((f[n] * ivf[n-r]) % MOD) * ivf[r]) % MOD


f = [1] * MAX
f = array('q', f)
ivf = [0] * MAX
ivf = array('q', ivf)
for i in range(1, MAX):
    f[i] = (f[i-1] * i) % MOD
    ivf[i] = modpow(f[i], MOD-2)
r = 0
for i in range(b, w):
    y1 = h - a - 1
    x1 = i
    y2 = a - 1
    x2 = w - i - 1
    p = (nCr(x1 + y1, x1) * nCr(x2 + y2, x2)) % MOD
    r = (r + p) % MOD
print(int(r))