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

import itertools

N,X,Y = map(int,input().split())
n = list(range(1,N+1))
l = []
for v in itertools.combinations(n,2):
  if v[1] - v[0] > abs(Y-v[1]) + abs(X-v[0]) + 1:
    l.append(abs(Y-v[1]) + abs(X-v[0]) + 1)
  else:
    l.append(v[1] - v[0])
    
for k in range(1,N):
  print(l.count(k))

### FIXED CODE ###

import itertools

N,X,Y = map(int,input().split())
n = list(range(1,N+1))
l = [0]*N
for v in itertools.combinations(n,2):
  l[min(abs(Y-v[1]) + abs(X-v[0]) + 1,v[1] - v[0])] += 1
for k in range(1,N):
  print(l[k])
### BUGGY CODE ###

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

a = []
b = []

for i in range(m):
	s, t = map(int, input().split())
	a.append(s-1)
	b.append(t-1)

#各部屋から行ける部屋
c = [[] for i in range(n)]

for i in range(m):
	c[a[i]].append(b[i])
	c[b[i]].append(a[i])

s = [0]
f = []

#部屋1からの距離
d = [10**6]*n
d[0] = 0

while s!=[]:
	x = s[-1]
	s.pop(-1)
	if not(x in f):
		for i in c[x]:
			if not(i in s):
				s.append(i)
			d[i] = min(d[i], d[x]+1)
		f.append(x)

print('Yes')
for i in range(1,n):
	m = 10**6
	ans = 0
	for j in c[i]:
		if d[j]<m:
			m = d[j]
			ans = j+1
	print(ans)

### FIXED CODE ###

import queue

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

a = []
b = []

for i in range(m):
	s, t = map(int, input().split())
	a.append(s-1)
	b.append(t-1)

#各部屋から行ける部屋
c = [[] for i in range(n)]

for i in range(m):
	c[a[i]].append(b[i])
	c[b[i]].append(a[i])

q = queue.Queue()
q.put(0)

#部屋1からの距離
inf = 10**8
d = [inf]*n
d[0] = 0
ans = [0]*n

while not q.empty():
	x = q.get()
	for i in c[x]:
		if d[i]==inf:
			q.put(i)
			d[i] = d[x]+1
			ans[i] = x+1

print('Yes')
for i in range(1,n):
	print(ans[i])
### BUGGY CODE ###

N = int(input())
l = sorted([int(item) for item in input().split(' ')])
count = 0
 
for i in range(N-2):
    for j in range(i+1, N-1):
        low = j + 1
        high = N - 1
        idx = (low + high + 1) // 2 
        for _ in range(10):
            if low == high:
                if not l[i] + l[j] > l[idx]:
                    idx -= 1
                break
            if l[i] + l[j] > l[idx]:
                low = idx
                idx = (low + high + 1) // 2
            else:
                high = idx - 1
                idx = (low + high + 1) // 2
        count += idx - j
print(count)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(map(int, input().split()))

ans = 0
for i in range(n):
    for j in range(i+1, n):
        end = bisect.bisect_left(l, l[i]+l[j])
        ans += end - j - 1
print(ans)
### BUGGY CODE ###

from operator import itemgetter
n,m = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a,reverse = True)
x = []
for _ in range(m):
    b,c = map(int,input().split())
    x.append([c,b])
x.sort(key = itemgetter(0),reverse = True)
y = []
i=0
j=0
#print(a,x)
while len(y)<n:
    if (j == len(x)) or (a[i]>x[j][0]):
        y.append(a[i])
        i+=1
    else:
        y = y + [x[j][0]]*x[j][1]
        #print(y)
        j+=1
y = y[:n]
print(sum(y))

### FIXED CODE ###

from operator import itemgetter
n,m = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a,reverse = True)
x = []
for _ in range(m):
    b,c = map(int,input().split())
    x.append([c,b])
x.sort(key = itemgetter(0),reverse = True)
i=0
j=0
#print(a,x)
s=0
p = 0
x1 = len(x)
while p<n:
    if (j == x1) or (a[i]>x[j][0]):
        s+=a[i]
        p+=1
        i+=1
    else:
        if (p + x[j][1]) > n:
            temp = n - p
            p+=temp
            s = s + x[j][0]*temp
        else:
            p = p + x[j][1]
            s = s + x[j][0]*x[j][1]
        #print(y)
        j+=1
print(s)
### BUGGY CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
 
next_city = 1
visited = []
x = [-1]*n
while x[next_city-1] == -1:
    visited.append(next_city)
    next_city = A[next_city-1]
idx = visited.index(next_city)
visited2 = visited[idx:]
mod = len(visited2)
x = (k%mod-idx)%mod
print(visited2[x])

### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
visited = [0]*n
n_city = 1
while visited[n_city-1] == 0:
    visited[n_city-1] = 1
    n_city = A[n_city-1]
cnt = 1
root = n_city
n_city = A[n_city-1]
while n_city != root:
    n_city = A[n_city-1]
    cnt += 1
to_root = 0
n_city = 1
while n_city != root:
    n_city = A[n_city-1]
    to_root += 1
loop_num = k if k < to_root else (k-to_root)%cnt + to_root
cnt = 0
n_city = 1
while cnt < loop_num:
    n_city = A[n_city-1]
    cnt += 1
print(n_city)
### BUGGY CODE ###

from collections import deque

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

f_lst = [[] for _ in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    f_lst[a].append(b)
    f_lst[b].append(a)

b_lst = [[] for _ in range(n+1)]
for i in range(k):
    c,d = map(int,input().split())
    b_lst[c].append(d)
    b_lst[d].append(c)

res = []
for i in range(1, n+1):
    tmp = []
    visited = [False]*(n+1)
    visited[i] = True
    que = deque(f_lst[i])
    while que:
        v = que.popleft()
        if visited[v]:
            continue
        else:
            visited[v] = True
            tmp.append(v)
            for w in f_lst[v]:
                que.append(w)
    res.append(tmp)

ans = []
for i in range(n):
    x,y,z = set(res[i]), set(f_lst[i+1]), set(b_lst[i+1])
    ans.append(len(x-y-z))
print(*ans)

### FIXED CODE ###

n,m,k = map(int,input().split())
par = [-1]*n
num = [0]*n
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    if x==y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

def same(x,y):
    return find(x) == find(y)

def size(x):
    return -par[find(x)]

for i in range(m):
    a,b = map(int,input().split())
    unite(a-1, b-1)
    num[a-1] += 1
    num[b-1] += 1

edge = [[] for i in range(n)]

for i in range(k):
    c,d = map(int,input().split())
    edge[c-1].append(d-1)
    edge[d-1].append(c-1)

for i in range(n):
    cnt = size(i) - num[i] - 1
    for e in edge[i]:
        if same(e, i):
            cnt -= 1
    print(cnt, end=' ')
### BUGGY CODE ###

s=input()
t=input()

ss=list(s)
tt=list(t)
l=len(ss)    
count=0
y=-1
ind={}
flag1=0
for x in tt:
    ind[x]=[i for i, xx in enumerate(ss) if xx == x]
    if ind[x]==[]:
        flag1=1

if flag1==0:    
    for x in tt:
        for z in ind[x]:
            if z>y:
                y=z
                flag=0
                break
            flag=1
        if flag==1:
            count+=1
            y=ind[x][0]
    #         print(count,z,y)
    ans=count*l+z+1
    print(ans)
else:
    print(-1)



### FIXED CODE ###

s = input()
t = input()
r = 0
p = 0
x = 0
for i in t:
    if s.find(i) == -1:
        print(-1)
        exit()
    if p > s.find(i):
        if s[p:].find(i) == -1:
            x += 1
            p = s.find(i) + 1
        else:
            p = p + s[p:].find(i) + 1
    else:
        p = s.find(i) + 1
print(x * len(s) + p)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    S = input().strip()
    N = len(S)
    mod = 10**9+7
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    for n in range(N):
        c = S[N-n-1]
        if c == "?":
            for i in range(10):
                for j in range(13):
                    dp[n+1][(j + i*10**n)%13] += dp[n][j]
        else:
            for j in range(13):
                dp[n+1][(j + int(c)*10**n)%13] += dp[n][j]
        for i in range(13):
            dp[n+1][i] %= mod
    print(dp[N][5])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    S = input().strip()
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    m = 1
    for n in range(N):
        c = S[N-n-1]
        if c == "?":
            for i in range(10):
                for j in range(13):
                    dp[n+1][(j + i*m)%13] += dp[n][j]
        else:
            k = int(c)
            for j in range(13):
                dp[n+1][(j + k*m)%13] += dp[n][j]
        for i in range(13):
            dp[n+1][i] %= 10**9+7
        m = m * 10 % 13
    print(dp[N][5])


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

# coding: utf-8
#import math
#import numpy
#N = int(input())
def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    #K =int(input())
    ANS = []
    a_ = 1
    for i in range(K):
        a_ *= A[K-i-1]
    #ANS.append(a)
    for i in range(K,N):
        if A[i-K] < A[i]:
            print("Yes")
        else:
            print("No")
        
        
        #ANS.append(a)
    #print(ANS)
    

if __name__ == '__main__':
    main()

### FIXED CODE ###

# coding: utf-8
#import math
#import numpy
#N = int(input())
def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    #K =int(input())
    ANS = []
    
    #ANS.append(a)
    for i in range(K,N):
        if A[i-K] < A[i]:
            print("Yes")
        else:
            print("No")
        
        
        #ANS.append(a)
    #print(ANS)
    

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

import math
N = int(input())
d = math.factorial(N)

k, ans = 1, 1
for i in range(1, N + 1):
    while d % i == 0:
        d //= i
        k += 1
    ans *= k
    k = 1
print(ans % (10**9 + 7))


### FIXED CODE ###

import math
N = int(input())
d = math.factorial(N)

k, ans = 1, 1
for i in range(2, N + 1):
    while d % i == 0:
        d //= i
        k += 1
    ans *= k
    k = 1
print(ans % (10**9 + 7))
### BUGGY CODE ###

from collections import deque

h, w = list(map(int, input().split()))
f = []
q = deque()
for i in range(h):
    l = input()
    for j, c in enumerate(l):
        if c == '#':
            q.append((0, i, j))
    f.append(l)
visited = [[False] * w for _ in [0] * h]
ans = 0
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while q:
    d, i, j = q.popleft()
    if visited[i][j]:
        continue
    ans = d
    visited[i][j] = True
    for di, dj in move:
        ni, nj = i + di, j + dj
        if ni < 0 or h <= ni or nj < 0 or w <= nj:
            continue
        if visited[ni][nj]:
            continue
        q.append((d + 1, ni, nj))

print(ans)


### FIXED CODE ###

from collections import deque

h, w = list(map(int, input().split()))
f = []
q = deque()
for i in range(h):
    l = input()
    for j, c in enumerate(l):
        if c == '#':
            q.append((0, i, j))
    f.append(l)

visited = [[False] * w for _ in [0] * h]
for d, i, j in q:
    visited[i][j] = True

ans = 0
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while q:
    d, i, j = q.popleft()
    ans = d
    for di, dj in move:
        ni, nj = i + di, j + dj
        if ni < 0 or h <= ni or nj < 0 or w <= nj:
            continue
        if visited[ni][nj]:
            continue
        visited[ni][nj] = True
        q.append((d + 1, ni, nj))

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

import sys
from itertools import combinations


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n = inint()
A = inintl()

MOD = 1000000007

ans = 0

for c in combinations(A,2):
    ans += c[0]*c[1] % MOD

print(ans % MOD)

### FIXED CODE ###

import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n = inint()
A = inintl()

S = [0]*(n+1)
ans = 0

for i in range(n):
    S[i+1] = S[i] + A[i]

for i in range(1,n):
    ans += A[i-1]*(S[-1] - S[i])
    ans %= (10**9 + 7)

print(ans % (10**9 + 7))
### BUGGY CODE ###

s= input()[::-1]
 
sum_of_digits = 0
 
cnts = [0] * 2019
 
cnts[0] = 1
 
d = 1
 
for c in s:
    sum_of_digits += int(c) * d
    num = sum_of_digits % 2019
    d *= 10
    cnts[num] += 1
 
ans = 0
    
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2
 
print(ans)

### FIXED CODE ###

s= input()[::-1]
 
sum_of_digits = 0
 
cnts = [0] * 2019
 
cnts[0] = 1
 
d = 1
 
for c in s:
    sum_of_digits += int(c) * d
    num = sum_of_digits % 2019
    d *= 10
    d %=2019
    cnts[num] += 1
 
ans = 0
    
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2
 
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = list(input())
lr = []
for i in range(Q):
    l, r = map(int, input().split())
    lr.append([l, r])

for i in range(Q):
    count = 0
    l = lr[i][0]-1
    r = lr[i][1]-1
    for j in range(l,r):
        if S[j] is 'A':
            if S[j+1] is 'C':
                count += 1
    print(count)

### FIXED CODE ###

N, Q = map(int, input().split())
S = list(input())
lr = []
for i in range(Q):
    l, r = map(int, input().split())
    lr.append([l, r])

pair = [0] * len(S)
for i in range(len(S)-1):
    if S[i] is 'A' and S[i+1] is 'C':
        pair[i+1] = pair[i] + 1
    else:
        pair[i+1] = pair[i]

for i in range(Q):
    ans = 0
    l = lr[i][0]-1
    r = lr[i][1]-1
    print(pair[r]-pair[l])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

class HashTable(list):
    def __init__(self, length):
        list.__init__(self)
        self.length = length
        self[:] = [None] * length

    def h1(self, key):
        return key % self.length

    def h2(self, key):
        return 1 + (key % (self.length - 1))

    def h(self, key, i):
        return (self.h1(key) + i*self.h2(key)) % self.length

    def insert(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self[j] is None:
                self[j] = key
                return j
            else:
                i += 1
    
    def search(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self[j] == key:
                return j
            elif self[j] is None or i >= self.length:
                return None
            else:
                i += 1

def getNum(char):
    char2num = str.maketrans("ACGT", "1234")
    return int(char.translate(char2num))

if __name__ == '__main__':

    n = int(input())
    T = HashTable(n*10)
    C = [input().split(" ") for i in range(n)]
    C = map(lambda x:(x[0], getNum(x[1])), C)
    
    for command, num in C:
        if command == "insert":
            T.insert(num)
        else:
            if T.search(num) is None:
                print("no")
            else:
                print("yes")



### FIXED CODE ###

# -*- coding: utf-8 -*-

class HashTable(list):
    def __init__(self, length):
        list.__init__(self)
        self.length = length
        self[:] = [None] * length

    def h(self, key, i):
        h1 = key % self.length
        h2 = 1 + (key % (self.length - 1))
        return (h1 + i*h2) % self.length

    def insert(self, key):
        i = 0
        while True:
            h1 = key % self.length
            h2 = 1 + (key % (self.length - 1))
            j = (h1 + i*h2) % self.length
            #j = self.h(key, i)
            if self[j] is None:
                self[j] = key
                return j
            else:
                i += 1
    
    def search(self, key):
        i = 0
        while True:
            h1 = key % self.length
            h2 = 1 + (key % (self.length - 1))
            j = (h1 + i*h2) % self.length
            #j = self.h(key, i)
            if self[j] == key:
                return j
            elif self[j] is None or i >= self.length:
                return None
            else:
                i += 1

def getNum(char):
    char2num = str.maketrans("ACGT", "1234")
    return int(char.translate(char2num), 5)

if __name__ == '__main__':

    n = int(input())
    T = HashTable(1046527)
    C = [input().split(" ") for i in range(n)]
    
    for command, char in C:
        num = getNum(char)
        if command[0] == "i":
            T.insert(num)
        else:
            if T.search(num) is None:
                print("no")
            else:
                print("yes")
### BUGGY CODE ###

def main():
    n, x, y = map(int,input().split())
    ans = [0] * n
    dp = [[0] * (n - 1) for i in range(n)]
    for i in range(1,n+1):
        for j in range(1,n+1):
            dirct = abs(i-j)
            mid_x = abs(x-i) + 1 + abs(y - j)
            mid_y = abs(y-i) + 1 + abs(x - j)
            ans[min(dirct, mid_x, mid_y)] += 1
    for i in range(1, n ):
        print(ans[i] // 2)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, x, y = map(int,input().split())
    ans = [0] * n
    dp = [[0] * (n - 1) for i in range(n)]
    for i in range(1,n+1):
        for j in range(i,n+1):
            dirct = abs(i-j)
            mid_x = abs(x-i) + 1 + abs(y - j)
            mid_y = abs(y-i) + 1 + abs(x - j)
            ans[min(dirct, mid_x, mid_y)] += 1
    for i in range(1, n ):
        print(ans[i])


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

a, b = input().split()
ab = int(a)*10**(len(b)) + int(b)

judge = 0
i = int(a) * int(b)

while judge == 0:
    if i**2 == ab:
        judge = 1
        break
    i += 1

if judge == 1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a, b = input().split()
ab = int(a)*10**(len(b)) + int(b)

judge = 0
i = min(int(a), int(b))

while judge == 0:
    if i**2 == ab:
        judge = 1
        break
    i += 1
    if i**2 > ab:
        break

if judge == 1:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

from collections import Counter
import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n = int(input())
al = list(map(int, input().split()))
c = Counter(al)

k = 0
for v in c.values():
    if v == 1:
        continue
    else:
        k += combinations_count(v, 2)

for a in al:
    if c[a] == 1:
        print(k)
    elif c[a] == 2:
        print(k-combinations_count(c[a], 2))
    else:
        print(k-combinations_count(c[a], 2)+combinations_count(c[a]-1,2))


### FIXED CODE ###

from collections import Counter
from operator import mul
from functools import reduce


def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


n = int(input())
al = list(map(int, input().split()))
c = Counter(al)

k = 0
for v in c.values():
    if v == 1:
        continue
    else:
        k += cmb(v, 2)

for a in al:
    if c[a] == 1:
        print(k)
    elif c[a] == 2:
        print(k-cmb(c[a], 2))
    else:
        print(k-cmb(c[a], 2)+cmb(c[a]-1,2))
### BUGGY CODE ###

s = input()
q = int(input())

for i in range(q):
    tmp=input()
    if len(tmp)==1:
        s=s[::-1]
    else:
        if tmp[2]=="1":
            s=tmp[4]+s
        else:
            s=s+tmp[4]

print(s)

### FIXED CODE ###

s = input()
q = int(input())
hanten=False
mae=""
usiro=""
for i in range(q):
    tmp=input()
    if len(tmp)==1:
        hanten=not(hanten)
    else:
        if hanten==False:
            if tmp[2]=="1":
                mae=tmp[4]+mae
            else:
                usiro=usiro+tmp[4]
        else:
            if tmp[2]=="1":
                usiro=usiro+tmp[4]
            else:
                mae=tmp[4]+mae
                
ans=mae+s+usiro
if hanten==False:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

k = int(input())
import itertools
def GCD(a,b):
    if(a%b == 0):
        return b
    else:
        return GCD(b,a%b)
total = 0
for i in list(itertools.product(list(range(1,k+1)), repeat = 3)):
    a = int(i[0])
    b = int(i[1])
    c = int(i[2])
    total += GCD(GCD(a,b),c)
print(total)

### FIXED CODE ###

k = int(input())
import itertools
def GCD(a,b):
    if(a%b == 0):
        return b
    else:
        return GCD(b,a%b)
total = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            total += GCD(GCD(a,b),c)
print(total)
### BUGGY CODE ###

# 解説を参考に作成
def solve():
    S = input()
    lenS = len(S)
    modS = []
    mod_list = [0] * 2019
    for i in range(lenS):
        x = int(S[lenS - 1 - i:]) % 2019
        modS.append(int(S[lenS - 1 - i:]) % 2019)
        mod_list[x] += 1
    result = 0
    for i, ml in enumerate(mod_list):
        if i == 0:
            result += ml
        result += int(ml * (ml - 1) / 2)
    print(result)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# 解説を参考に作成
# さらに 提出 #12403542 を参考


def solve():
    S = input()
    lenS = len(S)
    mod_list = [0] * 2019
    x = 0
    for i in range(lenS):
        x = (int(S[lenS - 1 - i]) * pow(10, i, 2019) + x) % 2019
        mod_list[x] += 1

    result = 0
    for i, ml in enumerate(mod_list):
        if i == 0:
            result += ml
        result += int(ml * (ml - 1) / 2)
    print(result)


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

#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w,d=MI()
mp=[LI() for i in range(h)]
lis=[[0,0] for i in range(w*h)]
for i in range(h):
    for j in range(w):
        lis[mp[i][j]-1]=[i,j]
cost=[0 for i in range(w*h)]
for i in range(h*w):
    if i+d<h*w:
        cost[i]=abs(lis[i+d][0]-lis[i][0])+abs(lis[i+d][1]-lis[i][1])
#print(cost)
q=I()
for i in range(q):
    ans=0
    l,r=MI()
    for i in range(l,r,d):
        #print(i)
        ans+=cost[i-1]
    print(ans)
        


    
    


    

    
            
        
        
    
    
    
    

    
    


    
    

        
        
    


    

### FIXED CODE ###

#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w,d=MI()
mp=[LI() for i in range(h)]
lis=[[0,0] for i in range(w*h)]
for i in range(h):
    for j in range(w):
        lis[mp[i][j]-1]=[i,j]
#print(lis)

costs=[0 for i in range(h*w+1)]
for i in range(1,d+1):
    for j in range(0,h*w):
        if i+d*(j+1)<h*w+1:
            costs[i+d*(j+1)]=costs[i+d*j]+abs(lis[i+d*(j+1)-1][1]-lis[i+d*j-1][1])+abs(lis[i+d*(j+1)-1][0]-lis[i+d*j-1][0])
        else:
            break
q=I()
for i in range(q):
    l,r=MI()
    u=l%d
    print(costs[r]-costs[l])
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
CA = collections.Counter(A)
V,C = zip(*CA.most_common())
S = 0
for i in range(len(C)):
    L = C[i]
    S += int(L*(L-1)/2)
for k in range(N):
    print(S - A.count(A[k]) + 1)

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
CA = collections.Counter(A)
S = 0
for i in CA.values():
    S += i*(i-1)//2
for x in A:
    print(S - CA[x] + 1)