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

import sys
imput=sys.stdin.readline
h,w=map(int,input().split())
w+=2
h+=2
grid='#'*w
for _ in range(h-2):
    grid+='#'+input()+'#'
grid+='#'*w
move=[1,-1,w,-w]
score_a=[0]*(h*w)
score_b=[0]*(h*w)
score_c=[0]*(h*w)
score_d=[0]*(h*w)

for i in range(h*w):
    if grid[i]=='#':
        score_a[i]=0
        score_b[i]=0
    else:
        if i-1>=0 and i-1<=h*w-1:
            score_a[i]+=score_a[i-1]+1
        if i-w>=0 and i-w<=h*w-1:
            score_b[i]+=score_b[i-w]+1
    if grid[h*w-1-i]=='#':
        score_c[h*w-1-i]=0
        score_d[h*w-1-i]=0
    else:
        if h*w-1-i+1<=h*w-1 and h*w-1-i+1>=0:
            score_c[h*w-1-i]+=score_c[h*w-1-i+1]+1
        if h*w-1-i+w<=h*w-1 and h*w-1-i+w>=0:
            score_d[h*w-1-i]+=score_d[h*w-1-i+w]+1
ans=0
for i in range(h*w):
    ans=max(ans, score_a[i]+score_b[i]+score_c[i]+score_d[i]-3)
print(ans)

### FIXED CODE ###

h, w = map(int, input().rsplit())
S = [list(input().rstrip()) for _ in range(h)]
U = [[0] * w for _ in range(h)]
D = [[0] * w for _ in range(h)]
L = [[0] * w for _ in range(h)]
R = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if j == 0:
            if S[i][j] == ".":
                L[i][j] = 1
            continue
        if S[i][j] == "#":
            continue
        else:
            L[i][j] += 1 + L[i][j - 1]
for i in range(h):
    for j in range(w):
        if i == 0:
            if S[i][j] == ".":
                U[i][j] = 1
            continue
        if S[i][j] == "#":
            continue
        else:
            U[i][j] += 1 + U[i - 1][j]
for i in range(h - 1, -1, -1):
    for j in range(w - 1, -1, -1):
        if j == w - 1:
            if S[i][j] == ".":
                R[i][j] = 1
            continue
        if S[i][j] == "#":
            continue
        else:
            R[i][j] += 1 + R[i][j + 1]
for i in range(h - 1, -1, -1):
    for j in range(w - 1, -1, -1):
        if i == h - 1:
            if S[i][j] == ".":
                D[i][j] = 1
            continue
        if S[i][j] == "#":
            continue
        else:
            D[i][j] += 1 + D[i + 1][j]
ans = 0
for i in range(h):
    for j in range(w):
        temp = D[i][j] + U[i][j] + L[i][j] + R[i][j] - 3
        ans = max(temp, ans)
print(ans)
### BUGGY CODE ###

n = int(input())
A = sorted(map(int, input().split()))

B = [1] * n
for i in range(n):
    if B[i] == 0:
        continue
    a = A[i]
    for j in range(i + 1, n):
        if A[j] % a == 0:
            B[j] = 0

for i in range(n - 1):
    if B[i] == 1:
        if A[i] == A[i + 1]:
            B[i] = 0

print(sum(B))


### FIXED CODE ###

from collections import Counter


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

ok = [False] * (10**6 + 1)
for a in A:
    ok[a] = True

for i in range(10**6 + 1):
    if ok[i]:
        j = 2
        while i * j <= 10**6:
            ok[i * j] = False
            j += 1

for a, cnt in Counter(A).items():
    if cnt >= 2:
        ok[a] = False

print(sum(ok))
### BUGGY CODE ###

import math

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

balls = [0]*n
for a in A:
    balls[a-1] += 1

tei = math.factorial(2)
ball_permu = [0]*n
ball_permu_target = [0]*n
for i in range(n):
    if balls[i] < 2:
        ball_permu[i] = 0
    else:
        ball_permu[i] = math.factorial(
            balls[i])//(math.factorial(balls[i]-2)*tei)

    ball = balls[i]-1
    if ball < 2:
        ball_permu_target[i] = 0
    else:
        ball_permu_target[i] = math.factorial(
            ball)//(math.factorial(ball-2)*tei)

ball_sum = sum(ball_permu)
# print(balls)
# print(ball_permu)
# print(ball_permu_target)
for a in A:
    ans = ball_sum-ball_permu[a-1]+ball_permu_target[a-1]
    print(ans)


### FIXED CODE ###

from collections import Counter

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

C = Counter(A)
a_sum = 0
for i in C.values():
    a_sum += i*(i-1)//2

for a in A:
    k = C[a]
    print(a_sum-(k*(k-1)//2)+((k-1)*(k-2)//2))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [W for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = set([(Dh, Dw)])
    while True:
        nq = set()
        while q:
            q_ = set()
            for h, w in q:
                # print('({}, {}) = {}'.format(h, w, ans))
                if h == Ch and w == Cw:
                    print(ans)
                    return True
                M[h][w] = '#'
                nq.add((h, w))
                for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    if 0 <= h+dh < H and 0 <= w+dw < W:
                        if M[h+dh][w+dw] == '.':
                            q_.add((h+dh, w+dw))
                            M[h+dh][w+dw] = '#'
            q = q_

        if nq:
            for h, w in nq:
                for dh in range(-2, 3):
                    for dw in range(-2, 3):
                        if 0 <= h+dh < H and 0 <= w+dw < W:
                            if M[h+dh][w+dw] == '.':
                                q.add((h+dh, w+dw))
        # for h in range(H):
        #     print(M[h])
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [W for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = set([(Dh, Dw)])
    while True:
        nq = set()
        while q:
            q_ = set()
            for h, w in q:
                # print('({}, {}) = {}'.format(h, w, ans))
                if h == Ch and w == Cw:
                    print(ans)
                    return True
                M[h][w] = '#'
                nq.add((h, w))
                for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    if 0 <= h+dh < H and 0 <= w+dw < W:
                        if M[h+dh][w+dw] == '.':
                            q_.add((h+dh, w+dw))
                            M[h+dh][w+dw] = '#'
            q = q_

        if nq:
            for h, w in nq:
                for dh in range(-2, 3):
                    for dw in range(-2, 3):
                        if 0 <= h+dh < H and 0 <= w+dw < W:
                            if M[h+dh][w+dw] == '.':
                                q.add((h+dh, w+dw))
        # for h in range(H):
        #     print(M[h])
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

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

import sys

# A - Two Abbreviations
def get_lcm(a, b):
	import math
	return (a * b) // math.gcd(a, b)


def is_match(X, L):
  global M
  global T

  i = 0
  m = L//M * i

  while m + 1 < L:
    if m+1 in X.keys():
      if X[m+1] != T[i]:
        return False

    i += 1
    m = L//M * i

  return True


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

if S[0] != T[0]:
  print(-1)
else:
  lcm = get_lcm(N, M)

  for i in range(1, 100):
    L = lcm * i
    X = dict()

    j = 0
    n = L//N * j

    while n + 1 < L:
      X[n+1] = S[j]

      j += 1
      n = L//N * j

    if is_match(X, L):
      print(L)
      exit()

  print(-1)

### FIXED CODE ###

import sys

# A - Two Abbreviations
def get_lcm(a, b):
	import math
	return (a * b) // math.gcd(a, b)


def is_match(X, L):
  global M
  global T

  i = 0
  m = L//M * i

  while m + 1 < L:
    if m+1 in X.keys():
      if X[m+1] != T[i]:
        return False

    i += 1
    m = L//M * i

  return True


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

if S[0] != T[0]:
  print(-1)
else:
  lcm = get_lcm(N, M)

  for i in range(1, 100):
    L = lcm * i
    X = dict()

    j = 0
    n = L//N * j

    while n + 1 < L:
      X[n+1] = S[j]

      j += 1
      n = L//N * j

    if is_match(X, L):
      print(L)
      exit()

  print(-1)
### BUGGY CODE ###

N, M = (map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

C = 1
A.sort(reverse=True)
B.sort(reverse=True)

aloop = 0
bloop = 0

if len(set(A)) != len(A) or len(set(B)) != len(B):
    C = 0

else:
    for k in range(N * M, 0, -1):
        if aloop < N and bloop < M and k == A[aloop] and k == B[bloop]:
            aloop += 1
            bloop += 1
        elif aloop < N and k == A[aloop]:
            C *= bloop
            aloop += 1
        elif bloop < M and k == B[bloop]:
            C *= aloop
            bloop += 1
        else:
            C *= (aloop*bloop-(N*M-k))

print(C % (10**9+7))

### FIXED CODE ###

N, M = (map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

C = 1
A.sort(reverse=True)
B.sort(reverse=True)

aloop = 0
bloop = 0

if len(set(A)) != len(A) or len(set(B)) != len(B):
    C = 0

else:
    for k in range(N * M, 0, -1):
        if aloop < N and bloop < M and k == A[aloop] and k == B[bloop]:
            aloop += 1
            bloop += 1
        elif aloop < N and k == A[aloop]:
            C *= bloop
            aloop += 1
        elif bloop < M and k == B[bloop]:
            C *= aloop
            bloop += 1
        else:
            C *= (aloop * bloop - (N * M - k))

        C = C % (10**9+7)
print(C)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
import numpy as np
count=0
for i in range (N):
    count_A=np.sum(np.array(A)<B[i])
    count_B=np.sum(np.array(C)>B[i])
    count+=count_A*count_B
print(count)

### FIXED CODE ###

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()

count=0
for i in range (N):
    count_A=bisect.bisect_left(A,B[i])
    count_B=len(C)-bisect.bisect_right(C,B[i])
    count+=count_A*count_B
print(count)
### BUGGY CODE ###

import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
N = int(input())
#n, m, k = map(int, sys.stdin.readline().split())
#s = input()
#a = list(map(int, sys.stdin.readline().split()))

def make_divisors(n):
    cnt = 0
    #lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            #lower_divisors.append(i)
            if i != n // i:
                cnt += 1
                #upper_divisors.append(n//i)
        i += 1
    return cnt       

l = [0]
for i in range(1, N+1):
    l.append(make_divisors(i))



ans = 0
for i in range(1, N+1):
    ans += i * l[i]

print(ans)

    













### FIXED CODE ###

import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
n = int(input())
#n, m, k = map(int, sys.stdin.readline().split())
#s = input()
#A = list(map(int, sys.stdin.readline().split()))

ans = 0
for i in range(1, n+1):
    x = n // i
    y = i * (x * (x + 1)) // 2
    ans += y

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


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

count = 0
for i in range(K+1) :
    for j in range(K+1) :
        for k in range(K+1) :
            if S == i + j + k :
                count += 1
print(count)


### FIXED CODE ###


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

count = 0
for i in range(K+1) :
    for j in range(K+1) :
        if S < i + j :
            break
        if S - i - j <= K :
            count += 1

print(count)
### BUGGY CODE ###

cnt = 0
N = int(input())
A = list(map(int, input().split()))
minus_list = [j - A[j] for j in range(N)]
for i in range(N):
    add = A[i] + i
    cnt += minus_list.count(add)
print(cnt)

### FIXED CODE ###

from collections import Counter
cnt = 0
N = int(input())
A = list(map(int, input().split()))
minus_list = [j - A[j] for j in range(N)]
counter = Counter(minus_list)
for i in range(N):
    add = A[i] + i
    cnt += counter[add]
print(cnt)
### BUGGY CODE ###

from collections import deque
n = int(input())
A = deque([int(input()) for _ in range(n)])
ans = []

for _ in range(n):
    tmp = A.popleft()
    print(max(A))
    A.append(tmp)


### FIXED CODE ###

from collections import deque
n = int(input())
A = [int(input()) for _ in range(n)]
# ans = []
#
# for _ in range(n):
#     tmp = A.popleft()
#     print(max(A))
#     A.append(tmp)

# 時間がかかるのはソートだけ。
sorted_A = sorted(A, reverse=True)
max_val = sorted_A[0]
second_val = sorted_A[1]

for i in range(n):
    # 索引は速いらしい
    if A[i] != max_val:
        print(max_val)
    else:
        print(second_val)
### BUGGY CODE ###

import itertools as it
D, G = map(int, input().split())
P, C = [], []
for _ in range(D):
    p, c = map(int, input().split())
    P.append(p)
    C.append(c)
A = list(it.permutations([i for i in range(D)]))
ans = 10**9
for a in A:
    S, i, sub_ans = 0, 0, 0
    while 1:
        if S + (a[i] + 1) * 100 * P[a[i]] < G:
            S += (a[i] + 1) * 100 * P[a[i]]
            sub_ans += P[a[i]]
            S += C[a[i]]
        else:
            j = 0
            while S < G and j < P[a[i]]:
                S += (a[i] + 1) * 100
                sub_ans += 1
            if j == P[a[i]]:
                S += C[a[i]]
        if S >= G:
            if sub_ans < ans:
                ans = sub_ans
            break
        i += 1
print(ans)


### FIXED CODE ###

import itertools as it
D, G = map(int, input().split())
P, C = [], []
for _ in range(D):
    p, c = map(int, input().split())
    P.append(p)
    C.append(c)
A = it.permutations([i for i in range(D)])
ans = 10**9
for a in A:
    S, i, sub_ans = 0, 0, 0
    while 1:
        if S + (a[i] + 1) * 100 * P[a[i]] < G:
            S += (a[i] + 1) * 100 * P[a[i]]
            sub_ans += P[a[i]]
        else:
            x = (G - S) // ((a[i] + 1) * 100)
            if S + (a[i] + 1) * 100 * x < G:
                x += 1
            sub_ans += x
            S += (a[i] + 1) * 100 * x
        S += C[a[i]]
        if S >= G:
            if sub_ans < ans:
                ans = sub_ans
            break
        i += 1
print(ans)
### BUGGY CODE ###

s = input() + "T"
x, y = map(int, input().split())
X = [[], [0]]
d = 0
t = 0
for i in range(len(s)):
    if s[i] == "F":
        t += 1
    else:
        X[d].append(t)
        d = 1-d
        t = 0
def calc(l):
    if len(l) == 0: return [0] 
    post = [l[0]]
    for i in range(1, len(l)):
        if l[i]:
            pre = post
            post = []
            for j in pre:
                if j+l[i] not in post: post.append(j+l[i])
                if j-l[i] not in post: post.append(j-l[i])
            # print(pre, post)
    return post

if x in calc(X[0]) and y in calc(X[1]):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

s = input() + "T"
x, y = map(int, input().split())
X = [[], [0]]
d = 0
t = 0
for i in range(len(s)):
    if s[i] == "F":
        t += 1
    else:
        X[d].append(t)
        d = 1-d
        t = 0
def calc(l):
    if len(l) == 0: return [0] 
    post = [l[0]]
    for i in range(1, len(l)):
        if l[i]:
            pre = sorted(post)
            post = []
            for j in range(len(pre)):
                if j==0 or pre[j] != pre[j-1]:
                    post.append(pre[j]+l[i])
                    post.append(pre[j]-l[i])
            # print(pre, post)
    return post

if x in calc(X[0]) and y in calc(X[1]):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

def primes(n):
    '''
    素数テーブルの作成
    '''
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    ret = []
    for i, p in enumerate(is_prime):
        if p:
            ret.append(i)
    return ret, is_prime
prime_list, is_prime = primes(55555 * 100)
prime_list.reverse()

from itertools import combinations

N = int(input())
A = []
for i in range(5):
    A.append(prime_list.pop())

while len(A) < N:
    n = prime_list.pop()
    if not any([is_prime[sum(comb)+n] for comb in combinations(A, 4)]):
        A.append(n)

print(*A, sep=" ")



### FIXED CODE ###

N = int(input())

def get_primes(n):
    '''
    素数テーブルの作成
    '''
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i, b in enumerate(is_prime):
        if b:
            yield i

primes_and_mod1 = []
for i in get_primes(55999):
    if i % 5 == 1:
        primes_and_mod1.append(i)

print(*primes_and_mod1[:N], sep=" ")
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
    a.sort()
    a[n-1]=a[n-1]//2
ans=0
for i in range(n):
    ans+=a[i]
print(ans)


### FIXED CODE ###

import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
lis=[]
for i in range(n):
    heapq.heappush(lis,-a[i])
for i in range(m):
    b=(heapq.heappop(lis)*(-1)//2)*(-1)
    heapq.heappush(lis,b)
    #print(lis)
ans=0
#print(lis)
for i in range(n):
    ans+=lis[i]
print(-ans)
### BUGGY CODE ###

from fractions import gcd


N = int(input())
A = list(map(int, input().split()))
lcm = lambda x, y: x*y//gcd(x, y)
l = 1
for a in A:
    l = lcm(l, a)
ans = 0
MOD = 10**9+7
for a in A:
    ans = (ans + l // a) % MOD 
print(ans)


### FIXED CODE ###

from fractions import gcd


N = int(input())
A = list(map(int, input().split()))
lcm = lambda x, y: x*y//gcd(x, y)
l = 1
for a in A:
    l = lcm(l, a)
ans = 0
MOD = 10**9+7
for a in A:
    ans += l // a
print(ans % MOD)
### BUGGY CODE ###

def count_changes(s, k, prev=None):
    count = 0
    for _ in range(k):
        for cur in s:
            if cur == prev:
                count += 1
                prev = None
            else:
                prev = cur
    return count, prev


if __name__ == '__main__':
    s = input()
    k = int(input())
    print(count_changes(s, k)[0])


### FIXED CODE ###

def count_changes(s, k, prev=None):
    count = 0
    for _ in range(k):
        for cur in s:
            if cur == prev:
                count += 1
                prev = None
            else:
                prev = cur
    return count, prev


if __name__ == '__main__':
    s = input()
    k = int(input())
    if len(set(s)) == 1:
      print((len(s) * k) // 2)
      exit()
    if k <= 10 ** 8:
        print(count_changes(s, k)[0])
    else:
        base_count, prev = count_changes(s, 3)
        d, rest = divmod(k, 3)
        res = base_count * d
        if rest:
            res += count_changes(s, rest, prev)[0]
        elif s[0] == prev:
            res += (d - 1)
        print(res)
### BUGGY CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    return res

inf = 2 * 10**9
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = accumulate(C1, C2);  z1.reverse()
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        z1 = accumulate(C1, C2[j:]);  z1.reverse();  Z1.append(z1)
        z2 = accumulate(C1[j:], C2);  z2.reverse();  Z2.append(z2)
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + (Z1[j-k][k] if j>=k else Z2[k-j][j])
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)


### FIXED CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    n = min(len(S1), len(S2))
    res = [0] * (n+1)
    c = 0
    for i in range(n):
        if S1[i] == S2[i]:
            c += 1
        res[n-i-1] = c
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)
### BUGGY CODE ###

import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)

for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
mxd = 0
res = [set() for _ in range(N + 1)]
Q = int(input())
qd = [0] * Q
qc = [0] * Q
for i in range(Q):
  v, d, c = map(int, input().split())
  qd[i] = d
  qc[i] = c
  res[v].add(i)
  mxd = max(mxd, d)
#print(qc)

def clean():
  global res
  for i in range(1, N + 1):
    a = sorted(res[i], reverse = True)
    d = -1
    for j in range(len(a)):
      x = a[j]
      if qd[x] <= d: res[i].discard(x)
      d = max(d, qd[x])
clean()
for t in range(mxd):
  tres = [set() | s for s in res]
  for x in range(1, N + 1):
    for y in e[x]:
      for z in res[x]:
        if qd[z] > t: tres[y].add(z)
  res = tres
  clean()
#print(res)

for r in res[1: ]:
  if len(r): print(qc[max(r)])
  else: print(0)

### FIXED CODE ###

import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)

for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
mxd = 0
res = [[-1] * 11 for _ in range(N + 1)]
Q = int(input())
qd = [0] * Q
qc = [0] * Q
for i in range(Q):
  v, d, c = map(int, input().split())
  qd[i] = d
  qc[i] = c
  res[v][d] = i
  mxd = max(mxd, d)
#print(qc)

#print(mxd)
for t in range(mxd):
  tres = [x[: ] for x in res]
  for x in range(1, N + 1):
    for y in e[x]:
      for i in range(t + 1, 11):
        res[y][i] = max(res[y][i], tres[x][i])

#print(res)
for r in res[1: ]:
  x = -1
  for i in range(11):
    if r[i] != -1: x = max(x, r[i])
  if x == -1: print(0)
  else: print(qc[x])
### BUGGY CODE ###

from sys import stdin
input = stdin.buffer.readline
k = int(input())
t, c = 7, 1
while t % k:
    t = t * 10 + 7
    c += 1
print(c)


### FIXED CODE ###

from sys import stdin
input = stdin.buffer.readline
k = int(input())
t = 7
for i in range(1, k + 1):
    if not t % k:
        print(i)
        exit()
    t = (t * 10 + 7) % k
print(-1)