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

# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_D
sample_input = list(range(3))
sample_input[0] = '''5
5
1
4
3
2'''
sample_input[1] = '''3
3
2
1'''
sample_input[2] = '''1
1'''
give_sample_input = None
if give_sample_input is not None:
    sample_input_list = sample_input[give_sample_input].split('\n')
    def input():
        return sample_input_list.pop(0)
        
# main
def print_list(l):
    output = ''
    for elem in l:
        output += str(elem) + ' '
    output = output.rstrip()
    print(output)

def log_m_floor(n):
    m = 5
    pot = 1
    power = 0
    while (pot < n):
        pot *= 2
        power += 1
    return power

def insertion_sort(A, n, g):
    cnt = 0
    for i in range(g, n):
        v = A[i]
        j = i - g
        while (j >= 0 and A[j] > v):
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v
    return cnt

def shell_sort(A, n):
    cnt = 0
    m = log_m_floor(n)
    if m == 0:
        print(1)
        print(1)
        print(0)
        return
    print(m)
    G = [2**(m-i-1) for i in range(m)]
    print_list(G)
    for i in range(m):
        cnt += insertion_sort(A, n, G[i])
    print(cnt)
        
num_of_data = int(input())
data = []
for i in range(num_of_data):
    data.append(int(input()))
shell_sort(data, num_of_data)
for d in data:
    print(d)

### FIXED CODE ###

# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_D
sample_input = list(range(3))
sample_input[0] = '''5
5
1
4
3
2'''
sample_input[1] = '''3
3
2
1'''
sample_input[2] = '''5
5
1
4
3
2'''
give_sample_input = None
if give_sample_input is not None:
    sample_input_list = sample_input[give_sample_input].split('\n')
    def input():
        return sample_input_list.pop(0)
        
# main
def print_list(l):
    output = ''
    for elem in l:
        output += str(elem) + ' '
    output = output.rstrip()
    print(output)

def determine_G(n):
    G = []
    pot = 1
    while True:
        pot *= 2
        if pot-1 > n:
            break
        G.append(pot-1)
    G.reverse()
    return G

def log_m_floor(n):
    m = 2
    pot = 1
    power = 0
    while (pot < n):
        pot *= 2
        power += 1
    return power

def insertion_sort(A, n, g):
    cnt = 0
    for i in range(g, n):
        v = A[i]
        j = i - g
        while (j >= 0 and A[j] > v):
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v
    return cnt

def shell_sort(A, n):
    cnt = 0
    G = determine_G(n)
    m = len(G)
    if m == 0:
        print(1)
        print(1)
        print(0)
        return
    print(m)
    print_list(G)
    for i in range(m):
        cnt += insertion_sort(A, n, G[i])
    print(cnt)
        
num_of_data = int(input())
data = []
for i in range(num_of_data):
    data.append(int(input()))
shell_sort(data, num_of_data)
for d in data:
    print(d)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
total = 0
a.sort()
total = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if a[k] < a[i] + a[j]:
                total+=1
print(total)

### FIXED CODE ###

import bisect
inf = 10**15
mod = 10**9+7
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans=0
for i in range(n-2):
    a = l[i]
    for j in range(i+1, n-1):
        b = l[j]
        indc = bisect.bisect_left(l,a+b)
        ans+=(indc-j-1)
print(ans)
### BUGGY CODE ###

range = xrange
input = raw_input
MOD = 10**9+7
 
n = int(input())

dp = [0] * (1 << n)
for i in [i for i, x in enumerate(input().split()) if x == '1']:
    dp[1 << i] = 1

npow = 1 << n

A = [1<<j for j in range(n)]
masks = [[mask for mask in range(npow) if not mask & jpow] for jpow in A]

for i in range(n - 1):
    _dp = [0] * npow
    for j in [i for i, x in enumerate(input().split()) if x == '1']:
        jpow = 1 << j
        for mask in masks[j]:
            _dp[mask + jpow] += dp[mask]
    for mask in range(npow):
        _dp[mask] %= MOD
    dp = _dp
 
print(sum(dp) % MOD)

### FIXED CODE ###

range = xrange
input = raw_input
MOD = 10**9+7
 
n = int(input())

dp = [0] * (1 << n)
for i in [i for i, x in enumerate(input().split()) if x == '1']:
    dp[1 << i] = 1

npow = 1 << n

for i in range(n - 1):
    _dp = [0] * npow
    for j in [i for i, x in enumerate(input().split()) if x == '1']:
        jpow = 1 << j
        mask = 0
        while mask < npow:
            _dp[mask + jpow] += dp[mask]
            mask += 1 + ((mask+1) & jpow)
    for mask in range(npow):
        _dp[mask] %= MOD
    dp = _dp
 
print(sum(dp) % MOD)
### BUGGY CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

mod=10**9+7
N,P=map(int,input().split())
S=input()
dp=[[0 for i in range(P)] for n in range(N)]
#visited=set()
for n,s in enumerate(S):
    s=int(s)
    for i in range(P):
        A=(i*10+s)%P
        dp[n][A]+=dp[n-1][i]
    dp[n][s%P]+=1

print(sum([i[0] for i in dp]))


### FIXED CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

N,P=map(int,input().split())
S=input()

if P in [2,5]:
    count=0
    for i in range(N):
        if int(S[i])%P==0:
            count+=i+1
    print(count)
    exit()
S=list(S)
S.reverse()
nlst=[0,int(S[0])%P]
for i in range(1,N):
    nlst.append((nlst[i]+int(S[i])*pow(10,i,P))%P)

count=0
for i,n in Counter(nlst).most_common():
    count+=n*(n-1)//2

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

n, m = map(int, input().split())
d = {}
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    if not a in d.keys():
        d[a] = [b]
    else:
        d[a].append(b)
    if not b in d.keys():
        d[b] = [a]
    else:
        d[b].append(a)
    if a == 1:
        ans[b-1] = 1
    if b == 1:
        ans[a-1] = 1

q = [1]
alr = [1]
while not len(q) == 0:
    x = q.pop(0)
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
        if i in alr:
            continue
        alr.append(i)
        q.append(i)
if 0 in ans:
    print('No')
else:
    print('Yes')
    for j in ans[1:]:
        print(j)

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
d = [[] for _ in range(n+1)]
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

q = deque([1])
while not len(q) == 0:
    x = q.popleft()
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
            q.append(i)

if 0 in ans:
    print('No')
else:
    print('Yes')
    s  = "\n".join(map(str, ans[1:]))
    print(s)
### BUGGY CODE ###

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

nums = [0 for _ in range(N)]

for i in range(N):
    nums[i] = nums[i] + A.count(A[i])
    nums[i] = nums[i] + A.count(A[i] +1)
    nums[i] = nums[i] + A.count(A[i] -1)
    
print(max(nums))   

### FIXED CODE ###

import collections

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

l = []
for X in A:
    l += [X-1, X, X+1]

c = collections.Counter(l)
print(c.most_common()[0][1])
### BUGGY CODE ###

import queue

def resolve():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        grid[i] = list(input())


    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.put([i, j])
                distance[i][j] = 0

    # BFS開始
    while not que.empty():

        now = que.get()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = [now[0] + move_y, now[1] + move_x]
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

			# 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # 黒塗りされているなら何もしない
            if grid[target[0]][target[1]] == '#':
                continue

            # キューに追加
            que.put(target)

            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

H,W = map(int,input().split())
INF = 10**10
trout = [[INF for i in range(W)]for i in range(H)]
q = []
for h in range(H):
  row = list(input())
  for w in range(W):
    if row[w]=='#':
      q.append([h,w])
      trout[h][w] = 0
while len(q)!=0:
  h,w = q[0][0],q[0][1]
  del q[0]
  if h<0 or H<=h or w<0 or W<=w:
    continue
  if trout[h][w]!=INF and trout[h][w]!=0:
    continue
  if trout[h][w]==INF:
    s = []
    if 0<=h-1:
      s.append(trout[h-1][w])
    if h+1<H:
      s.append(trout[h+1][w])
    if 0<=w-1:
      s.append(trout[h][w-1])
    if w+1<W:
      s.append(trout[h][w+1])
    trout[h][w] = min(s)+1
  q.append([h-1,w])
  q.append([h+1,w])
  q.append([h,w-1])
  q.append([h,w+1])
res = 0
for h in range(H):
  res = max([res]+trout[h])
print(res)

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
S = [[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            S[h][w] = H*W
for h in range(H):
    a = 0
    for w in range(W):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for w in range(W)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
for w in range(W):
    a = 0
    for h in range(H):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for h in range(H)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
ans = H*W
for h in range(H):
    for w in range(W):
        ans = min(ans,S[h][w])
print(H*W-ans)
### BUGGY CODE ###

from fractions import gcd

n,m = map(int,input().split())
x = [abs(int(i)-m) for i in input().split()]

while len(x)!=1:
    x = x[:-2] + [gcd(x[-2],x[-1])]

print(x[0])


### FIXED CODE ###

from fractions import gcd

n,m = map(int,input().split())
x = [abs(int(i)-m) for i in input().split()]

res = x[0]

for i in x:
    res = gcd(res,i)

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

import collections
n, x, y = map(int, input().split())
lst = []
for i in range(1, n+1):
  for j in range(i, n+1):
    tmp = min(abs(i-j), abs(x-i)+1+abs(j-y), abs(y-i)+1+abs(x-j))
    lst.append(tmp)
lst = collections.Counter(lst)
for i in range(1, n):
  print(lst[i])

### FIXED CODE ###

import collections
n, x, y = map(int, input().split())
lst = []
for i in range(1, n+1):
  for j in range(i, n+1):
    tmp = min(abs(i-j), abs(x-i)+1+abs(j-y), abs(y-i)+1+abs(x-j))
    lst.append(tmp)
lst = collections.Counter(lst)
for i in range(1, n):
  print(lst[i])
### BUGGY CODE ###

k = int(input())
a=7
i=1
while i <= 10000000:
  if a%k ==0:
    print(i)
    break
  elif k%2 ==0:
    print("-1")
    break
  elif k%5 ==0:
    print("-1")
    break
  i+=1
  a = a + 7*10**(i-1)


### FIXED CODE ###

k = int(input())
if k % 2 == 0 or k%5==0:
    print(-1)
    exit()
a = 7
ans = 1
while True:
    if a % k == 0:
        print(ans)
        exit()
    a = (a*10+7) % k
    ans += 1
### BUGGY CODE ###

def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

def make_divisors2(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    prime_list = prime(max(a))
    prime_count = dict()
    for value in prime_list:
        prime_count[value] = 0
    
    for i in range(n):
        value = a[i]
        divisors = make_divisors(value)
        for d in divisors:
            if d in prime_count:
                c, v = 0, value
                while v%d == 0:
                    c += 1
                    v //= d
                if prime_count[d] < c:
                    prime_count[d] = c
    
    ans = 0
    inf = pow(10, 9)+7
    
    for value in a:
        sub = 1
        for p in prime_list:
            k = prime_count[p]
            v = value
            while v%p == 0:
                v //= p
                k -= 1
            sub *= pow(p, k, inf)
            sub %= inf
        ans += sub
        ans %= inf
    
    print(ans)
    

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import Counter

def prime_factorize(n):
    ans = []
    while not n%2:
        ans.append(2)
        n //= 2
    mod = 3
    while mod**2 <= n:
        if n%mod == 0:
            ans.append(mod)
            n //= mod
        else:
            mod += 2
    if n != 1:
        ans.append(n)
    counter = Counter(ans)
    return counter

def main():
    input = sys.stdin.readline
    mod = pow(10,9)+7
    n = int(input())
    a = [int(x) for x in input().split()]
    
    prime_list = dict()
    for i in range(n):
        primes = prime_factorize(a[i])
        for key, value in primes.items():
            if key in prime_list:
                if prime_list[key] < value:
                    prime_list[key] = value
            else:
                prime_list[key] = value
    
    L = 1
    for key, value in prime_list.items():
        L *= pow(key, value, mod)
        L %= mod
        
    ans = 0
    for i in range(n):
        ans += (L*pow(a[i], mod-2, mod))%mod
        ans %= mod
    
    print(ans)
            


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

n,k=map(int,input('').split(' '))
s=0
h=0

while s==0:
    h=n
    n=n-k
    if n<0:
        n=n*(-1)
    if h>n:
        s=0
    else:
        s=1
        n=h

print(n)

### FIXED CODE ###

n,k=map(int,input('').split(' '))
s=0
h=0

n=n%k
while s==0:
    h=n
    n=n-k
    if n<0:
        n=n*(-1)
    if h>n:
        s=0
    else:
        s=1
        n=h

print(n)
### BUGGY CODE ###

K, S = map(int, input().split())
ans = 0
for X in range(min(K+1, S+1)):
    for Y in range(min(K+1, S+1)):
        for Z in range(min(K+1, S+1)):
            ans += (S - (X+Y)) == Z
print(ans)


### FIXED CODE ###

K, S = map(int, input().split())
ans = 0
for X in range(min(K+1, S+1)):
    for Y in range(min(K+1, S+1)):
        ans += 0 <= (S - (X + Y)) <= K
print(ans)
### BUGGY CODE ###

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

#二分累乗法
#nnが1以上の時使える
#powと同じ
#aa**nn
#2**35=2*2**2)
def powT(aa,nn):
	if nn==1:
		return aa
	if nn%2==0:
		v = powT(aa,nn//2)**2
	else:
		v = aa*powT(aa,nn//2)**2
	return v

#二分累乗法
#pow()%10**9
def powTmod(aa,nn):
	mod=10**9+7
	if nn==1:
		return aa
	if nn%2==0:
		v = powTmod(aa,nn//2)**2
	else:
		v = aa*powTmod(aa,nn//2)**2
	return v%(mod)

#nCa mod(10**9+7)
#フェルマーの小定理
def powTnCa(n,a):
	temp=1
	mod=10**9+7
	for i in range(n-a+1,n+1):
		temp*=i%mod
	temp2=1
	for i in range(1,a+1):
		temp2*=i%mod
	temp2=powTmod(temp2,10**9+7-2)

	return temp*temp2%mod

result=powT(2,n)-powTnCa(n,a)-powTnCa(n,b)-1

print(result)








### FIXED CODE ###

mod = 10**9 + 7
n, a, b = map(int, input().split())
ans = pow(2, n, mod) - 1

for r in [a, b]:
    x = 1
    for i in range(r):
        x *= n-i
        x %= mod
        x *= pow(i+1, mod-2, mod)
        x %= mod
    ans = (ans + mod-x)%mod

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

import math

def siki(A, B, X):
	return math.floor((A*X)/B) - A*math.floor(X/B)

A,B,N = map(int,input().split())
x = N
max_value = 0

if N < B:
	k = N
else:
	k = B
for i in range(1, k+1):
	if max_value < siki(A,B,i):
		max_value = siki(A,B,i)

print(max_value)


### FIXED CODE ###

import math

def f(A, B, X):
	return math.floor((A*X)/B) - A*math.floor(X/B)

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

if N < B:
	print(f(A,B,N))
else:
	print(f(A,B,B-1))
### BUGGY CODE ###

import bisect
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')
MAXINT = sys.maxsize

N, Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = np.array([int(input()) for _ in range(Q)])

ans = np.full(Q, np.inf)

for s, t, x in sorted(STX, key=lambda stx: -stx[2]):
    # [lo, hi) に出発した人は x で止まる
    lo = bisect.bisect_left(D, s - x)
    hi = bisect.bisect_left(D, t - x)
    ans[lo:hi] = x

for a in ans:
    print(int(a) if a < np.inf else -1)


### FIXED CODE ###

import bisect
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, Q = list(map(int, next(sys.stdin).split()))
STX = [list(map(int, next(sys.stdin).split())) for _ in range(N)]
D = [int(next(sys.stdin)) for _ in range(Q)]

ans = [-1 for _ in range(Q)]
nexts = [-1 for _ in range(Q)]

for s, t, x in sorted(STX, key=lambda stx: (stx[2], stx[1])):
    # [lo, hi) に出発した人は x で止まる
    # x の小さい順にソート済みなのでここで確定
    lo = max(0, bisect.bisect_left(D, s - x))
    hi = min(len(D), bisect.bisect_left(D, t - x))

    p = lo
    while p < hi:
        if nexts[p] == -1:
            ans[p] = x
            nexts[p] = hi
            p += 1
        else:
            prev = p
            p = nexts[p]
            nexts[prev] = hi

for a in ans:
    print(int(a))
### BUGGY CODE ###


import heapq

n,k,*td=map(int,open(0).read().split())
td = [[t,d] for t,d in zip(td[::2],td[1::2])]
td = sorted(td,key = lambda x:x[1],reverse=True)

score = [0] * k
taste_sum = 0
extra_taste = []
eat_num = 0
eat_kind = set()

for t,d in td:
    if t in eat_kind:
        if eat_num == k:
            continue
        else:
            heapq.heappush(extra_taste, d)
            eat_num += 1
    else:
        eat_kind.add(t)
        taste_sum += d
        eat_num += 1
        if eat_num > k:
            eat_num -= 1
            heapq.heappop(extra_taste)
    
    if eat_num == k:
        score[len(eat_kind)-1] = len(eat_kind)**2 + taste_sum + sum(extra_taste)
            
    if len(eat_kind) == k:
        break
print(max(score))

### FIXED CODE ###


import heapq

n,k,*td=map(int,open(0).read().split())
td = [[t,d] for t,d in zip(td[::2],td[1::2])]
td = sorted(td,key = lambda x:x[1],reverse=True)

score = [0] * k
taste_sum = 0
extra_taste = []
eat_num = 0
eat_kind = set()

for t,d in td:
    if t in eat_kind:
        if eat_num == k:
            continue
        else:
            heapq.heappush(extra_taste, d)
            taste_sum += d
            eat_num += 1
    else:
        eat_kind.add(t)
        taste_sum += d
        eat_num += 1
        if eat_num > k:
            eat_num -= 1
            taste_sum -= heapq.heappop(extra_taste)
    
    if eat_num == k:
        score[len(eat_kind)-1] = len(eat_kind)**2 + taste_sum
            
    if len(eat_kind) == k:
        break
print(max(score))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import heapq

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=[]
b=10**6+1
bb=b*b
Q.append(0+(x1-1)*b+(y1-1)*bb)
MAP[x1-1][y1-1]=0

while Q:
    P=heapq.heappop(Q)
    y=P//bb
    x=(P%bb)//b
    c=P%b

    if MAP[x][y]<c:
        continue

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            MAP[x+i][y]=MAP[x][y]+1
            heapq.heappush(Q,(MAP[x][y]+1+(x+i)*b+y*bb))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            MAP[x-i][y]=MAP[x][y]+1
            heapq.heappush(Q,(MAP[x][y]+1+(x-i)*b+y*bb))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            MAP[x][y+i]=MAP[x][y]+1
            heapq.heappush(Q,(MAP[x][y]+1+x*b+(y+i)*bb))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            MAP[x][y-i]=MAP[x][y]+1
            heapq.heappush(Q,(MAP[x][y]+1+x*b+(y-i)*bb))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=deque()
Q.append((x1-1,y1-1))
MAP[x1-1][y1-1]=0

while Q:
    x,y=Q.pop()

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            if MAP[x+i][y]==1<<30:
                MAP[x+i][y]=MAP[x][y]+1
                Q.appendleft((x+i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            if MAP[x-i][y]==1<<30:
                MAP[x-i][y]=MAP[x][y]+1
                Q.appendleft((x-i,y))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            if MAP[x][y+i]==1<<30:
                MAP[x][y+i]=MAP[x][y]+1
                Q.appendleft((x,y+i))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            if MAP[x][y-i]==1<<30:
                MAP[x][y-i]=MAP[x][y]+1
                Q.appendleft((x,y-i))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])
### BUGGY CODE ###

N = int(input())

a = 1
b = N

for i in range(1, N):
    if N % i == 0:
        j = N // i
        if (i + j) < (a + b):
            a = i
            b = j

print(a + b -2)

### FIXED CODE ###

import math
N = int(input())
a = 1
b = N
nn = math.sqrt(N)
n = math.ceil(nn)

for i in range(2, n+1):
    if N % i == 0:
        j = N // i    
        if (i + j) < (a + b):
            a = i
            b = j

print(a + b -2)