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

N, K = list(map(int, input().split()))
C = 998244353
S = set()
for _ in range(K):
    l, r = list(map(int, input().split()))
    S |= set(range(l, r+1))
# print(S)

dp = [0]*N
dp[0] = 1
for i in range(N-1):
    if dp[i] == 0:
        continue
    for j in S:
        if i+j < N:
            dp[i+j] = (dp[i+j]+dp[i]) % C
# print(dp)
print(dp[-1] % C)


### FIXED CODE ###

N, K = list(map(int, input().split()))
C = 998244353
L = [None]*K
for j in range(K):
    l, r = list(map(int, input().split()))
    L[j] = [l, r+1]

dp = [0]*N
dp[0] = 1
imos = [0]*(N+1)
imsm = [0]*N

for i in range(N-1):
    if i > 0:
        imsm[i] = imsm[i-1]+imos[i]
        dp[i] = imsm[i] % C
    a = dp[i]
    # print(i,dp)
    for j in range(K):
        l, r = L[j]
        nl = min(i+l, N)
        nr = min(i+r, N)
        imos[nl] += a
        imos[nr] -= a
        # print(i, imos)
dp[N-1] = (imsm[N-2]+imos[N-1]) % C
print(dp[N-1])
### BUGGY CODE ###

n = int(input())
print(sum(range(n)))


### FIXED CODE ###

n = int(input())
print( ((n * (n+1))//2) - n )
### BUGGY CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
import itertools
l=list(itertools.combinations(p,K))
M=999999999999999999
for i in l:
    M=min(M,sum(i))
print(M)
    






        






    
















        


























            
    


    


    
    














    


    














### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
p.sort()
ans=0
for i in range(K):
    ans+=p[i]
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
ab=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    ab[a].append(b)
    ab[b].append(a)
queue=[0]
ans=[-1]*n
ans[0]=0
while queue:
    now_check=queue.pop(0)
    for i in ab[now_check]:
        if ans[i]==-1:
            queue.append(i)
            ans[i]=now_check
print('Yes')
for i in range(1,n):
    print(ans[i]+1)

### FIXED CODE ###

from sys import stdin
from collections import deque

n,m=map(int,input().split())
ab=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,stdin.readline().split())
    a-=1
    b-=1
    ab[a].append(b)
    ab[b].append(a)
queue=[0]
ans=[-1]*n
ans[0]=0
while len(queue)!=0:
    now_check=queue.pop(0)
    for i in ab[now_check]:
        if ans[i]==-1:
            queue.append(i)
            ans[i]=now_check
print('Yes')
for i in range(1,n):
    print(ans[i]+1)
### BUGGY CODE ###

def main():
    import math
    import collections
    N = int(input())
    A = list(map(int, input().split()))
    tt = 0
    #ans = list()
    ann = 0

    def comb(m, n):
        return math.factorial(m) // (math.factorial(n) * math.factorial(m - n))
    '''
    def A_count(n):
        if n in memo:
            return memo[n]
        h = A.count(i)
        memo[n] = A.count(i)
        return h
    '''

    C = collections.Counter(A)
    for i in C.values():
        if i>=2:
            tt = tt + comb(i, 2)

    for i in A:
        f = C[i] #A_count(A[i])
        if f>=3:
            ann = (tt - comb(f, 2) + comb(f-1, 2))
        elif f==2:
            ann = tt - comb(f, 2)
        else:
            ann = tt
        print(ann)

    #for i in ans:
    #    print(i)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import math
    import collections
    N = int(input())
    A = list(map(int, input().split()))
    tt = 0
    #ans = list()
    ann = 0

    def comb(m, n):
        #return math.factorial(m) // (math.factorial(n) * math.factorial(m - n))
        return ((m - 1 + 1) / 1) * (m - 2 + 1) / 2

    '''
    def A_count(n):
        if n in memo:
            return memo[n]
        h = A.count(i)
        memo[n] = A.count(i)
        return h
    '''

    C = collections.Counter(A)
    for i in C.values():
        if i>=2:
            tt = tt + comb(i, 2)

    for i in A:
        f = C[i] #A_count(A[i])
        if f>=3:
            ann = (tt - comb(f, 2) + comb(f-1, 2))
        elif f==2:
            ann = tt - comb(f, 2)
        else:
            ann = tt
        print(int(ann))

    #for i in ans:
    #    print(i)


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

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in a:
    ans^=i
k=~ans
for i in range(n):
    a[i]&=k
rank=0
# 掃き出し法
for i in range(59,-1,-1):
    for j in range(rank,n):
        if a[j]>>i&1:
            break
    if j==n:
        continue
    if j>rank:
        # a[rank]のi番目のbitを1にするswapでもいい
        a[rank]^=a[j]
    for j in range(rank+1,n):
        a[j]=min(a[j],a[j]^a[rank])
    res=0
    rank+=1
for i in a:
    res=max(res,res^i)
print(ans+2*res)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in a:
    ans^=i
k=~ans
for i in range(n):
    a[i]&=k
rank=0
# 掃き出し法
for i in range(59,-1,-1):
    for j in range(rank,n):
        if a[j]>>i&1:
            break
    if j==n:
        continue
    if j>rank:
        # a[rank]のi番目のbitを1にするswapでもいい
        a[rank]^=a[j]
    for j in range(rank+1,n):
        a[j]=min(a[j],a[j]^a[rank])
    res=0
    rank+=1
for i in a:
    res=max(res,res^i)
print(ans+2*res)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    h,w,d = LI()
    a = [LI() for _ in range(h)]
    q = I()
    lr = [LI() for _ in range(q)]
    t = {}
    for i in range(h):
        for j in range(w):
            t[a[i][j]] = (i,j)

    m = {}
    def f(l,r):
        if l == r:
            return 0
        k = (l,r)
        if k in m:
            return m[k]
        res = abs(t[l][0]-t[l+d][0]) + abs(t[l][1]-t[l+d][1])
        res += f(l+d,r)
        m[k] = res
        return res
    rr = []
    for l,r in lr:
        rr.append(f(l,r))

    return '\n'.join(map(str,rr))


print(main())




### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    h,w,d = LI()
    a = [LI() for _ in range(h)]
    q = I()
    lr = [LI() for _ in range(q)]
    t = {}
    for i in range(h):
        for j in range(w):
            t[a[i][j]] = (i,j)


    k = [0] * (h*w+1)
    for i in range(d+1,h*w+1):
        k[i] = k[i-d] + abs(t[i][0] - t[i-d][0]) + abs(t[i][1] - t[i-d][1])
    rr = []
    for l,r in lr:
        rr.append(k[r]-k[l])

    return '\n'.join(map(str,rr))


print(main())
### BUGGY CODE ###

from itertools import permutations
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]

def calc(p):
    ret = 0
    # 各条件を満たしていれば、dを加算していく
    for a, b, c, d in abcd:
        if p[b-1] - p[a-1] == c:
            ret += d
    return ret

ans = [0]
def dfs(s, n):
    if n == N:
        ans[0] = max(ans[0], calc(list(map(int,s))))
        return
    for i in range(int(s[-1]),M+1):
        dfs(s+str(i), n+1)

for i in range(1, M+1):
    dfs(str(i), 1)

print(ans[0])


### FIXED CODE ###

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]

def calc(p):
    ret = 0
    # 各条件を満たしていれば、dを加算していく
    for a, b, c, d in abcd:
        if p[b-1] - p[a-1] == c:
            ret += d
    return ret

ans = [0]
def dfs(s):
    if len(s) == N:
        ans[0] = max(ans[0], calc(s))
        return
    for i in range(s[-1],M+1):
        dfs(s+[i])

for i in range(1, M+1):
    dfs([i])

print(ans[0])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n=int(input())
s=[input() for i in range(n)]
d={}
for i in range(n):
  d[s[i]] = d.get(s[i],0) + 1

max_k_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
max_k_list.sort()
print(*max_k_list)

### FIXED CODE ###

from collections import Counter

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

c = Counter(s)
c2 = c.most_common()
m = c2[0][1]#最大値
ans = [i[0] for i in c2 if i[1] == m]#回数が最大となるもの
ans.sort()
print(*ans)
### BUGGY CODE ###

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

if len(dic) <= K:
  print(0)
else:
  count_list = []
  for i in range(len(dic)):
    count_list.append(A.count(dic[i]))
  
  count_list.sort()
  print(sum(count_list[:len(dic)-K]))

### FIXED CODE ###

from collections import Counter 
n,k = map(int, input().split())
a = list(map(int, input().split()))
ct = sorted(list(Counter(a).values()), reverse=True)
print(sum(ct[k:]))
### BUGGY CODE ###

s=input()
n=len(s)
ans=0
for i in range(n-5+1):
      for j in range(i+4,n):
            a=int(s[i:j+1])
            if a%2019==0:
                  ans+=1
print(ans)


### FIXED CODE ###

s=input()
n=len(s)
mod=2019
sum=0
p=1
d={}
d[0]=1
for i in range(n-1,-1,-1):
    sum=(sum+int(s[i])*p)%mod
    if sum in d:
        d[sum]+=1
    else:
        d[sum]=1
    p=(p*10)%mod
ans=0
for v in d.values():
    ans+=(v*(v-1))//2
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# E
# dp[[i][j]で、(i,j)で可能な偏りをリストとして格納していく

import sys
# 再起回数上限変更
# sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
a = []
x = []

for i in range(H):
    a.append(list(map(int, input().split())))
for i in range(H):
    x.append(list(map(int, input().split())))
    for j in range(W):
        x[i][j] = abs(x[i][j] - a[i][j])


dp = [[[] for _ in range(W)] for _ in range(H)]
dp[0][0].append(x[0][0])
for i in range(H):
    for j in range(W):
        if i > 0:
            for num in dp[i-1][j]:
                dp[i][j].append(num + x[i][j])
                dp[i][j].append(abs(num - x[i][j]))
        if j > 0:
            for num in dp[i][j-1]:
                dp[i][j].append(num + x[i][j])
                dp[i][j].append(abs(num - x[i][j]))
        dp[i][j] = list(set(dp[i][j]))

# print(dp)
print(min(dp[H-1][W-1]))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# E: bit演算を活用して効率的に計算しないとTLEになる

# dp[[i][j]で、(i,j)で可能な偏りを格納していく
# 1, 2, 3が可能な場合は"00000111"と表現する
# n + m を可能にするには、n << mにすれば良い
# (1, 2, 3)に2を足して(3, 4, 5)を可能にするなら、
# "00011100"としたいので、n << mで良い
# (3, 4, 5)に±4する場合；
# 求めたいのは(7, 8, 9) | (-1, 0, 1)
# −１を1としたい

import sys
# 再起回数上限変更
# sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
a = []
x = []

for i in range(H):
    a.append(list(map(int, input().split())))
for i in range(H):
    x.append(list(map(int, input().split())))
    for j in range(W):
        x[i][j] = abs(x[i][j] - a[i][j])


dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1 << x[0][0]
# print(bin(dp[0][0]))


def reverse(d, x):
    res = 0
    for i in range(x+1):
        res <<= 1
        if (1<<i) & d:
            res |= 1
    return res


for i in range(H):
    for j in range(W):
        g = x[i][j]
        if i > 0:
            d1 = dp[i-1][j]
            dp[i][j] |= d1 << g | d1 >> g | reverse(d1, g)
        if j > 0:
            d2 = dp[i][j-1]
            dp[i][j] |= d2 << g | d2 >> g | reverse(d2, g)


a = dp[H-1][W-1]
for i in range(a.bit_length()):
    if a >> i & 1 == 1:
        print(i)
        sys.exit()
### BUGGY CODE ###

A,B,C = map(int, input().split())
n = A
while n < 100000000:
  if n % B == C:
    print("YES")
    break;
  n += A
if n > 100000000:
  print("NO")

### FIXED CODE ###

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

for i in range(0,B):
  if (A*(i+1)) % B == C:
    print("YES")
    exit()

print("NO")
### BUGGY CODE ###

import sys
n, ma, mb = map(int, input().split())
tc = [[] for _ in range(100 * n + 1)]
tn = [[] for _ in range(100 * n + 1)]
for i in range(n):
  a, b, c = map(int, input().split())
  tn[c].append((a, b))
  for j in range(1, 100 * n + 1):
    for aa, bb in tc[j]:
      tn[j].append((aa, bb))
      tn[c + j].append((a + aa, b + bb))
  tc = tn
  tn = [[] for _ in range(100 * n + 1)]
for i in range(1, 100 * n + 1):
  for a, b in tc[i]:
    if a % ma == 0 and b % mb == 0 and a // ma == b // mb:
      print(i)
      sys.exit()
print(-1)


### FIXED CODE ###

import sys
inf = float('inf')
n, ma, mb = map(int, input().split())
t = [[inf] * 401 for _ in range(401)]
for _ in range(n):
  a, b, c = map(int, input().split())
  for aa in range(400, 0, -1):
    for bb in range(400, 0, -1):
      if t[aa][bb] == inf:
        continue
      if t[a + aa][b + bb] > c + t[aa][bb]:
        t[a + aa][b + bb] = c + t[aa][bb]
  if t[a][b] > c:
    t[a][b] = c
result = inf
for a in range(400, 0, -1):
  for b in range(400, 0, -1):
    if a * mb == b * ma and t[a][b] < result:
      result = t[a][b]
if result == inf:
  print(-1)
else:
  print(result)
### BUGGY CODE ###


in_1 = input().split()
n = int(in_1[0])
k = int(in_1[1])

trees_height = []
for i in range(n):
    trees_height.append(int(input()))

trees_height.sort()


def sub_minmax(list):
    return max(list)-min(list)

subs = []

for i in range(n+1-k):
    subs.append(sub_minmax(trees_height[i:i+k]))


print(min(subs))


### FIXED CODE ###

in_1 = input().split()
n = int(in_1[0])
k = int(in_1[1])

trees_height = []
for i in range(n):
    trees_height.append(int(input()))

trees_height.sort()


def sub_minmax(list):
    return max(list)-min(list)

subs = []

for i in range(n+1-k):
    subs.append(trees_height[i+k-1]-trees_height[i])


print(min(subs))
### BUGGY CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip() for _ in range(n)]

s = []
cnt = [0] * n
_max = 0
for tmp in data:
  if tmp not in s:
    s.append(tmp)
  else:
    cnt[s.index(tmp)] += 1
    if _max < cnt[s.index(tmp)]:
      _max = cnt[s.index(tmp)]
    
results = []
for i in range(len(s)):
  if cnt[i] == _max:
    results.append(s[i])

results.sort()
for result in results:
  print(result)

### FIXED CODE ###

n = int(input())

dic = {}
for i in range(n):
  s = input()
  if s in dic:
    dic[s] += 1
  else:
    dic[s] = 1

_max = 0
for v in dic.values():
  if _max < v:
    _max = v
dic2 = sorted(dic.items())

for (k,v) in dic2:
  if v == _max:
    print(k)
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
tmp=[0]*n
for i in range(n):
  if 'AC' == s[i:i+2]:
    tmp[i+1]=1
for i in range(q):
  l,r = map(int,input().split())
  print(sum(tmp[l:r]))

### FIXED CODE ###

n,q = map(int, input().split())
s = input()
tmp=[0]
l,cnt=0,0
r=2
while r<=n:
  if 'AC' == s[l:r]:
    cnt+=1
    l=r
    tmp.append(cnt)
    tmp.append(cnt)
    r+=2
  else:
    tmp.append(cnt)
    l+=1
    r+=1
for i in range(q):
  l,r = map(int,input().split())
  print(tmp[r-1]-tmp[l-1])
### BUGGY CODE ###

import sys

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s - ord('a') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    grid = in_map2(N)

    cnt = 0
    for i in range(N):
        tmp_grid = [[0] * N for _ in range(N)]
        for y in range(N):
            for x in range(N):
                tmp_grid[(y + i) % N][x] = grid[y][x]

        # print(tmp_grid)

        flag = True
        for y in range(N):
            for x in range(N):
                if tmp_grid[y][x] != tmp_grid[x][y]:
                    flag = False

        if flag:
            cnt += N

    print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s - ord('a') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    grid = in_map2(N)

    cnt = 0
    for i in range(N):
        tmp_grid = [[0] * N for _ in range(N)]
        for y in range(N):
            for x in range(N):
                tmp_grid[(y + i) % N][x] = grid[y][x]

        # print(tmp_grid)

        flag = True
        for y in range(N):
            for x in range(N):
                if tmp_grid[y][x] != tmp_grid[x][y]:
                    flag = False

        if flag:
            cnt += N

    print(cnt)


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

import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


def main():
    N, K = map(int, readline().split())
    S = set()
    for k in range(K):
        L, R = map(int, readline().split())
        S |= set(range(L, R + 1))

    dp = [0] * (N + 1)
    dp[1] = 1
    S = list(S)
    S.sort()

    for i in range(1, N + 1):
        for s in S:
            if i - s > 0:
                dp[i] += dp[i - s]
                dp[i] %= M
            else:
                break
    print(dp[N])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


def segfunc(x, y):
    return x + y


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()

    A = [0] * (N + 1)
    A[1] = 1
    seg = SegTree(A, segfunc=segfunc, ide_ele=0)
    for i in range(2, N + 1):
        for l, r in LR:
            if i - l > 0:
                total = (seg.tree[i + seg.num] + seg.query(max(1, i - r), min(N, i - l + 1)) % M)
                seg.update(i, total)
            else:
                break
    print(seg.tree[seg.num + N] % M)


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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6) #for deep recursion

N, Q = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(N-1)]
counts = [0] * N
operations = [list(map(int, input().split())) for _ in range(Q)]

counts = [0] * N
for op in operations:
    p, x = op
    counts[p-1] += x
    
all_connected_vertices = {i: [] for i in range(1, 1+N)}
for a, b in edges:
    all_connected_vertices[a].append(b)
    all_connected_vertices[b].append(a)
    
def get_connected_vertices(v):
    return all_connected_vertices[v]
    
def dfs(point, pre):
    connected_vertices = get_connected_vertices(point)
    children = [v for v in connected_vertices if v != pre]
    for c in children:
        counts[c-1] += counts[point-1]
        dfs(c, point)
    
dfs(1, -1)
    
print(*counts)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6) #for deep recursion

N, Q = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

counts = [0] * N
for op in operations:
    p, x = op
    counts[p-1] += x
    
all_connected_vertices = {i: [] for i in range(1, 1+N)}
for a, b in edges:
    all_connected_vertices[a].append(b)
    all_connected_vertices[b].append(a)
    
def dfs(point, pre):
    connected_vertices = all_connected_vertices[point]
    for c in connected_vertices:
        if c == pre:
            continue
        counts[c-1] += counts[point-1]
        dfs(c, point)
    
dfs(1, -1)
    
print(*counts)
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

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

dist = [[[float('inf')] * 2 for _ in range(W)] for _ in range(H)]
dist[x1 - 1][y1 - 1] = [0, 0]

# (cost, x, y, mode)
q = [(0, x1 - 1, y1 - 1, 0), (0, x1 - 1, y1 - 1, 1)]
while q :
  ccost, cx, cy, cmode = heappop(q)
  if ccost > dist[cx][cy][cmode] :
    continue
  for i, (dx, dy) in enumerate(((-1, 0), (0, -1), (1, 0), (0, 1))) :
    nmode = i % 2
    nx, ny = cx + dx, cy + dy
    if cmode == nmode :
      ncost = ccost + 1
    else :
      ncost = ccost + K - ccost % K
      
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] != '@' and ncost < dist[nx][ny][nmode] :
      heappush(q, (ncost, nx, ny, nmode))
      dist[nx][ny][nmode] = ncost
 
if min(dist[x2 - 1][y2 - 1]) == float('inf') :
  print(-1)
else :
  print((min(dist[x2 - 1][y2 - 1]) + K - 1) // K)

### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i == '.' for i in input()] for _ in range(H)]

x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
INF = 1 << 60
dist = [INF] * (H * W * 2)

def pos(x, y, m) :
  return (x * W + y) * 2 + m
dist[pos(x1, y1, 0)] = dist[pos(x1, y1, 1)] = 0

q = [(0, pos(x1, y1, 0)), (0, pos(x1, y1, 1))]
while q :
  ccost, cpos = heappop(q)
  if ccost > dist[cpos] : continue
  cx = cpos // 2 // W
  cy = cpos // 2 % W
  cmode = cpos % 2
  dir = [
    [(-1, 0), (1, 0)],
    [(0, -1), (0, 1)]
  ]
  for dx, dy in dir[cmode] :
    nx, ny = cx + dx, cy + dy
    ncost = ccost + 1
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] and ncost < dist[pos(nx, ny, cmode)] :
      heappush(q, (ncost, pos(nx, ny, cmode)))
      dist[pos(nx, ny, cmode)] = ncost
      
  ncost = (ccost + K - 1) // K * K
  if ncost < dist[pos(cx, cy, cmode ^ 1)] :
    dist[pos(cx, cy, cmode ^ 1)] = ncost
    heappush(q, (ncost, pos(cx, cy, cmode ^ 1)))

ans = min(dist[pos(x2, y2, 0)], dist[pos(x2, y2, 1)])
if ans == INF :
  print(-1)
else :
  print((ans + K - 1) // K)