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

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(input())
lines = readlines()
edge = np.array([line.split() for line in lines[:N-1]],np.int64).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
Q, K = map(int,lines[N-1].split())
#XY = [list(map(int,line.split())) for line in lines[N:]]
XY = np.array([line.split() for line in lines[N:]],np.int64).T
distance_mat_K = dijkstra(graph, directed = False, indices = K-1)

for i in range(Q):
  print(int(distance_mat_K[XY[0][i]-1]+ distance_mat_K[XY[1][i]-1]))



### FIXED CODE ###

import sys
import numpy as np
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import defaultdict

N = int(input())
lines = readlines()
graph = defaultdict(list)
for line in lines[:N-1]:
  a,b,c = map(int,line.split())
  graph[a].append((b,c))
  graph[b].append((a,c))
Q, K = map(int,lines[N-1].split())
XY = np.array([line.split() for line in lines[N:]],np.int64)

def degreesOfSeparation(graph,start):
    if start not in graph:
        return -1
    visited = set()
    frontier = set()
    table = [0] * (len(graph) + 1)
    degrees = 0
    visited.add(start)
    frontier.add(start)
    while len(frontier) > 0:
        #print(frontier,":",degrees)
        #degrees += 1
        newfront = set()
        for g in frontier:
            for next in graph[g]:
                if next[0] not in visited:
                    visited.add(next[0])
                    newfront.add(next[0])
                    table[next[0]] += next[1] + table[g]
        frontier = newfront
    return table
table = degreesOfSeparation(graph,K)
for q in range(Q):
  print(table[XY[q][0]] + table[XY[q][1]])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  n, m = map(int, input().split())
  U = 2**n
  dp = [ [float("inf")]*(2**n) for _ in range(m) ]
  dp[0][0] = 0
  for i in range(1, m):
    a, b = map(int, input().split())
    k = map(int, input().split())
    c = 0
    for l in k:
      c += 2**(l-1)
    for j in range(U):
      dp[i][j] = min(dp[i-1][j&(~c)]+a, dp[i-1][j])

  if dp[m-1][2**n-1] == float("inf"):
    print(-1)
  else:
    print(dp[m-1][2**n-1])
    
if __name__ == "__main__":
  main()

### FIXED CODE ###

n, m = map(int, input().split())
dp = [ [float("inf")]*(2**n) for _ in range(m) ]
dp[0][0] = 0
for i in range(1, m):
  a, b = map(int, input().split())
  k = set(map(int, input().split()))
  c = 0
  for l in k:
    c += 2**(l-1)
  for j in range(2**n):
    dp[i][j] = min(dp[i-1][j&(~c)]+a, dp[i-1][j])

if dp[m-1][2**n-1] == float("inf"):
  print(-1)
else:
  print(dp[m-1][2**n-1])
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

#mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

def main():
	h,w=map(int,input().split())
	
	G=[[0]*w for i in range(h)]
	
	for i in range(h):
		A=list(map(int,input().split()))
		for j in range(w):
			G[i][j]+=A[j]
	for i in range(h):
		B = list(map(int, input().split()))
		for j in range(w):
			G[i][j] =abs(G[i][j]-B[j])
	M=(h+w)*80
	
	li = [[[] for i in range(w)] for j in range(h)]
	for i in range(h):
		for j in range(w):
			if i == j == 0:
				li[i][j].append(G[i][j])
			elif i == 0:
				for k in li[i][j - 1]:
					aa = abs(k - G[i][j])
					bb = abs(k + G[i][j])
					if aa <= M:
						li[i][j].append(aa)
					if abs(bb) <= M:
						li[i][j].append(bb)
			elif j == 0:
				for k in li[i - 1][j]:
					aa = abs(k - G[i][j])
					bb = abs(k + G[i][j])
					if aa <= M:
						li[i][j].append(aa)
					if abs(bb) <= M:
						li[i][j].append(bb)
			else:
				for k in li[i - 1][j]:
					aa = abs(k - G[i][j])
					bb = abs(k + G[i][j])
					if aa <= M:
						li[i][j].append(aa)
					if abs(bb) <= M:
						li[i][j].append(bb)
				for k in li[i][j - 1]:
					aa = abs(k - G[i][j])
					bb = abs(k + G[i][j])
					if aa <= M:
						li[i][j].append(aa)
					if abs(bb) <= M:
						li[i][j].append(bb)
			
			s = set(li[i][j])
			li[i][j] = list(s)
	
	print(min(li[h - 1][w - 1]))


if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

def main():
	h, w = map(int, input().split())
	
	G = [[0] * w for i in range(h)]
	A = [0]*h
	B = [0]*h
	
	for i in range(h):
		A[i] = list(map(int, input().split()))
	for i in range(h):
		B[i] = list(map(int, input().split()))
	
	for i in range(h):
		for j in range(w):
			G[i][j]=abs(A[i][j]-B[i][j])

	M = (h + w) * 80

	li = [[[0] * M for i in range(w)] for j in range(h)]
	
	li[0][0][G[0][0]] = 1
	for i in range(h):
		for j in range(w):
			for k in range(M):
				
				if li[i][j][k] == 1:
					if i < h - 1:
						li[i + 1][j][abs(k - G[i+1][j])] = 1
						li[i + 1][j][abs(k + G[i+1][j])] = 1
					if j < w - 1:
						li[i][j + 1][abs(k - G[i][j+1])] = 1
						li[i][j + 1][abs(k + G[i][j+1])] = 1

	for i in range(M):
		if li[h-1][w - 1][i] == 1:
			print(i)
			exit(0)


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

from collections import Counter

N = int(input())

s = [[] for _ in range(N)]
check = []
ans = []
for x in range(N):
    for c in input():
        s[x].append(c)

for x in s:
    check.append(Counter(x))

for x in range(N):
    if check:
        cc = check.pop(0)
        ans.append(check.count(cc))


print(sum(ans))

### FIXED CODE ###

from collections import Counter

N = int(input())

# check = []
# ans = {}
# answer = 0
# for _ in range(N):
#     s = Counter(input())
#     if s not in check:
#         check.append(s)
#         ans[str(sorted(s.items(), key=lambda x:x[0]))] = 0
#
#     else:
#         ans[str(sorted(s.items(), key=lambda x:x[0]))] += 1
#         answer += ans[str(sorted(s.items(), key=lambda x:x[0]))]
#
# print(answer)

ans = {}
answer = 0
for _ in range(N):
    s = "".join(sorted(input()))

    if s not in ans:
        ans[s] = 0

    else:
        ans[s] += 1
        answer += ans[s]

print(answer)
### BUGGY CODE ###

S = input()
T = input()

dp = [[0]*(len(T)+1) for _ in range(len(S)+1)]
prev = [[(-1,-1)]*(len(T)+1)for _ in range(len(S)+1)]

res = ""

for i in range(1,len(S)+1):
    for j in range(1,len(T)+1):
        if S[i-1] != T[j-1] or dp[i-1][j] != dp[i-1][j-1] or dp[i][j-1] != dp[i-1][j-1]:
            if dp[i-1][j] > dp[i][j-1]:
                dp[i][j] = dp[i-1][j]
                prev[i][j] = (i-1,j)
            else:
                dp[i][j] = dp[i][j-1]
                prev[i][j] = (i,j-1)
        else:
            dp[i][j] = dp[i-1][j-1] + 1
            res += S[i-1]
            prev[i][j] = (-2,-2)
to = (len(S), len(T))
res = ""
while to != (-1,-1):
    p = prev[to[0]][to[1]]
    if p[0] == -2:
        res += S[to[0]-1]
        to = (to[0]-1, to[1]-1)
    else:
        to = p
print(res[::-1])





### FIXED CODE ###

import sys
sys.setrecursionlimit(3003)
def main():
    s = " "+input()
    N = len(s)-1

    t = " "+input()
    M = len(t)-1
    if N < M:
        N, M = M, N
        s, t = t, s
    # dp[i][j] := sのi文字目, tのj文字目までを使ったLCSの長さ
    dp = [[-1]*(M+1) for i in range(N+1)]
    dp[0] = [0]*(N+1)
    for i in range(N+1):
        dp[i][0] = 0
    for i in range(1, N+1):
        for j in range(1, M+1):
            
            if s[i] == t[j]:
                dp[i][j] = dp[i-1][j-1]+1
            elif s[i] != t[j]:
                if dp[i-1][j] > dp[i][j-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
    print(get(s, t, N, M, dp))

def get(s, t, i, j, dp):
    if i == 0 or j == 0:
        return ""

    if s[i]==t[j]:
        return get(s, t, i-1, j-1, dp) + s[i]
    elif s[i] != t[j]:
        if dp[i-1][j] > dp[i][j-1]:
            return get(s, t, i-1, j, dp)
        else:
            return get(s, t, i, j-1, dp)


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

import sys
input = sys.stdin.readline

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

for _ in range(K):
    B = [0]*N
    for i, a in enumerate(A):
        bottom = i - a
        top = i + a + 1
        if bottom < 0:
            bottom = 0
        if top > N:
            top = N
        B[bottom:top] = list(map(lambda x: x+1, B[bottom:top]))
    A = B[:]

ans = ' '.join(list(map(str, A)))
print(ans)


### FIXED CODE ###

from numba import jit
import sys
input = sys.stdin.readline


@jit
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    for _ in range(K):
        B = [0]*(N+1)
        for i, a in enumerate(A):
            B[max(0, i-a)] += 1
            B[min(N, i+a+1)] -= 1
        for j in range(1, N):
            B[j] += B[j-1]
        if A == B[:-1]:
            A = B[:-1]
            break
        A = B[:-1]

    ans = ' '.join(list(map(str, A)))
    print(ans)


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

n,*l=map(int,open(0).read().split())
a=1
for i in sorted(l): a*=i
print([a,-1][a>10**18])

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
if 0 in l:
  print(0)
  exit()
a=1
for i in l:
  a*=i
  if a>10**18:
    print(-1)
    exit()
print(a)
### BUGGY CODE ###

import itertools
N,M,Q=map(int,input().split())
ABCD=[list(map(int,input().split())) for _ in range(Q)]
tl=[]
for i in range(1,M+1):
    tl.append([i])
for i in range(N):
    t=[]
    for l in tl:
        for j in range(1,M+1):
            if l[-1]<=j:
                t.append(l+[j])
    tl=t[:]
ans=0
for l in tl:
    t=0
    for a,b,c,d in ABCD:
        if l[b-1]-l[a-1]==c:
            t+=d
    ans=max(ans,t)
print(ans)

### FIXED CODE ###

import itertools
N,M,Q=map(int,input().split())
ABCD=[list(map(int,input().split())) for _ in range(Q)]
tl=[]
for i in range(1,M+1):
    tl.append([i])
for i in range(N):
    t=[]
    for l in tl:
        for j in range(1,M+1):
            if l[-1]<=j:
                t.append(l+[j])
    tl=t[:]
ans=0
for l in tl:
    t=0
    for a,b,c,d in ABCD:
        if l[b-1]-l[a-1]==c:
            t+=d
    ans=max(ans,t)
print(ans)
### BUGGY CODE ###

def get_cost_change_black(S):
    return S.count(".")

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

indexs = [i for i, x in enumerate(S) if x == "#"]
if len(indexs) == 0:
    print(0)
else:
    answer = 10000000
    change_white = 0
    for i in indexs:
        x = change_white + get_cost_change_black(S[i:])
        if x < answer:
            answer = x
        change_white = change_white + 1
        if change_white >= x:
            break
    print(answer)


### FIXED CODE ###

def get_cost_change_black(S):
    return S.count(".")

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

indexs = [i for i, x in enumerate(S) if x == "#"]
if len(indexs) == 0:
    print(0)
else:
    answer = 10000000000
    change_white = 0
    change_black = get_cost_change_black(S[indexs[0]:])
    for i, ind in enumerate(indexs):
        x = change_white + change_black
        if x < answer:
            answer = x
        change_white = change_white + 1
        if i == len(indexs) - 1:
            if change_white < answer:
                answer = change_white
            break
        change_black = change_black - (indexs[i+1] - indexs[i] - 1)
    print(answer)
### BUGGY CODE ###

A,B,q = map(int,input().split())
import bisect
L1=[]
L2=[]
for _ in range(A):
    L1.append(int(input()))
for _ in range(B):
    L2.append(int(input()))
L1 = [-10**20] + L1 + [10**20]
L2 = [-10**20] + L2 + [10**20]
for _ in range(q):
    Q = int(input())
    cand = []
    for i in range(2):
        for j in range(2):
                t =  L1[bisect.bisect_left(L1,Q)-i]
                tmp = abs (t - Q)
                tmp  +=  abs(L2[bisect.bisect_left(L2,t)-j]  - t)
                cand.append(tmp)
                t =  L2[bisect.bisect_left(L2,Q)-i]
                tmp = abs (t - Q)
                tmp  +=  abs(L1[bisect.bisect_left(L1,t)-j]  - t)
                cand.append(tmp)
    print(min(cand))



### FIXED CODE ###

A,B,Q = map(int,input().split())
import bisect
s=[]
t=[]
for _ in range(A):
    s.append(int(input()))
for _ in range(B):
    t.append(int(input()))
s = [-10**20] + s + [10**20]
t = [-10**20] + t + [10**20]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = 10**20
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###

import re

def main():
    NumString = int(input())
    String = input()
    
    total_ans = 0
    for i in range(NumString):
        i_RGB = 'RGB'
        for j in range(i+1, NumString):
            j_RGB = re.sub(String[i], '', i_RGB)
            if String[i] == String[j]:
                continue

            k_RGB = re.sub(String[j], '', j_RGB)
            total_ans += String.count(k_RGB, j+1)
            if (j + (j-i)) < NumString and String[j + (j-i)] == k_RGB:
                total_ans -= 1
    
    print(total_ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

NumString = int(input())
String = input()

r_string_num, g_string_num, b_string_num = 0, 0, 0
for i_string in String:
    if i_string == 'R':
        r_string_num += 1
    elif i_string == 'G':
        g_string_num += 1
    else:
        b_string_num += 1
    
total_ans = r_string_num * g_string_num * b_string_num

exclude_num = 0
for i in range(NumString-2):
    for j in range(i+1, NumString-1):
        if (2*j - i) < NumString and String[i] != String[j] and \
            String[j] != String[2*j-i] and String[i] != String[2*j-i]:
            exclude_num += 1

total_ans -= exclude_num

print(total_ans)
### BUGGY CODE ###

syogens = []
n = int(input())
for i in range(n):
    syogens.append([])
    a = int(input())
    for j in range(a):
        m,s=map(int,input().split())
        syogens[i].append([m,s])
ok = 0
for i in range(2**n):
    ng = False
    i2 = format(i,"b").zfill(16)
    i2 = i2[::-1]
    for k,j in enumerate(syogens):
        for l,j2 in enumerate(j):
            if i2[k] == "1":#i2[k]
                if str(j2[1]) != i2[j2[0]-1]:#証言が正しいかチェック
                    ng = True#証言が矛盾していればNG
    if ng:
        ng = False
    else:
        if i2.count("1") > ok: ok = i2.count("1") 
print(ok)

### FIXED CODE ###

syogens = []
n = int(input())
for i in range(n):
    syogens.append([])
    a = int(input())
    for j in range(a):
        m,s=map(int,input().split())
        syogens[i].append([m,s])
ok = 0
for i in range(2**n):
    ng = False
    i2 = format(i,"b").zfill(16)
    i2 = i2[::-1]
    for k,j in enumerate(syogens):
        if i2[k] == "1":
            for l,j2 in enumerate(j):
                if str(j2[1]) != i2[j2[0]-1]:
                    ng = True
    if ng:
        ng = False
    else:
        if i2.count("1") > ok: ok = i2.count("1") 
print(ok)
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
s=[list(input()) for _ in range(H)]

white=sum([1 if s[y][x]=='.' else 0 for x in range(W) for y in range(H)])
used=[[False for x in range(W)] for y in range(H)]
q = deque([(0,0,1)])
while True:
    if len(q)==0:
        print(-1)
        break
    x,y,l=q.popleft()
    if x==W-1 and y==H-1:
        print(white-l)
        break
    used[y][x]=True
    for d in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx=x+d[0]
        ny=y+d[1]
        if ny>=0 and ny<H and nx>=0 and nx<W and not used[ny][nx]:
            if s[ny][nx]=='.':
                q.append((nx,ny,l+1))
    


### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
white=0
s=[]
for y in range(H):
    line=input()
    white+=line.count('.')
    s.append(list(line))

q = deque([(0,0,1)])
q_append=q.append
q_popleft=q.popleft
while q:
    x,y,l=q_popleft()
    if s[y][x]!='.':
        continue
    if x==W-1 and y==H-1:
        print(white-l)
        break
    s[y][x]='*'
    for d in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx, ny=(x+d[0],y+d[1])
        if 0<=nx<W and 0<=ny<H:
            q_append((nx,ny,l+1))
else:
    print(-1)
### BUGGY CODE ###

# import queue
# from collections import deque

h, w = map(int, input().split())

grid = [[1] * (w + 2)]
for _ in range(h):
    grid.append([1] + [1 if x == '#' else 0 for x in input()] + [1])
grid.append([1] * (w + 2))

# q = deque()
q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if grid[i][j] == 1:
            q.append((i, j))

cnt = 0
while True:
    qq = []
    for (i, j) in q:
        # i, j = q.pop()
        if grid[i + 1][j] == 0:
            grid[i + 1][j] = 1
            qq.append((i + 1, j))
        if grid[i - 1][j] == 0:
            grid[i - 1][j] = 1
            qq.append((i - 1, j))
        if grid[i][j + 1] == 0:
            grid[i][j + 1] = 1
            qq.append((i, j + 1))
        if grid[i][j - 1] == 0:
            grid[i][j - 1] = 1
            qq.append((i, j - 1))

    if not qq:
        break
    cnt += 1
    q = qq

print(cnt)


### FIXED CODE ###

h, w = map(int, input().split())

grid = [[True] * (w + 2)]
for _ in range(h):
    grid.append([True] + [x == '#' for x in input()] + [True])
grid.append([True] * (w + 2))

q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if grid[i][j] is True:
            q.append((i, j))

cnt = 0
while q:
    qq = []
    for i, j in q:
        if not grid[i + 1][j]:
            grid[i + 1][j] = True
            qq.append((i + 1, j))
        if not grid[i - 1][j]:
            grid[i - 1][j] = True
            qq.append((i - 1, j))
        if not grid[i][j + 1]:
            grid[i][j + 1] = True
            qq.append((i, j + 1))
        if not grid[i][j - 1]:
            grid[i][j - 1] = True
            qq.append((i, j - 1))

    cnt += 1
    q = qq

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

N = int(input())
alist = list(map(int, input().split()))
min_x, max_x = min(alist), max(alist)
max_num = 0
for x in range(min_x, max_x + 1):
    num = len([xx for xx in alist if x -1 <= xx <= x + 1])
    max_num = max(max_num, num)
print(max_num)

### FIXED CODE ###

from collections import defaultdict as dd
N = input()
a_raw = list(map(int, input().split()))
num_count = dd(int)
for item in a_raw:
    num_count[item] += 1
    num_count[item-1] += 1
    num_count[item+1] += 1
print(max(num_count.values()))
### BUGGY CODE ###

N,K = map(int, input().split())
A = list(map(int, input().split()))
dp = [0 for i in range(N)]
dp[0] = 0
if N > K:
    for i in range(1,N):
        if i <= K:
            dp[i] = abs(A[i] - A[0])
        else:
            L = []
            for j in range(1,K+1):
                L.append(abs(A[i]-A[i-j]) + dp[i-j])
            dp[i] = min(L)
    print(dp[N-1])
else:
    print(abs(A[N-1]-A[0]))

### FIXED CODE ###

import numpy as np

N,K = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(A)
dp = np.zeros(N, dtype=int)
dp[0] = 0
if N > K:
    for i in range(1,N):
        if i <= K:
            dp[i] = abs(A[i] - A[0])
        else:
            j = max(i - K, 0)
            dp[i] = np.min(np.abs(A[i] - A[j:i]) + dp[j:i])
    print(dp[N-1])
else:
    print(abs(A[N-1]-A[0]))
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
point = [list(map(int,input().split())) for i in range(Q)]
ac_list = [0]*N
for i in range(N-1):
  if S[i] == 'A' and S[i+1] == 'C':
    ac_list[i] = 'a'
#print(ac_list)
for i in range(Q):
  print(ac_list[point[i][0]-1:point[i][1]-1].count('a'))



### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
point = [list(map(int,input().split())) for i in range(Q)]
ac_list = [0]*(N+1)

for i in range(N):
  if S[i:i+2] == 'AC':
    ac_list[i+1] = ac_list[i] + 1
  else:
    ac_list[i+1] = ac_list[i]


for i in range(Q):
  print(ac_list[point[i][1]-1] - ac_list[point[i][0]-1])
### BUGGY CODE ###

n = int(input())
s = []
sn = []
for i in range(n):
    si = str(input())
    if si in s:
        sn[s.index(si)] += 1
    else:
        s.append(si)
        sn.append(1)

ma = max(sn)
kouho = []
for i in range(len(s)):
    if ma == sn[i]:
        kouho.append(s[i])

kouho.sort()
for i in kouho:
    print(i)


### FIXED CODE ###

n = int(input())
d = dict()

for i in range(n):
    s = str(input())
    if s in d:
        d[s] += 1
    else:
        d[s] = 1

M = max(d.values())
ans = []
for k,v in d.items():
    if v == M:
        ans.append(k)

ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                # if m[x2][y2] == '@':
                #     break
                # if x2 < 0 or x2 >= H:
                #     break
                # if y2 < 0 or y2 >= W:
                #     break
                # if M[x2][y2] < d + 1:
                #     break
                # if M[x2][y2] == d + 1:
                #     continue

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if (m[x2][y2] == '@') or (M[x2][y2] < d + 1):
                        break
                    elif M[x2][y2] == d + 1:
                        continue

                    q.append((d + 1, x2, y2))
    print(-1)


# for i in range(len(M)):
#     print(M[i])


if __name__ == '__main__':
    H, W, K = map(int, sys.stdin.readline().strip().split())
    xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
    xg -= 1
    yg -= 1

    m = []
    for _ in range(H):
        m.append(list(map(str, sys.stdin.readline().strip())))

    M = [[float('inf')] * W for _ in range(H)]

    bfs(xs - 1, ys - 1, 0)


### FIXED CODE ###

from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])
### BUGGY CODE ###

N=int(input())
n_list=input().split()
count=0
for i in range(N) :
  for j in range(i+1,N) :
    if int(n_list[j])+int(n_list[i])==j-i :
      count+=1

print(count)

### FIXED CODE ###

import collections
N=int(input())
n_list=input().split()
count=0
L_list=[]
R_list=[]
for i,item in enumerate(n_list) :
  L_list.append(str(i+int(item)))
  R_list.append(str(i-int(item)))
L_dic=collections.Counter(L_list)
R_dic=collections.Counter(R_list)
count=0
for i in range(N) :
  L_count=L_dic[str(i)]
  R_count=R_dic[str(i)]
  count+=L_count*R_count
print(count)
### BUGGY CODE ###

S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in S[::-1]:
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10
  p[r] += 1

print(sum([i*(i-1)//2 for i in p]))

### FIXED CODE ###

S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

print(sum([i*(i-1)//2 for i in p]))