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

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, K = [int(x) for x in input().split()]
    P = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]

    ans = -float("inf")
    for i in range(N):
        next = P[i] - 1
        visited = set()
        cnt = 0
        tmp = 0
        f = False
        while next not in visited:
            tmp += C[next]
            ans = max(ans, tmp)
            cnt += 1
            if cnt == K:
                f = True
                break
            visited.add(next)
            next = P[next] - 1

        if f or cnt <= 0:
            continue

        q, r = divmod(K, cnt)
        tmp *= q
        cnt = 0
        while True:
            tmp += C[next]
            ans = max(ans, tmp)
            cnt += 1
            if cnt == r:
                break
            next = P[next] - 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, K = [int(x) for x in input().split()]
    P = [int(x) - 1 for x in input().split()]
    C = [int(x) for x in input().split()]

    ans = max(C)
    for i in range(N):
        next = P[i]
        cnt = 0
        tmp = 0

        while True:
            tmp += C[next]
            ans = max(ans, tmp)
            cnt += 1
            if cnt == K or next == i:
                break
            next = P[next]

        if cnt == K or tmp <= 0:
            continue

        q = K // cnt
        r = K % cnt
        next = P[i]
        if q != 0:
            tmp *= (q - 1)
            q -= 1
            r += cnt
            ans = max(ans, tmp)
        else:
            tmp = 0
        while r > 0:
            tmp += C[next]
            ans = max(ans, tmp)
            next = P[next]
            r -= 1
    print(ans)


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

def main():
    s = input()
    k = int(input())
    ss = set()
    for i in range(len(s)):
        for j in range(i+1, len(s)+1):
            ss |= {s[i:j]}
    print(sorted(ss)[k-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

s = input()
k = int(input())
n = len(s)
if n == 1:
    print(s)
elif n == 2:
    l2 = sorted(list(set([s[i:i+2] for i in range(n-1)])))
    print(l2[0])
elif n == 3:
    l1 = list(set(s))
    l2 = list(set([s[i:i+2] for i in range(n-1)]))
    l3 = list(set([s[i:i+3] for i in range(n-2)]))
    out = sorted(l1 + l2 + l3)
    print(out[k-1])
elif n == 4:
    l1 = list(set(s))
    l2 = list(set([s[i:i+2] for i in range(n-1)]))
    l3 = list(set([s[i:i+3] for i in range(n-2)]))
    l4 = list(set([s[i:i+4] for i in range(n-3)]))
    out = sorted(l1 + l2 + l3 + l4)
    print(out[k-1])
else:
    l1 = list(set(s))
    l2 = list(set([s[i:i+2] for i in range(n-1)]))
    l3 = list(set([s[i:i+3] for i in range(n-2)]))
    l4 = list(set([s[i:i+4] for i in range(n-3)]))
    l5 = list(set([s[i:i+5] for i in range(n-4)]))
    out = sorted(l1 + l2 + l3 + l4 + l5)
    print(out[k-1])
### BUGGY CODE ###

import numpy as np
N = int(input())
An = list(map(int, input().split()))
ans = 0
ng = set()
a_An = np.array(An)
for i, a in enumerate(An):
    temp = a_An / a
    temp[i] = 0.1
    check = np.where(temp % 1 == 0)
    check = check[0]
    # check = np.delete(check, np.where(check == i))
    # check = check[check != i]
    if len(check) > 0:
        ng = ng | set(check)
print(N-len(ng))



### FIXED CODE ###

N = int(input())
An = list(map(int, input().split()))
An.sort()
max_n = max(An)
dp = [0] * (max_n + 1)
for i in range(N):
    if dp[An[i]] != 0:
        dp[An[i]] = 2
        continue
    for j in range(1, max_n//An[i] + 1):
        dp[An[i]*j] += 1
ans = 0
for a in An:
    if dp[a] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

def calc(list_of_int):
  # 1と0で構成されているとする
  length = len(list_of_int)
  res = list_of_int[0]
  keisu = 1
  for i,r in zip(list_of_int[1:],range(N-1)):
    
    keisu = keisu*(N-r-1)//(r+1)
    # print(keisu,(N-r)-1,(r+1))
    res = (res + (keisu*i) )% 2
  return res
  
N = int(input())
S = input()
a = [int(s)-1 for s in S]
if 1 in a:
  print(calc(a))
else:
  print(calc(list(map(lambda x:x//2,a)))*2)

### FIXED CODE ###

N = int(input())
S = input()
a = [int(s)-1 for s in S]


from collections import defaultdict

r = 1
d = defaultdict(int)
while 2**r  <= N:
  for i in range(1,N):
    if i*(2**r) <= N:
      d[i*(2**r)] += 1
    else:
      break
  r+=1

def calc(list_of_int):
  # 1と0で構成されているとする
  length = len(list_of_int)
  res = list_of_int[0]
  
  keisu = 0
  for i,r in zip(list_of_int[1:], range(N-1)):
    keisu += d[N-r-1]-d[r+1]
    res = (res + ((2 if keisu>0 else 1)*i) )% 2
  return res

if 1 in a:
  print(calc(a))
else:
  print(calc(list(map(lambda x:x//2,a)))*2)
### BUGGY CODE ###

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

for _ in range(n):
    _list.append(int(input()))

for i in range(n):
    if i==0:
        tmp_list = _list[1:]
        tmp_max = max(tmp_list)
        print(tmp_max)
        
        if _list[0] < tmp_max:
            maxi = tmp_max
        else:
            maxi = _list[0]

    elif 0<i<n-1:
        if _list[i] < maxi:
            print(maxi)
        else:
            tmp_list = _list[:i] + _list[i+1:]
            print(max(tmp_list))

    else:
        if _list[i] < maxi:
            print(maxi)
        else:
            tmp_list = _list[:n-1]
            print(max(tmp_list))

### FIXED CODE ###

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

for _ in range(n):
    a.append(int(input()))

b = sorted(a, reverse=True)

for i in range(n):
    if a[i] == b[0]:
        print(b[1])
    else:
        print(b[0])
### BUGGY CODE ###

q=input()
a=input()

q1=q.split(" ")
a1=list(map(int,a.split(" ")))

sumsum=0
for i in range(len(a1)-int(q1[1])+1):
    sum1=sum(a1[i:i+int(q1[1])])
    if(sumsum<sum1):
        sumsum=sum1
sumsum+=int(q1[1])
print(sumsum/2)


### FIXED CODE ###

q1=list(map(int,input().split(" ")))
a1=list(map(int,input().split(" ")))


sum1=sum(a1[:q1[1]])
sumsum=sum1
for i in range(q1[0]-q1[1]):
    sum1=sum1+a1[i+q1[1]]-a1[i]
    if(sumsum<sum1):
        sumsum=sum1
sumsum+=q1[1]
print(sumsum/2)
### BUGGY CODE ###

c={}
for _ in range(int(input())): s=input(); c[s]=c.get(s,0)+1
print(*sorted(k for k in c if c[k]==max(c.values())))

### FIXED CODE ###

N = int(input())
count = {}
for i in range(N):
    s = input()
    count.setdefault(s, 0)
    count[s] += 1
p = max(count.values())
ans = []
for k in count.keys():
    if count[k] == p:
        ans.append(k)
ans.sort()
for a in ans:
    print(a)
### BUGGY CODE ###

import heapq
import sys
input=sys.stdin.readline

N,Q=map(int,input().split())
H=[]
for i in range(N):
    s,t,x=map(int,input().split())
    H.append([s-x,t-x,x])
H.sort()
#print(H)
P=0
q=[]
heapq.heapify(q)
for i in range(Q):
    n=int(input())
    #print("A",len(q))
    if P<N:
        while H[P][0]<=n:
            heapq.heappush(q,[H[P][2],H[P][0],H[P][1]])
            P+=1
            if P==N:
                break
    #print("B",i,len(q))
    if len(q)>0:
        while q[0][2]<=n:
            heapq.heappop(q)
            if len(q)==0:
                break
    if len(q)==0:
        print(-1)
    else:
        print(q[0][0])

### FIXED CODE ###

import heapq
import sys
input=sys.stdin.readline

N,Q=map(int,input().split())
H=[]
for i in range(N):
    s,t,x=map(int,input().split())
    H.append([s-x,t-x,x])
H.sort()
#print(H)
P=0
q=[]
heapq.heapify(q)
for i in range(Q):
    n=int(input())
    #print("A",len(q))
    if P<N:
        while H[P][0]<=n:
            heapq.heappush(q,[H[P][2],H[P][0],H[P][1]])
            P+=1
            if P==N:
                break
    #print("B",i,len(q))
    if len(q)>0:
        while q[0][2]<=n:
            heapq.heappop(q)
            if len(q)==0:
                break
    if len(q)==0:
        print(-1)
    else:
        print(q[0][0])
### BUGGY CODE ###

import sys
#input = sys.stdin.readline
from collections import deque
N, u, v = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
v-=1
u-=1
que = deque([v])
par = [-1]*N
depth = [-1]*N
depth[v] = 0
while que:
    i = que.popleft()
    d = depth[i]
    for nv in G[i]:
        if depth[nv]>=0:
            continue
        depth[nv] = d+1
        par[nv] = i
        que.append(nv)
d = depth[u]
now = u
m = 0
que = deque([now])
while que:
    i = que.pop()
    m = max(m, depth[i])
    for nv in G[i]:
        if depth[nv]<depth[i]:
            continue
        que.append(nv)
for i in range(d//2):
    pp = par[now]
    que = deque([pp])
    while que:
        i = que.pop()
        m = max(m, depth[i])
        for nv in G[i]:
            if depth[nv]<depth[i] or nv == pp:
                continue
            que.append(nv)
    now = pp
print(m-1)
    






### FIXED CODE ###

import sys
#input = sys.stdin.readline
from collections import deque
N, u, v = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
v-=1
u-=1
que = deque([v])
par = [-1]*N
depth = [-1]*N
depth[v] = 0
while que:
    i = que.popleft()
    d = depth[i]
    for nv in G[i]:
        if depth[nv]>=0:
            continue
        depth[nv] = d+1
        par[nv] = i
        que.append(nv)
d = depth[u]
now = u
m = 0
que = deque([now])
while que:
    i = que.pop()
    m = max(m, depth[i])
    for nv in G[i]:
        if depth[nv]<depth[i]:
            continue
        que.append(nv)
for i in range(d//2):
    pp = par[now]
    que = deque([pp])
    while que:
        i = que.pop()
        m = max(m, depth[i])
        for nv in G[i]:
            if depth[nv]<depth[i] or nv == now:
                continue
            que.append(nv)
    now = pp
print(m-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SI(): return input().split()

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product
from heapq import heapify, heappop, heappush


def solve():
    n = II()
    A = LI()
    th = pow(10, 18)
    ans = 1
    for a in A:
        ans *= a
        # print(a, ans)
        # if ans > th:
        #     print(-1)
        #     return
    if ans > th:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SI(): return input().split()

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product
from heapq import heapify, heappop, heappush


def solve():
    n = II()
    A = LI()
    th = 1_000_000_000_000_000_000
    ans = 1
    if 0 in A:
        print(0)
        return

    for a in A:
        ans *= a
        # print(a, ans)
        if ans > th:
            print(-1)
            return
    print(ans)


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

[N,L] = [int(x) for x in input().split()]
A = {}
B = [0]*N
C = N//L
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    B[i] = x
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        count += 1
        for k in range(L) :
            if j + k not in ANS : ANS[j+k] = i
    if count  > C - 3 : break
        
for i in range(L):
    if i not in ANS : ANS[i] = min(B[:i+1])
for i in range(L,N):
    if i not in ANS : ANS[i] = min(B[i+1-L:i+1])
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
cnt = 0
for i in range(n // r + 1):
    for j in range(n // g + 1):
        c = n - i * r - j * g
        if c % b == 0 and c >= 0:
             cnt += 1
print(cnt)


### FIXED CODE ###

r,g,b,n = map(int,input().split(" "))
cnt = 0
for i in range(n // r + 1):
    for j in range(n // g + 1):
        c = n - i * r - j * g
        if c < 0:
            break
        if c % b == 0:
             cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append(b)
    edge[b].append(a)

color = [0] * N

def dfs(v, c):
    color[v] = c
    now = 0
    for nv in edge[v]:
        if v == nv: continue
        now += 1
        if now == c:
            now += 1
        dfs(nv, now)

dfs(0, 0)
color[0] = max(color)
print(*color, sep="\n")


### FIXED CODE ###

class ColorMgmt:
    from heapq import heappop, heappush
    def __init__(self, n):
        self.colors_hash = [set() for _ in range(n)]
        self.next_colors = [1] * n
    
    def set_color(self, v, c):
        self.colors_hash[v].add(c)
        while self.next_colors[v] in self.colors_hash[v]:
            self.next_colors[v] += 1
    
    def get_color(self, v):
        return self.next_colors[v]


N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for _ in range(N)]
edge_cnt = [0] * N
for idx, (a, b) in enumerate(ab):
    a, b = a-1, b-1
    edge[a].append([b, a, 0, idx])
    edge_cnt[a] += 1
    edge_cnt[b] += 1
K = max(edge_cnt)

next_list = []
now_list = [0]
color_mgmt = ColorMgmt(N)
while len(now_list) > 0:
    for v in now_list:
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            colors1 = color_mgmt.get_color(nextv[1])
            colors2 = color_mgmt.get_color(nextv[0])
            color = max(colors1, colors2)
            color_mgmt.set_color(nextv[1], color)
            color_mgmt.set_color(nextv[0], color)
            edge[v][idx][2] = color
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for edges in edge:
    for e in edges:
        ret.append(e)
ret.sort(key=lambda x:x[3])
print(K)
for r in ret:
    print(r[2])
### BUGGY CODE ###

def main():
    n = int(input())
    l = sorted(list(map(int, input().split())), reverse=True)
    ll = len(l)
    ans = 0

    seen = []
    for i in range(ll):
        for j in range(i+1, ll):
            for k in range(j+1, ll):
                if len(set([l[i], l[j], l[k]])) != 3:
                    continue
                if l[j] + l[k] > l[i] and [i, j, k] not in seen:
                    ans += 1
                    seen.append([i, j, k])
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    l = list(map(int, input().split()))
    ll = len(l)
    ans = 0

    for i in range(ll):
        for j in range(i+1, ll):
            for k in range(j+1, ll):
                if len(set([l[i], l[j], l[k]])) != 3:
                    continue
                item = [l[i], l[j], l[k]]
                if max(item) < sum(item) - max(item):
                    ans += 1
    print(ans)


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

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

if(3*K == S):
  print(1)
  exit()
cnt = 0
for i in range(K+1):
  for j in range(K+2):
    for k in range(K+3):
      if(i+j+k == S):
        cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = 0
for i in range(K+1):
  for j in range(K+1):
    if(S-(i+j) <= K and S-(i+j) >= 0):
      cnt += 1
print(cnt)
### BUGGY CODE ###

H, W, M = map(int, input().split())
targets = [list(map(int, input().split())) for _ in range(M)]
x_counter = [0 for _ in range(W + 1)]
y_counter = [0 for _ in range(H + 1)]
y_index = []
x_index = []
dup = True

for target in targets:
    y_counter[target[0]] += 1
    x_counter[target[1]] += 1

y_max, x_max = max(y_counter), max(x_counter)

for i in range(H + 1):
    if y_counter[i] == y_max:
        y_index.append(i)

for j in range(W + 1):
    if x_counter[j] == x_max:
        x_index.append(j)

for k in y_index:
    for l in x_index:
        if [k, l] not in targets:
            dup = False

if dup:
    print(y_max + x_max - 1)
else:
    print(y_max + x_max)


### FIXED CODE ###

h,w,m=map(int,input().split())
item=[list(map(int,input().split())) for i in range(m)]
row=[0]*h
col=[0]*w
for i in range(m):
    x,y=item[i]
    row[x-1]+=1
    col[y-1]+=1
mr,mc=max(row),max(col)
xr=set([i for i in range(h) if row[i]==mr])
xc=set([i for i in range(w) if col[i]==mc])
check=len(xr)*len(xc)
for i in range(m):
    r,c=item[i]
    if r-1 in xr and c-1 in xc:
        check-=1
print(mr+mc if check>0 else mr+mc-1)
### BUGGY CODE ###

n, m = (int(i) for i in input().split())
a = [int(input()) for i in range(m)]
MOD = 10**9 + 7

d = [0] * (n+5)
d[1] = (1 if len(a) == 0 or a[0] != 1 else 0)
d[2] = (d[1] + 1 if len(a) == 0 or 2 not in a else 0)

for i in range(2,n):
    d[i+1] = d[i] + d[i-1]
    if i+1 in a:
        d[i+1] = 0
print(d[n]%MOD)

### FIXED CODE ###

n, m = (int(i) for i in input().split())
a = {int(input()) for i in range(m)}
MOD = 10**9 + 7

d = [0] * (n+5)
d[1] = (0 if 1 in a else 1)
d[2] = (0 if 2 in a else d[1] + 1)

for i in range(2,n):
    d[i+1] = (d[i] + d[i-1])%MOD
    if i+1 in a:
        d[i+1] = 0
print(d[n]%MOD)
### BUGGY CODE ###

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


for i in range(N):
    SUM=0
    XOR=0
    for j in range(i,N):
        SUM=SUM+A[j]
        XOR=XOR ^ A[j]

        if SUM==XOR:
            count+=1
        else:
            break


print(count)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
count=0
F=0
B=0
SUM=0



while F<N:
    while True:
        SUMtest=SUM+A[B]
        XORtest=SUM^A[B]

        if SUMtest==XORtest:
            if B==N-1:
                for i in range(F,N):
                    count=count+(N-i)
                F=N
                break
                
            else:
                B+=1
                SUM=SUMtest

        else:
            count=count+(B-F)
            SUM=SUM-A[F]
            F+=1
            break


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

# -*- coding: utf-8 -*-
def main():
    N = int(input())
    A  = [int(i) for i in input().split()]
    #ax = itertools.combinations(A, 2)
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            ans = (ans + A[i]*A[j]) % 1000000007
            #print(A[i],A[j],ans)
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
def main():
    N = int(input())
    A  = [int(i) for i in input().split()]
    #N = 100000
    #A = [i for i in range(1,100000)]
    sum_a = sum(A)% 1000000007
    ans = 0
    for i in range(N):
        sum_a = (sum_a - A[i])% 1000000007
        ans = (ans + sum_a*A[i] ) % 1000000007
        #print((sum_a-A[i])*A[i]/2 ,ans)
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import itertools
import collections


def is_anagram(s1, s2):
    c1 = collections.Counter(s1)
    c2 = collections.Counter(s2)
    return c1 == c2


n = int(input())
s = list([input() for _ in range(n)])

summ = 0
for s1, s2 in itertools.combinations(s, 2):
    summ += is_anagram(s1, s2)

print(summ)

### FIXED CODE ###

import math
import collections


def comb(n, r):
    mf = math.factorial
    return mf(n) // (mf(n - r) * mf(r))


n = int(input())
s = [''.join(sorted(list(input()))) for _ in range(n)]
c = collections.Counter(s)
print(sum(comb(a, 2) for a in c.values() if a > 1))
### BUGGY CODE ###


# -*- coding: utf-8 -*-
import math
K=int(input())

count=0

for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            cal=math.gcd(math.gcd(a,b),c) 
            #print(cal)
            count+=cal
            

print(count)

### FIXED CODE ###


# -*- coding: utf-8 -*-
import math
K=int(input())

count=0

for a in range(1,K+1):
    for b in range(a,K+1):
        for c in range(b,K+1):
            cal=math.gcd(math.gcd(a,b),c) 
            #print(cal)
            if a!=b and b!=c:
                count+=cal*6
            elif a==b==c:
                count+=cal
            else:
                count+=cal*3
            

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

import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W, K = map(int, rl().split())
    sy, sx, gy, gx = map(lambda n: int(n) - 1, rl().split())
    c = [rl().rstrip() for _ in range(H)]
    
    INF = 10 ** 10
    cost = [[INF] * W for _ in range(H)]
    cost[sy][sx] = 0
    que = deque([(sy, sx)])
    while que:
        cy, cx = que.popleft()
        for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            for k in range(1, K + 1):
                ny, nx = cy + k * dy, cx + k * dx
                if 0 <= ny < H and 0 <= nx < W:
                    if c[ny][nx] == '@':
                        break
                    if cost[ny][nx] <= cost[cy][cx]:
                        break
                    cost[ny][nx] = cost[cy][cx] + 1
                    que.append((ny, nx))
    print(cost[gy][gx] if cost[gy][gx] != INF else -1)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W, K = map(int, rl().split())
    sy, sx, gy, gx = map(lambda n: int(n) - 1, rl().split())
    c = [rl().rstrip() for _ in range(H)]
    
    INF = 10 ** 10
    cost = [[INF] * W for _ in range(H)]
    cost[sy][sx] = 0
    que = deque([(sy, sx)])
    while que:
        cy, cx = que.popleft()
        for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            for k in range(1, K + 1):
                ny, nx = cy + k * dy, cx + k * dx
                if 0 <= ny < H and 0 <= nx < W:
                    if c[ny][nx] == '@':
                        break
                    if cost[ny][nx] <= cost[cy][cx]:
                        break
                    ncost = cost[cy][cx] + 1
                    if ncost < cost[ny][nx]:
                        cost[ny][nx] = ncost
                        que.append((ny, nx))
    print(cost[gy][gx] if cost[gy][gx] != INF else -1)


if __name__ == '__main__':
    solve()