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

import sys
import copy

input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(list(input()[:-1]))
    
    L = [[0] * W for _ in range(H)]
    R = copy.deepcopy(L)
    U = copy.deepcopy(L)
    D = copy.deepcopy(L)
    
    for h in range(H):
        cntL, cntR = 0, 0
        for w in range(W):
            wreverse = W - w - 1
            if grid[h][w] == '.':
                cntL += 1
            else:
                cntL = 0
            if grid[h][wreverse] == '.':
                cntR += 1
            else:
                cntR = 0
            L[h][w] = cntL
            R[h][wreverse] = cntR

    for w in range(W):
        cntU, cntD = 0, 0
        for h in range(H):
            hreverse = H - h - 1
            if grid[h][w] == '.':
                cntU += 1
            else:
                cntU = 0
            if grid[hreverse][w] == '.':
                cntD += 1
            else:
                cntD = 0
            U[h][w] = cntU
            D[hreverse][w] = cntD
    
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, L[h][w] + R[h][w] + U[h][w] + D[h][w] - 3)

    print(ans)
        
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import copy

input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(list(input()[:-1]))
    
    L = [[0] * W for _ in range(H)]
    R = copy.deepcopy(L)
    U = copy.deepcopy(L)
    D = copy.deepcopy(L)
    
    for h in range(H):
        cntL, cntR = 0, 0
        for w in range(W):
            wreverse = W - w - 1
            if grid[h][w] == '.':
                cntL += 1
            else:
                cntL = 0
            if grid[h][wreverse] == '.':
                cntR += 1
            else:
                cntR = 0
            L[h][w] = cntL
            R[h][wreverse] = cntR

    for w in range(W):
        cntU, cntD = 0, 0
        for h in range(H):
            hreverse = H - h - 1
            if grid[h][w] == '.':
                cntU += 1
            else:
                cntU = 0
            if grid[hreverse][w] == '.':
                cntD += 1
            else:
                cntD = 0
            U[h][w] = cntU
            D[hreverse][w] = cntD
    
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, L[h][w] + R[h][w] + U[h][w] + D[h][w] - 3)

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

N,Ma,Mb=map(int,raw_input().split())
A=[]
B=[]
C=[]
a_sum=0
b_sum=0
for i in range(N):
	a,b,c=map(int,raw_input().split())
	A.append(a)
	B.append(b)
	C.append(c)
	a_sum+=a
	b_sum+=b

dp=[ [ [ float("inf") for y in range(b_sum+1) ] for x in range(a_sum+1)] for k in range(N+1) ]
dp[0][0][0]=0


for k in range(1,N+1):
	for x in range(a_sum+1):
		for y in range(b_sum+1):
			dp[k][x][y]=min( dp[k][x][y], dp[k-1][x][y] )
			if x-A[k-1]>=0 and y-B[k-1]>=0:
				dp[k][x][y]=min( dp[k-1][x][y], dp[k-1][x-A[k-1]][y-B[k-1]]+C[k-1] )


ans=float("inf")
for x in range(1,a_sum+1):
	for y in range(1,b_sum+1):
		if x*Mb==y*Ma:
			ans=min(ans,dp[N][x][y])

if ans==float("inf"):
	print -1
else:
	print ans
			

### FIXED CODE ###

from collections import defaultdict
N,Ma,Mb=map(int,raw_input().split())

dp=defaultdict(lambda: float("inf"))
dp[(0,0)]=0

for i in range(N):
	a,b,c=map(int,raw_input().split())
	for j in dp.items():
		x=j[0][0]
		y=j[0][1]
		z=j[1]
		na, nb, nc = x+a, y+b, z+c 
		dp[(na, nb)]=min( dp[(na, nb)], nc)


ans=float("inf")
for i in dp.items():
	x=i[0][0]
	y=i[0][1]
	z=i[1]
	if x==0 and y==0:
		continue
	if x*Mb==y*Ma:
		ans=min(ans,z)

else:
	if ans==float("inf"):
		print -1
	else:
		print ans
### BUGGY CODE ###

n = int(input())

arr = list(map(float, input().split()))

dp = [[0] * 3000 for _ in range(3000)]

dp[0][0] = 1.0

for i in range(n):
    for j in range(i + 1):
        dp[i+1][j+1] += dp[i][j] * arr[i]
        dp[i+1][j] += dp[i][j] * (1.0 - arr[i])

print(sum(dp[n][1+n//2:]))


### FIXED CODE ###

import numpy as np

n = int(input())
arr = list(map(float, input().split()))
dp = np.zeros(n + 1, dtype=float)
dp[0] = 1.0

for p in arr:
    tmp = dp * (1 - p)
    tmp[1:] += dp[:-1] * p
    dp = tmp

print(np.sum(dp[n // 2 + 1:]))
### BUGGY CODE ###

import bisect
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
b.sort()
c.sort()
ans = 0
for i in range(n):
    for j in range(bisect.bisect_right(b,a[i]),n):
        ans += n-bisect.bisect_right(c,b[j])
print(ans)

### 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()
c.sort()
ans = 0
for i in range(n):
    ans += bisect.bisect_left(a,b[i])*(n-bisect.bisect_right(c,b[i]))
print(ans)
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().strip().split()))

for i in range(n):
    tmp = x.copy()
    tmp.pop(i)
    tmp.sort()
    print(tmp[n//2-1])

### FIXED CODE ###

n = int(input())
x = list(map(int, input().strip().split()))

sorted_x = sorted(x)
b1,b2 = sorted_x[n//2-1], sorted_x[n//2]
for item in x:
    if item <= b1:
        print(b2)
    else:
        print(b1)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
l = A.pop(0)
r = A.pop(-1)

for i in range(n-2):
  if r<l:
    r+=A.pop(-1)
  else:
    l+=A.pop(0)
  
print(abs(r-l))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
l = A.pop(0)
idxl = 0
r = A.pop(-1)
idxr = -1

for i in range(n-2):
  if r<l:
    r+=A[idxr]
    idxr -= 1
  else:
    l+=A[idxl]
    idxl += 1
  
print(abs(r-l))
### BUGGY CODE ###

#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/input.txt"
exit $?
'''
import sys
import bisect
from operator import itemgetter


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n = _i()
    a = tuple(_ia())
    l = {}
    for i, ai in enumerate(a):
        aip = ai + i + 1
        l[aip] = l.get(aip, 0) + 1
    r = tuple(sorted(i+1-ai for i, ai in enumerate(a)))
    li = 0
    ans = 0
    for k, v in sorted(l.items(), key=itemgetter(0)):
        r = r[li:]
        li = bisect.bisect_right(r, k)
        ans += v * (li - bisect.bisect_left(r[:li], k))
        if li >= n:
            break
    return ans


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import sys
from collections import Counter


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    _ = sys.stdin.readline()
    a = list(_ia())
    l = Counter(ai+i+1 for i, ai in enumerate(a))
    r = Counter(i+1-ai for i, ai in enumerate(a))
    return sum(v*r.get(k, 0) for k, v in l.items())


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

s=input()
n=len(s)
a=0
t=1
d=[1]+[0]*2018
 
for i in range(n):
    a+=int(s[n-1-i])*t
    a%=2019
    t*=10
    #t%=2019
    
    d[a]+=1

ans=0
for i in d:
    ans+=i*(i-1)//2
 
print(ans)

### FIXED CODE ###

s=input()
n=len(s)
a=0
t=1
d=[1]+[0]*2018
 
for i in range(n):
    a+=int(s[n-1-i])*t
    a%=2019
    t*=10
    t%=2019
    
    d[a]+=1

ans=0
for i in d:
    ans+=i*(i-1)//2
 
print(ans)
### BUGGY CODE ###

#coding:utf-8
#1_5_A
def solve(i, m):
    if m == 0:
        return True
    if i >= n:
        return False

    res = solve(i+1, m) or solve(i+1, m-A[i])
    return res

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

for i in range(q):
    if solve(0, m[i]):
        print("yes")
    else:
        print("no")

### FIXED CODE ###

#coding:utf-8
#1_5_A
from itertools import combinations

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

numbers = set()
for i in range(1, n+1):
    for com in combinations(A, i):
        numbers.add(sum(com))

for m in ms:
    if m in numbers:
        print("yes")
    else:
        print("no")
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    H = [int(x) for x in input().split()] + [0] * K

    INF = 10 ** 10
    dp = [INF] * (N + K)
    dp[0] = 0
    for i in range(N):
        target = dp[i]
        for k in range(1, K + 1):
            res = target + abs(H[i] - H[i + k])
            dp[i + k] = res if res < dp[i + k] else dp[i + k]
    print(dp[N - 1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def resolve():
    import sys
    
    readline = sys.stdin.readline

    N, K = map(int, readline().split())
    h = [int(x) for x in readline().split()]

    inf = float('inf')
    dp = [inf] * N
    dp[0] = 0

    for i in range(1, N):
        leng = i + 1 if i < K else K + 1
        for j in range(leng):
            cal = dp[i - j] + abs(h[i] - h[i - j])
            if dp[i] > cal:
                dp[i] = cal

    print(dp[-1])
            

resolve()
### BUGGY CODE ###

def main():
    import sys
    from collections import deque
    from sys import stdin
    readline = stdin.readline

    n,m = map(int, readline().split())
    abl =[[]for i in range(n)]
    for i in range(m):
        a,b = map(int,readline().split())
        abl[a-1].append(b)
        abl[b-1].append(a)
    
    an=[0]*(n-1)
    i=1
    wk=deque([i])
    wwk=deque([])
    il=deque(abl[0])

    while len(wk)>0:
        i=wk.pop()
        il=deque(abl[i-1])
        lil=len(il)

        for k in range(lil):
            iwk=il.pop()
            if an[iwk-2]==0 and iwk>1:
                wwk.append(iwk)
                an[iwk-2]=i
                if all(an):
                    print('Yes')
                    for i in an:
                        print(i)
                    sys.exit()
        if len(wk)==0:
            wk=deque(wwk)
            wwk=deque([])
    print('No')

main()

### FIXED CODE ###

def main():
    from collections import deque
 
    n,m =map(int,input().split())
    abl=[[] for i in range(n+1)]
    for i in range(m):
        a,b = map(int,input().split())
        abl[a].append(b)
        abl[b].append(a)
 
    an=[0]*(n+1)
    an[0]=1
    tg = deque([1])
    while len(tg):
        itg = tg.popleft()
        for j in abl[itg]:
            if an[j]==0:
                an[j]=itg
                tg.append(j)

    if all(an):
        print('Yes')
        for j in an[2:]:
            print(j)
    else:
        print('No')
 
main()
### BUGGY CODE ###

import heapq

N = int(input())
d = [0] * N
INF = float('inf')

class Info:
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost
        
G = [[] for i in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1].append(Info(b - 1, c))
    G[b - 1].append(Info(a - 1, c))
    
def dijkstra(s):
    for i in range(N):
        d[i] = INF
    d[s] = 0
    h = []
    heapq.heappush(h, [0, s])
    
    while h != []:
        p = heapq.heappop(h)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e.to] > d[v] + e.cost:
                d[e.to] = d[v] + e.cost
                heapq.heappush(h, [d[e.to], e.to])

Q, K = map(int, input().split())
for _ in range(Q):
    ans = 0
    x, y = map(int, input().split())
    dijkstra(x - 1)
    ans += d[K - 1]
    #print(d)
    dijkstra(K - 1)
    ans += d[y - 1]
    #print(d)
    print(ans)

### FIXED CODE ###

import heapq

N = int(input())
d = [0] * N
INF = float('inf')

class Info:
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost
        
G = [[] for i in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1].append(Info(b - 1, c))
    G[b - 1].append(Info(a - 1, c))
    
def dijkstra(s):
    for i in range(N):
        d[i] = INF
    d[s] = 0
    h = []
    heapq.heappush(h, [0, s])
    
    while h != []:
        p = heapq.heappop(h)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e.to] > d[v] + e.cost:
                d[e.to] = d[v] + e.cost
                heapq.heappush(h, [d[e.to], e.to])

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

dijkstra(K - 1)

for _ in range(Q):
    ans = 0
    x, y = map(int, input().split())
    ans += d[x - 1]
    ans += d[y - 1]
    print(ans)
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def enum_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)

        return divisors

    import fractions
    from collections import Counter, defaultdict
    n = int(readline())
    a = [readline().rstrip("\n") for _ in range(n)]
    d = dict()
    ans = 0
    for x in a:
        fr = fractions.Fraction(x)
        num, den = fr.numerator, fr.denominator
        num_divs = enum_divisors(num)
        for div in num_divs:
            if d.get(div):
                c = d[div]
                ans += c[den]

        if not d.get(den):
            d[den] = Counter()
        d[den].update(num_divs)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    n = int(readline())
    c = Counter()
    ans = 0

    for _ in range(n):
        x = input()
        if "." in x:
            p, q = x.split(".")
            l = 9 - len(q)
            y = int(p + q + "0" * l)
        else:
            p = x
            y = int(p + "0" * 9)

        i = 0
        while i < 18:
            if y % (2 ** (i + 1)) != 0:
                break
            i += 1

        j = 0
        while j < 18:
            if y % (5 ** (j + 1)) != 0:
                break
            j += 1

        for k in range(18 - i, 19):
            for l in range(18 - j, 19):
                ans += c[(k, l)]

        c[(i, j)] += 1

    print(ans)


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

import sys
import collections
input = sys.stdin.readline


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

N  = int(input())
lst_A = list(map(int, input().split()))
mod = 10**9+7


lcm_lst = {}
lst_c = []
for i in lst_A:
	c = collections.Counter(prime_factorize(i))
	lst_c.append(c)
	for key in c:
		if key in lcm_lst:
			if(lcm_lst[key]<c[key]):
				lcm_lst[key]=c[key]
		else:
			lcm_lst[key]=c[key]

ans = 0
for c in lst_c:
	g = lcm_lst.copy()
	for key in c:
		g[key]=lcm_lst[key] - c[key]
	a = 1
	for key in g:
		a = (a * key**g[key]) % mod
	ans =  (ans + a )% mod
print(ans)

### FIXED CODE ###

import sys,fractions
input = sys.stdin.readline

mod = 10**9+7

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

lcm = 1
for a in lst_a:
    lcm = a*lcm//fractions.gcd(a,lcm)
lcm %= mod
ans = 0
for a in lst_a:
	ans += lcm*pow(a,mod-2,mod)
	ans %= mod

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

from collections import deque

w = deque([0])
e = deque([0])

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

# w = [0]
# e = [0]

tmp_w = 0
tmp_e = 0

for i in range(1, n):

    j = (n - 1) - i

    if (s[i-1] == 'W'):
        tmp_w += 1
        w.append(tmp_w)
    else:
        w.append(tmp_w)

    if (s[j+1] == 'E'):
        tmp_e += 1
        e.appendleft(tmp_e)
    else:
        e.appendleft(tmp_e)

ans = 10 ** 6 
for i in range(n):
    ans = w[i] + e[i] if w[i] + e[i] < ans else ans

print(ans)

### FIXED CODE ###

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

w = [0]
e = [0]

tmp_w = 0
tmp_e = 0

for i in range(1, n):

    j = (n - 1) - i

    if (s[i-1] == 'W'):
        w.append(tmp_w + 1)
        tmp_w += 1
    else:
        w.append(tmp_w)

    if (s[j+1] == 'E'):
        e.append(tmp_e + 1)
        tmp_e += 1
    else:
        e.append(tmp_e)

e.reverse()

ans = 10 ** 6 
for i in range(n):
    ans = w[i] + e[i] if w[i] + e[i] < ans else ans

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

N,Q=map(int, input().split())
node_lst=[list(map(int, input().split())) for i in range(N-1)]
ope_lst=[list(map(int, input().split())) for i in range(Q)]
cnt_lst=[0 for i in range(N)]
node_rel={}
for l in node_lst:
    src, dst = l[0], l[1]
    if src not in node_rel.keys():
        node_rel[src]=[dst]
    else:
        node_rel[src].append(dst)
    for k, v in node_rel.items():
        if src in v:
            node_rel[k].append(dst)
for ope in ope_lst:
    p, x = ope[0], ope[1]
    cnt_lst[p-1]+=x
    if p in node_rel.keys():
        for e in node_rel[p]:
            cnt_lst[e-1]+=x
print(" ".join([str(c) for c in cnt_lst]))

### FIXED CODE ###

N,Q=map(int, input().split())
node_lst=[list(map(int, input().split())) for i in range(N-1)]
ope_lst=[list(map(int, input().split())) for i in range(Q)]
cnt_lst=[0 for i in range(N)]
for ope in ope_lst:
    p, x = ope[0], ope[1]
    cnt_lst[p-1]+=x
node_lst=sorted(node_lst, key=lambda x:x[0])
for l in node_lst:
    src, dst = l[0]-1, l[1]-1
    cnt_lst[dst]+=cnt_lst[src]
print(" ".join([str(c) for c in cnt_lst]))
### BUGGY CODE ###

N = int(input())
s = []
ans = 0
for i in range(N):
    tmp = list(input())
    tmp = sorted(tmp)
    s.append(tmp)
s.sort()
for i in range(N - 1):
    for j in range(N - i - 1):
        if s[i] == s[i + j + 1]:
            ans += 1
        else:
            break
print(ans)

### FIXED CODE ###

N = int(input())
s = {}
ans = 0
for i in range(N):
    tmp = list(input())
    tmp = sorted(tmp)
    tmp = "".join(tmp)
    if tmp not in s:
        s[tmp] = 1
    else:
        ans += s[tmp]
        s[tmp] = s[tmp] + 1
print(ans)
### BUGGY CODE ###

def calc(x):
    return (x+1)/2

n, k = map(int, input().split())
p = list(map(calc,(map(int, input().split()))))

_ans = p[0:k]

ans = sum(_ans)

for x in range(k,n):
    _ans.pop(0)
    _ans.append(p[x])
    # print(_ans)
    ans = max(ans, sum(_ans))

print(ans)


### FIXED CODE ###

def calc(x):
    return (x+1)/2

n, k = map(int, input().split())
p = list(map(calc,(map(int, input().split()))))

_ans = sum(p[0:k])
ans = _ans
for x in range(n-k):
    # print(x, x + k)
    _ans = _ans - p[x] + p[x + k]
    ans = max(ans, _ans)

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

def resolve():
    s = input()
    t = input()

    dp = [[""] * (len(t)+1) for _ in range(len(s)+1)]

    
    def remove_s(in_s, del_s):
        for s in del_s:
            idx = in_s.find(s)
            in_s = in_s[idx+1:]
        return in_s

    for i in range(len(s)):
        for j in range(len(t)):
            #print(i, j)
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + s[i]
            else:
                if len(dp[i][j+1]) >= len(dp[i+1][j]):
                    dp[i+1][j+1] = dp[i][j+1]
                else:
                    dp[i+1][j+1] = dp[i+1][j]

    print(dp[len(s)][len(t)])

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

# dpに文字列を格納 (TLE)
def resolve():
    s = input()
    t = input()

    dp = [[""] * (len(t)+1) for _ in range(len(s)+1)]
    
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + s[i]
            else:
                if len(dp[i][j+1]) >= len(dp[i+1][j]):
                    dp[i+1][j+1] = dp[i][j+1]
                else:
                    dp[i+1][j+1] = dp[i+1][j]

    print(dp[len(s)][len(t)])

def resolve():
    s = input()
    t = input()

    dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]
    
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    # 後ろから探索
    # s[i-1]が、LCSに含まれるかどうか判定
    # dp[i][j]とdp[i-1][j]またはdp[i][j-1]が一致(変化なし)の場合、s[i-1]はLCSに含まれない
    res = ""
    i = len(dp) - 1
    j = len(dp[0]) - 1
    while i != 0 and j != 0:
        if dp[i][j] == dp[i - 1][j]: 
            i -= 1 
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res = s[i-1] + res
            i -= 1
            j -= 1

    print(res)

if __name__ == "__main__":
    resolve()
### 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] == '@':
                        break
                    elif M[x2][y2] == -1:
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] == d + 1:
                        continue
                    else:
                        break

                    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 = [[-1] * 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())
print(sum(range(n)))

### FIXED CODE ###

n=int(input())
print(n*(n-1)//2)