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

import sys
from collections import deque

H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())

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

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


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 == xg - 1) and (y1 == yg - 1):
            break

        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 x2 < 0 or x2 >= H:
                    break
                if y2 < 0 or y2 >= W:
                    break
                if m[x2][y2] == '@':
                    break
                if M[x2][y2] < d + 1:
                    break
                if M[x2][y2] == d + 1:
                    continue

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


if m[xs - 1][ys - 1] != '@':
    bfs(xs - 1, ys - 1, 0)

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

ans = M[xg - 1][yg - 1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)


### 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())
c=0
l=[int(i) for i in input().split()]
for i in range(n):
  c1=0
  for j in range(i+1):
    if(l[j]<l[i] and c1!=1):
      c+=1
      c1=1
print(n-c)

### FIXED CODE ###

n=int(input())
l=[int(i) for i in input().split()]
l1=[]
c=0
l1.append(l[0])
for i in range(1,n):
  l1.append(min(l1[i-1],l[i]))
for i in range(n):
  if(l[i]==l1[i]):
    c+=1
print(c)
### BUGGY CODE ###

R,C,K=map(int,input().split())
l=[[0] * C for i in range(R)]
dp=[[[0] * 4 for i in range(C)] for j in range(R)]
for i in range(K):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  l[a][b]=c
dp[0][0][1]=l[0][0]
for x in range(1,R+C-1):
  for y in range(R):
    i=y
    j=x-y
    if j<0 or C<=j:
      continue
    for k in range(4):
      A=0
      if 0<j:
        A=max(A,dp[i][j-1][k])
        if 0<k:
          A=max(A,dp[i][j-1][k-1]+l[i][j])
      if 0<i and k<2:
        for q in range(4):
          A=max(A,dp[i-1][j][q]+k*l[i][j])
      dp[i][j][k]=A
X=dp[R-1][C-1][3]
for k in range(3):
  X=max(X,dp[R-1][C-1][k])
print(X)
    

### FIXED CODE ###

R,C,K=map(int,input().split())
l=[[0] * C for i in range(R)]
for i in range(K):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  l[a][b]=c
dp=[0]*C
for i in range(R):
  ndp=[0]*C
  kdp=[0]*4
  kdp[0]=dp[0]
  kdp[1]=l[i][0]+dp[0]
  ndp[0]=kdp[1]
  for j in range(1,C):
    kdp[0]=max(kdp[0],dp[j])
    for k in range(2,-1,-1):
      kdp[k+1]=max(kdp[k+1],kdp[k]+l[i][j])
    ndp[j]=max(kdp)
  dp=ndp
print(dp[C-1])
### BUGGY CODE ###

def change(A,B,C):
    move=True
    a=A
    b=B
    c=C
    A=b+c
    B=a+c
    C=a+b
    if B-A==b-a:
        move=False
    return A,B,C,move
A,B,C,K=map(int,input().split())
ans=A-B
for i in range(K):
    A,B,C,move=change(A,B,C)
    ans=A-B
    if abs(ans)>1000000000000000000:
        print("Unfair")
        break
    elif not(move):
        print(ans)
        break
else:
    print(ans)

### FIXED CODE ###

A,B,C,K=map(int,input().split())
if K%2==0:
    ans=A-B
else:
    ans=B-A
if ans>1000000000000000000:
    ans="Unfair"
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
num = -2
for i in range(0, N-3):
    for j in range(i, N-1):
        I = S[i]
        J = S[j]
        if I != J:
            color = ['R', 'G', 'B']
            color.remove(I)
            color.remove(J)
            r = color[0]
            if j > num:
                num = S[j+1:].find(r)
                su = S[j+1:].count(r)
                ans += su
            else:
                ans += su
            try:
                if S[j+(j-i)] == r:
                    ans -= 1
            except IndexError:
                pass
            num = S[j+1:].find(r)
print(ans)


### FIXED CODE ###

N = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
ans = r*g*b

for i in range(N-2):
    for j in range(i+1, N):
        k = j+(j-i)
        if k > (N-1):
            break
        if S[i] != S[j] != S[k] != S[i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

s = input().strip()

import functools

@functools.lru_cache(maxsize=None)
def dfs(start, remain):
    if len(remain) == 0:
        return 1
    else:
        ans = 0
        for i in range(1, 3):
            if start == remain[:i]:
                continue
            else:
                ans = max(ans, 1 + dfs(remain[:i], remain[i:]))
        return ans

ans = 0
if len(s) == 1:
    print(ans)
    sys.exit(0)
for i in range(1, 3):
    ans = max(ans, dfs(s[:i], s[i:]))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

s = input().strip()
if len(s) == 1:
    print(0)
    sys.exit(0)
if len(s) == 2 and s[0] == s[1]:
    print(0)
    sys.exit(0)

# [i][0]: index iが1文字分割
# [i][1]: index iが2文字分割
dp = [[0] * 2 for _ in range(len(s))]
# 3文字以上では1文字/2文字の仮想結果が使われる
# 1文字
dp[0][0] = dp[0][1] = 1
# 2文字
if s[0] == s[1]:
    # 実際には常に2文字分割になる
    dp[1][0] = dp[1][1] = 1
else:
    dp[1][0] = 2
    dp[1][1] = 1

# 3文字以上
for i in range(2, len(s)):

    # [i][0]: 末尾の分割を1文字にする場合

    # 末尾2文字が同じ場合
    # - 1つ前を2文字分割にしなくてはならない
    if s[i] == s[i-1]:
        dp[i][0] = dp[i-1][1] + 1
    # 末尾2文字が異なる場合
    # - 1つ前が1文字分割
    # - 1つ前が2文字分割
    else:
        dp[i][0] = max(dp[i-1][0] + 1, dp[i-1][1] + 1)


    # [i][1]: 末尾の分割を2文字にする場合
    # 末尾前の2文字が末尾の2文字と同じ場合
    # 末尾前を1文字分割にしなくてはならない
    if s[i-3:i-1] == s[i-1:i+1]:
        dp[i][1] = dp[i-2][0] + 1
    # 末尾前の2文字が末尾の2文字と異なる場合
    # - 末尾前が1文字分割
    # - 末尾前が2文字分割
    else:
        dp[i][1] = max(dp[i-2][0] + 1, dp[i-2][1] + 1)

print(max(dp[-1][0], dp[-1][1]))
### BUGGY CODE ###

import sys

def main():
    n, w = map(int, input().split())
    a = [list(map(int, x.split())) for x in sys.stdin.readlines()]
    dp = [[0]*(w+1) for _ in range(n+1)]

    for i in range(n):
        for j in range(w+1):
            if j - a[i][0] >= 0:
                dp[i+1][j] = max(dp[i+1][j] , dp[i][j - a[i][0]] + a[i][1])

            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    print(dp[n][w])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def main():
    n, w = map(int, input().split())
    a = [list(map(int, x.split())) for x in sys.stdin.readlines()]
    dp = [[0]*(w+1) for _ in range(n+1)]

    for i in range(n):
        for j in range(w+1):
            if j - a[i][0] >= 0:
                dp[i+1][j] = max(dp[i+1][j] , dp[i][j - a[i][0]] + a[i][1])

            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    print(dp[n][w])

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

N=int(input())
S = [input() for i in range(N)]
P={}
A=[]
for i in range(len(S)):
    P[S[i]] = S.count(S[i])

m=P[S[0]]
for k in range(len(S)):
    if m<P[S[k]]:
        m=P[S[k]]

for k in range(len(S)):
    if P[S[k]]==m:
        A.append(S[k])

A0=set(A)
A1=list(A0)
A1.sort()

for List in A1:
    print(List)

### FIXED CODE ###

import collections
N=int(input())
S = [input() for i in range(N)]
A=[]

P=collections.Counter(S)

y=max(P.values())
A = [k for k, v in P.items() if v == y]

A.sort()

for List in A:
    print(List)
### BUGGY CODE ###


N=int(input())

n=1
while n<=N:
    tmp=n
    count=0
    for x in range(1,N+1):
        # if tmp != n:
        #     n+=1
        #     break
        x2=x**2
        if x2>n:
            break
        for y in range(1,N+1):
            # if tmp != n:
            #     break
            y2=y**2
            xy=x*y
            if y2 > n or xy > n or x2+y2>n or x2+xy > n or xy+y2 > n:
                break
            for z in range(1,N+1):
                z2=z**2
                xz=x*z
                yz=y*z
                if z2 > n or xz > n or yz > n or  x2+y2+z2>n or x2+z2>n or y2+z2>n or xy+yz>n or yz+xz>n or z2+xz>n or z2+xy>n or z2+yz>n:
                    tmp=n+1
                    break
                else:
                    comp=1
                    comp=x2+y2+z2+xy+yz+xz
                    if comp==n:
                        # print(x,y,z,n)

                        count+=1
    n+=1

    print( count)
    # print(n, count)


### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
	for j in range(1,105):
		for k in range(1,105):
			v = i*i+j*j+k*k+i*j+j*k+k*i
			if v<10050:
				ans[v]+=1
for i in range(n):
	print(ans[i+1])
### BUGGY CODE ###

n=int(input())
league=[]
for _ in range(n):
    a=list(map(int,input().split()))
    league.append(a[::-1])

total_match=n*(n-1)//2
match=0
day=0

while match<total_match:
    day+=1
    today_match=[]

    for i in range(n):
        if i in today_match:
            continue
        if league[i]:
            m=league[i][-1]-1
            if m in today_match:
                continue
            if league[m] and league[m][-1]-1==i:
                today_match.extend((league[i].pop()-1, league[m].pop()-1))
    if not today_match:
        day=-1
        break
    #print(today_match)
    match+=len(today_match)//2

print(day)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
pair = N * (N - 1) // 2
ptoi = dict()

i = 0
for x in range(1, N):
    for y in range(x + 1, N + 1):
        ptoi[(x, y)] = i
        ptoi[(y, x)] = i
        i += 1

edge = [[] for _ in range(pair)]
indeg = [0] * pair
for i in range(1, N+1):
    inp = list(map(int, input().split()))
    for s, t in zip(inp[:-1], inp[1:]):
        edge[ptoi[(i, s)]].append(ptoi[(i, t)])
        indeg[ptoi[(i, t)]] += 1


now = [i for i, d in enumerate(indeg) if d == 0]
day = 0
while now:
    nxt = []
    while now:
        s = now.pop()
        for t in edge[s]:
            if indeg[t] <= 0:
                continue
            indeg[t] -= 1
            if indeg[t] == 0:
                nxt.append(t)
    day += 1
    now = nxt

if all(i <= 0 for i in indeg):
    print(day)
else:
    print(-1)
### BUGGY CODE ###

n = int(input())
p = 10**9 + 7

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

def pow(a, n, p):
    bi = str(format(n, 'b'))
    res = 1
    for i in range(len(bi)):
        res = (res * res) % p
        if bi[i] == '1':
            res = (res * a) % p
    return res

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, 10**6 + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

if n == 1:
    print(0)
elif n == 2:
    print(2)
else:
    ans = 0
    for i in range(2, n + 1):
        tryvalue = ((pow(2, i, p) - 2)*cmb(n, i, p)*pow(8, n-i, p))
        ans = (ans + tryvalue) % p
    print(ans)


### FIXED CODE ###

n = int(input())
p = 10**9 + 7

def cmb(n, r, p):
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

def pow(a, n, p):
    bi = str(format(n, 'b'))
    res = 1
    for i in range(len(bi)):
        res = (res * res) % p
        if bi[i] == '1':
            res = (res * a) % p
    return res

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, 10**6 + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

if n == 1:
    print(0)
elif n == 2:
    print(2)
else:
    ans = 0
    powered_2 = pow(2, 1, p)
    for i in range(2, n + 1):
        powered_2 = powered_2 * 2 % p
        tryvalue = ((powered_2 - 2)*cmb(n, i, p)*pow(8, n-i, p))
        ans = (ans + tryvalue) % p
    print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
 
def gcd(a,b):
  if b==0:
    return a
  else:
  	return gcd(b, a%b)

def gcd_list(X):
  dmy=gcd(X[0],X[1])
  dmy=X[0]*X[1]
  for i in range(len(X)):
    dmy=gcd(dmy,X[i])
  return dmy
 
if N==2:
  print(max(A))
else:
  R=[0]*N
  for i in range(N):
    C=A[:i]
    C.extend(A[i+1:])
    #R.append(gcd_list(C))
    R[i]=gcd_list(C)
 
  print(int(max(R)))

### FIXED CODE ###

def gcd(a,b):
    if b == 0:
        return a
    if a % b == 0:
        return b
    else:
        return gcd(b,a%b)

N = int(input())
A = [i for i in map(int,input().split())]
L = [0]
R = [0]
for i in range(N):
    L.append(gcd(L[-1],A[i]))
for i in range(N-1,-1,-1):
    R.append(gcd(R[-1],A[i]))
R.reverse()
g = []
for i in range(N):
    g.append(gcd(L[i],R[i+1]))
print(max(g))
### BUGGY CODE ###

n, q = map(int,input().split())
S = input()
L = []
R = []
for i in range(q):
    l, r = [int(i) for i in input().split()]
    L.append(l)
    R.append(r)
for i in range(q):
    ans = S[L[i]-1:R[i]].count("AC")

    print(ans)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
	t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)

def main():
    N,M = map(int,input().split())
    e = [[] for i in range(N)]
    t = 0
    a = []
    for i in range(M):
        r,l,d = map(int,input().split())
        e[r-1].append([l-1,d])
        e[l-1].append([r-1,-d])
        a.append(r-1)
        a.append(l-1)
        t = r-1

    col = [ float("inf") for i in range(N) ]
    def dfs(i,c):
        for node in e[i]:
            if col[node[0]] == float("inf"):
                col[node[0]] = c + node[1]
                dfs(node[0],c+node[1])
            elif col[node[0]] != c + node[1]:
                print("No")
                exit()


    dfs(t,0)
    a = list(set(a))
    for i in a:
        if col[i] == float("inf"):
            dfs(i,0)


    print("Yes")


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

def main():
    N,M = map(int,input().split())
    e = [[] for i in range(N)]
    t = 0
    a = []
    for i in range(M):
        r,l,d = map(int,input().split())
        e[r-1].append([l-1,d])
        e[l-1].append([r-1,-d])
        a.append(r-1)
        a.append(l-1)
        t = r-1

    col = [ float("inf") for i in range(N) ]
    def dfs(i,c):

        for node in e[i]:
            if col[node[0]] == float("inf"):
                col[node[0]] = c + node[1]
                dfs(node[0],c+node[1])
            elif col[node[0]] != c + node[1]:
                print("No")
                exit()


    dfs(t,0)
    a = list(set(a))
    for i in a:
        if col[i] == float("inf"):
            dfs(i,0)


    print("Yes")


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

n,k,q = map(int, list(input().split()))
point=[k]*n
a=[]
	
for i in range(q):
	point = list(map(lambda x: x-1, point))
	a.append(int(input()))
	point[a[i]-1]+=1
max=max(point)
for i in range(n):
    if point[i]==max or point[i]>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k,q = map(int, list(input().split()))
point=[k]*n
a=[]
	
for i in range(q):
	a.append(int(input()))
	point[a[i]-1]+=1
for i in range(n):
    if point[i]-q>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n,k=map(int,input().split())

import sys
sys.setrecursionlimit(2147483647)

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = 10**9+7 #割る数
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans=1
for i in range(1,k+1):
    ans+=cmb(n, i, p)*cmb(n-1,n-i-1,p)
    
    #print(i,cmb(n, i, p),cmb(n-1,n-i-1,p))

print(ans%p)
    


### FIXED CODE ###

n,k=map(int,input().split())

import sys
sys.setrecursionlimit(2147483647)

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = 10**9+7 #割る数
N = 2*n+1  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans=1

if k>n:
    ans=cmb(n+n-1,n,p)

else:

    for i in range(1,k+1):
        ans+=(cmb(n, i, p)*cmb(n-1,n-i-1,p))%p
        
        #print(i,cmb(n, i, p),cmb(n-1,n-i-1,p))

print(ans%p)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
  a_=int(input())
  a.append(a_)
  
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
  dp[1]=0
else:
  dp[1]=1

for i in range(2,n+1):
  if i in a:
    dp[i]=0
    continue
  dp[i]=dp[i-1]+dp[i-2]
#print(dp)
print(dp[n]%(1000000007))

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
  a_=int(input())
  a.append(a_)
  
dp=[-1]*(n+1)
dp[0]=1
dp[1]=1
for i in a:
  dp[i]=0

for i in range(2,n+1):
  if dp[i]==-1:
    dp[i]=dp[i-1]+dp[i-2]
#print(dp)
print(dp[n]%(1000000007))
### BUGGY CODE ###

import collections

# 入力
N = int(input())
c = collections.Counter(list(map(int, input().split())))

# DPテーブルを初期化
dp = [[[-1 for k in range(310)] for j in range(310)] for i in range(310)]
dp[0][0][0] = 0


for k in range(0, c[3] + 1):
    for j in range(0, c[2]+c[3]-k + 1):
        for i in range(0, c[1]+c[2]+c[3]-j-k + 1):
            if i == j == k == 0:
                continue
            dp[i][j][k] = (N+i*dp[i - 1][j][k]+j *
                           dp[i + 1][j - 1][k]+k*dp[i][j + 1][k - 1])/(i+j+k)


# 答えを得て出力
print(dp[c[1]][c[2]][c[3]])


### FIXED CODE ###

import collections

# 入力
N = int(input())
c = collections.Counter(list(map(int, input().split())))

# DPテーブルを初期化
dp = [[[0.0 for k in range(310)] for j in range(310)] for i in range(310)]


for k in range(0, c[3] + 1):
    for j in range(0, c[2]+c[3]-k + 1):
        for i in range(0, c[1]+c[2]+c[3]-j-k + 1):
            if i == j == k == 0:
                continue
            dp[i][j][k] = (N+i*dp[i - 1][j][k]+j *
                           dp[i + 1][j - 1][k]+k*dp[i][j + 1][k - 1])/(i+j+k)


# 答えを得て出力
print(dp[c[1]][c[2]][c[3]])
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
    l,r=map(int,input().split())
    print(s[l-1:r].count("AC"))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
t=[0]*(n+1)
for i in range(n):
    if s[i:i+2]=="AC":
        t[i+1]=t[i]+1
    else:
        t[i+1]=t[i]

for i in range(q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

inf = 10**18
dp = [[inf for j in range(w)] for k in range(h)]
dp[x1-1][y1-1] = 0
q = deque([(x1-1, y1-1)])

while q:
    x, y = q.popleft()
    for i in range(x+1, x+k+1):
        if 0 <= i <= h-1:
            if g[i][y] == "@":
                break
            if dp[i][y] >= dp[x][y] + 1:
                dp[i][y] = dp[x][y] + 1
                q.append((i, y))
            else:
                break
        else:
            break

    for i in range(x-1, x-k-1, -1):
        if 0 <= i <= h-1:
            if g[i][y] == "@":
                break
            if dp[i][y] >= dp[x][y] + 1:
                dp[i][y] = dp[x][y] + 1
                q.append((i, y))
            else:
                break
        else:
            break

    for j in range(y+1, y+k+1):
        if 0 <= j <= w-1:
            if g[x][j] == "@":
                break
            if dp[x][j] >= dp[x][y] + 1:
                dp[x][j] = dp[x][y] + 1
                q.append((x, j))
            else:
                break
        else:
            break

    for j in range(y-1, y-k-1, -1):
        if 0 <= j <= w-1:
            if g[x][j] == "@":
                break
            if dp[x][j] >= dp[x][y] + 1:
                dp[x][j] = dp[x][y] + 1
                q.append((x, j))
            else:
                break
        else:
            break

if dp[x2-1][y2-1] == inf:
    print(-1)
else:
    print(dp[x2-1][y2-1])


### FIXED CODE ###

from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

inf = 10**9
dp = [[inf for j in range(w)] for k in range(h)]
dp[x1-1][y1-1] = 0
q = deque([(x1-1, y1-1)])

while q:
    x, y = q.popleft()
    if (x, y) == (x2-1, y2-1):
        break
    c = dp[x][y]
    for i in range(x+1, min(x+k+1, h)):
        if g[i][y] == "@":
            break

        if dp[i][y] == inf:
           q.append((i, y))

        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
        else:
            break


    for i in range(x-1, max(x-k-1, -1), -1):
        if g[i][y] == "@":
            break

        if dp[i][y] == inf:
           q.append((i, y))

        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
        else:
            break

    for j in range(y+1, min(y+k+1, w)):
        if g[x][j] == "@":
            break

        if dp[x][j] == inf:
            q.append((x, j))

        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
        else:
            break


    for j in range(y-1, max(y-k-1, -1), -1):
        if g[x][j] == "@":
            break

        if dp[x][j] == inf:
            q.append((x, j))

        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
        else:
            break

if dp[x2-1][y2-1] == inf:
    print(-1)
else:
    print(dp[x2-1][y2-1])
### BUGGY CODE ###

while 1:
    n = input()
    if n == 0: break
    p = sorted([map(int, raw_input().split()) for i in range(n)])
    d = [[p[i][0] - p[0][0], p[i][1] - p[0][1]] for i in range(1,n)]
    m = input()
    q = sorted([map(int, raw_input().split()) for i in xrange(m)])
    for p1 in q:
        for i in range(n-1):
            f = True
            for p2 in q:
                if p1[0] + d[i][0] == p2[0] and p1[1] + d[i][1] == p2[1]:
                    f = False
                    break
            if f: break
        else:
            print p1[0] - p[0][0], p1[1] - p[0][1]

### FIXED CODE ###

while 1:
    n = input()
    if n == 0: break
    p = set([tuple(map(int, raw_input().split())) for i in range(n)])
    m = input()
    q = set([tuple(map(int, raw_input().split())) for i in xrange(m)])
    ret = False
    for px, py in p:
        if ret: break
        for qx, qy in q:
            if ret: break
            dx = qx - px
            dy = qy - py
            for x, y in p:
                mx = x + dx
                my = y + dy
                if (mx, my) not in q:
                    break
            else:
                print dx, dy
                ret = True