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

n = int(input())
A = list(map(int, input().split()))
A = sorted(A)
ans = 0


def q(k):
    if A[k] < A[i] + A[j]:
        return True
    else:
        return False


for i in range(n):
    for j in range(i + 1, n):
        l = j
        r = n
        while r - l > 1:
            mid = (l + r) // 2
            if q(mid):
                l = mid
            else:
                r = mid
        ans += (l - j)


print(ans)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
A = sorted(A)
ans = 0


def q(k):
    if A[k] < A[i] + A[j]:
        return True
    else:
        return False


for i in range(n):
    for j in range(i + 1, n):
        l = j
        r = n
        while r - l > 1:
            mid = (l + r) // 2
            if q(mid):
                l = mid
            else:
                r = mid
        ans += (l - j)


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

from itertools import combinations as c
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
W,V = [],[]
for i in range(N):
    w,v = map(int,input().split())
    W.append(w),V.append(v)

ans = 0
for i in range(1,N+1):
    for a,b in zip(c(V,i),c(W,i)):
        if sum(b) > M:
            continue
        ans = max(ans,sum(a))
print(ans)

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline
N,W = map(int,input().split())
dp = np.zeros(W+1,dtype=int)
for i in range(N):
    w,v = map(int,input().split())
    dp[w:] = np.maximum(dp[w:],dp[:-w]+v)
print(dp[-1])
### BUGGY CODE ###

[R, C, K] = list(map(int, input().split()))
G = [[None]*C for i in range(R)]
for i in range(K):
    [r, c, v] = list(map(int, input().split()))
    G[r-1][c-1] = v

dp = [[[-1]*4 for i in range(C)] for j in range(R)]
dp[0][0][0] = 0
if G[0][0] != None: dp[0][0][1] = G[0][0]

for r in range(R):
    for c in range(C):
        for k in range(4):
            if dp[r][c][k] == -1: continue

            if c+1<C and G[r][c+1] != None and k < 3: # can go right and pick up
                if dp[r][c+1][k+1] < dp[r][c][k] + G[r][c+1]:
                    dp[r][c+1][k+1] = dp[r][c][k] + G[r][c+1]
            if c+1<C: # moving right without picking up
                if dp[r][c+1][k] < dp[r][c][k]:
                    dp[r][c+1][k] = dp[r][c][k]
            if r+1<R: # moving downward without picking up
                if dp[r+1][c][0] < dp[r][c][k]:
                    dp[r+1][c][0] = dp[r][c][k]
            if r+1<R and G[r+1][c] != None: # can go down and pick up
                if dp[r+1][c][1] < dp[r][c][k] + G[r+1][c]:
                    dp[r+1][c][1] = dp[r][c][k] + G[r+1][c]

print(max(dp[r][c]))


### FIXED CODE ###

import numpy as np
from numba import jit

R, C, K = map(int, input().split())
G = np.zeros((R+1, C+1), np.int64)
for i in range(K):
    [r, c, v] = list(map(int, input().split()))
    G[r-1][c-1] = v

@jit
def main(G, R, C):
    dp = np.full((R+1, C+1, 4), -1)
    dp[0][0][0] = 0
    if G[0][0] != None: dp[0][0][1] = G[0][0]
    for r in range(R):
        for c in range(C):
            for k in range(4):
                if dp[r][c][k] == -1: continue
                if k < 3: # can go right and pick up
                    if dp[r][c+1][k+1] < dp[r][c][k] + G[r][c+1]:
                        dp[r][c+1][k+1] = dp[r][c][k] + G[r][c+1]
                if dp[r][c+1][k] < dp[r][c][k]:
                    dp[r][c+1][k] = dp[r][c][k]
                if dp[r+1][c][0] < dp[r][c][k]:
                    dp[r+1][c][0] = dp[r][c][k]
                if dp[r+1][c][1] < dp[r][c][k] + G[r+1][c]:
                    dp[r+1][c][1] = dp[r][c][k] + G[r+1][c]
    return(max(dp[r][c]))

ret = main(G, R, C)
print(ret)
### BUGGY CODE ###

import math

N = int(input())

for i in range(1,N+1):
  ans = 0
  for x in range(1,math.ceil(math.sqrt(i/3))):
    # if x**2 + x**2 + x**2 + x*x + x*x + x*x > i:
    #   break
    for y in range(x,math.ceil(math.sqrt(i/2))):
      # if x**2 + y**2 + y**2 + x*y + y*y + y*x > i:
      #   break
      for z in range(y,math.ceil(math.sqrt(i))):
        # print(x,y,z)
        if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
          if x == y == z:
            ans += 1
          elif x == y | x == z | y == z:
            ans += 2
          else:
            ans += 3
          break
        # elif x**2 + y**2 + z**2 + x*y + y*z + z*x > i:
        #   break
      
  print(ans)


### FIXED CODE ###

import math

N = int(input())
ans = [0 for _ in range(10050)]

# for i in range(1,N+1):
for x in range(1,math.ceil(math.sqrt(N))):
  for y in range(1,math.ceil(math.sqrt(N))):
    for z in range(1,math.ceil(math.sqrt(N))):
      v = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if v < 10050:
        ans[v] += 1

for i in range(N):
  print(ans[i+1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
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:
    continue
  else:
    dp[i] = dp[i-1]+dp[i-2]
print(dp[-1] % (10**9+7))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
a = set(a)
dp = [0]*(n+1)
dp[0] = 1
mod = 10**9 + 7
if 1 in a:
  dp[1] = 0
else:
  dp[1] = 1
for i in range(2,n+1):
  if i in a:
    continue
  else:
    dp[i] = (dp[i-1]+dp[i-2]) % mod
print(dp[-1] % mod)
### BUGGY CODE ###

N=int(input())
cnt=0
for i in range(1,10):
    for k in range(1,10):
        a=0
        b=0
        for n in range(1,N+1):
            r=n%10
            l=n//(10**(len(str(n))-1))
            if k==r and i==l:
                a+=1
            if i==r and k==l:
                b+=1
        cnt+=a*b
print(cnt)

### FIXED CODE ###

N=int(input())
cnt=0
for i in range(1,10):
    for k in range(1,10):
        a=0
        b=0
        for n in range(1,N+1):
            r=n%10
            l=n//(10**(len(str(n))-1))
            if k==r and i==l:
                a+=1
            if i==r and k==l:
                b+=1
        cnt+=a*b
print(cnt)
### BUGGY CODE ###

from functools import reduce
n = int(input())
a = list(map(int, input().split()))

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

def gcd_list(ns):
    return reduce(gcd, ns)

ans = 0
l=len(a)
for i in range(l):
    b = a[0:i] + a[i+1:l]
    ans = max(ans, gcd_list(b))

print(ans)

### FIXED CODE ###

from functools import reduce

# 2数の最大公約数
def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

# リストの最大公約数
def gcd_list(nums):
    return reduce(gcd, nums)

# 入力
n = int(input())
a = list(map(int, input().split()))

#a[i]より前方要素の最大公約数を保持
l = [0 for _ in range(n)]
l[0] = 0
for i in range(1, n):
    l[i] = gcd(l[i-1], a[i-1])
# print(l)

#a[i]より後方要素の最大公約数を保持
r = [0 for _ in range(n)]
r[n-1] = 0
for i in reversed(range(n-1)):
    r[i] = gcd(r[i+1], a[i+1])
# print(r)

# a[i]を除いた最大公約数を計算
ans = 0
for i in range(n):
    ans = max(ans, gcd(l[i],r[i]))

# 出力
print(ans)
### BUGGY CODE ###

N, K = input().split()
P = input().split()
max_sum = 0
for i in range(int(N)-int(K) + 1):
  sum = 0
  for k in range(i, i + int(K)):
    p = int(P[k])
    sum += (p / 2) + 0.5
    if max_sum < sum:
      max_sum = sum
print(float(max_sum))


### FIXED CODE ###

N, K = input().split()
P = input().split()
K = int(K)

S = []
count = 0
max_sum = 0
for p in P:
    e = (int(p) + 1) / 2
    if count == 0:
        S.append(e)
    else:
        S.append(S[count-1] + e)
    if count == (K - 1):
        max_sum = S[count]
    elif count > (K - 1):
        sum = S[count] - S[count - K]
        if max_sum < sum:
            max_sum = sum
    count += 1
print(max_sum)
### BUGGY CODE ###

import math
N = int(input())
A = int(math.sqrt(N))
for i in range(A, N + 1):
    if N % i == 0 or len(str(i)) == len(str(N)):
        print(len(str(i)))
        break


### FIXED CODE ###

import math
N = int(input())
for i in range(int(math.sqrt(N)) + 1, 0, -1):
    q, m = divmod(N, i)
    if m == 0:
        print(len(str(q)))
        break
### BUGGY CODE ###

N=[int(e) for e in input().split()]
p=[int(e) for e in input().split()]
p2=[0]*(N[0]-N[1]+1)
for i in range(N[0]-N[1]+1):
    a=0
    for j in range(N[1]):
        a=a+(p[i+j]+1)
    p2[i]=a

print(max(p2)/2.)

### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
for i in range(N-1):
    p[i+1]=p[i+1]+p[i]
max=p[K-1]
if N>K:
    for i in range(1,N-K+1):
        tmp=p[i+K-1]-p[i-1]
        if max < tmp:
            max=tmp
print((max+K)/2.)
### BUGGY CODE ###

n=int(input())
s=list(input())
ans=3000000

for i in range(n):
    counts=0
    counts=s[:i].count("W")
    counts=counts+s[i+1:].count("E")
    ans=min(ans,counts)
print(ans)

### FIXED CODE ###

n=int(input())
s=list(input())
count_east=[0]*n
count_west=[0]*n
counts=[0]*n

for i in range(n-2,-1,-1):
    if s[i+1]=='E':
        count_east[i]=count_east[i+1]+1
    else:
        count_east[i]=count_east[i+1]
for i in range(1,n):
    if s[i-1]=='W':
        count_west[i]=count_west[i-1]+1
    else:
        count_west[i]=count_west[i-1]
for i in range(n):
    counts[i]=count_east[i]+count_west[i]

print(min(counts))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
for ai,a in enumerate(A):
    if a >= 2*10**5:
        continue
    for aj in range(ai+a,N):
        if A[aj] + A[ai] == aj - ai:
            ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
x2l = {} # i+A_i
ans = 0
for i,a in enumerate(A,1):
    if i - a in x2l:
        ans += x2l[i-a]
    if i + a in x2l:
        x2l[i+a] += 1
    else:
        x2l[i+a] = 1
print(ans)
### BUGGY CODE ###

X = int(input())
result = []
for i in range(X,X*2):
    for j in range (2, i):
        if (i % j) == 0:
            break
    else:
            result.append(i)
print (min(result))

### FIXED CODE ###

X = int(input())
result = []
for i in range(X,X*2):
    for j in range (2,i):
        if (i % j) == 0:
            break
    else:
            result.append(i)
            a = i
            break
print (a)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

S = input()
n = len(S)

dp = [0] * 2019
dp[0] = 1
for i in range(n):
    dp[(int(S[i:])%2019)] += 1
# print(dp)

ans = 0
for i in dp:
    if i >= 2:
        ans += i*(i-1)//2
        # print(i, dp[i])
print(ans)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

S = list(input())
n = len(S)

dp = [0] * 2019
dp[0] = 1
tmp = 0
ten = 1
for i in range(n):
    tmp += int(S[n-1-i]) * ten
    tmp %= 2019
    ten *= 10
    ten %= 2019
    dp[tmp%2019] += 1
# print(dp)

ans = 0
for i in dp:
    if i >= 2:
        ans += i*(i-1)//2
        # print(i, dp[i])
print(ans)
### BUGGY CODE ###

import itertools

n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]

com = list(itertools.combinations(h, k))

ans = max(com[0]) - min(com[0])
for c in com[1:]:
    ans = min(ans, max(c) - min(c))
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]
 
h = sorted(h)
 
ans = h[k-1] - h[0]
for i in range(1, n-k+1):
    ans = min(ans, h[i+k-1] - h[i])

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

N,ave = map(int,input().split())
card_ls = list(map(int, input().split()))
#dp[i+1][n][s] := i番目までのカード(0idx)からn枚使って合計がsとなるパターンの数
dp = [[[0]*(ave*N+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for n in range(N):
        for s in range(ave*N+1):
            # i番目を新しく使う
            if s+card_ls[i] < ave*N+1:
                dp[i+1][n+1][s+card_ls[i]] += dp[i][n][s]
            # i番目を使わない
            dp[i+1][n][s] += dp[i][n][s]

#print(dp)
ans = 0
for n in range(1,N+1):
    ans += dp[N][n][n*ave]
print(ans)

### FIXED CODE ###

N,ave = map(int,input().split())
card_ls = list(map(int, input().split()))
#dp[i+1][n][s] := i番目までのカード(0idx)からn枚使って合計がsとなるパターンの数
dp = [[[0]*(ave*N+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for n in range(N):
        for s in range(ave*N+1):
            # i番目を新しく使う
            if s+card_ls[i] < ave*N+1:
                dp[i+1][n+1][s+card_ls[i]] += dp[i][n][s]
            # i番目を使わない
            dp[i+1][n][s] += dp[i][n][s]

#print(dp)
ans = 0
for n in range(1,N+1):
    ans += dp[N][n][n*ave]
print(ans)
### BUGGY CODE ###

from sys import stdin
a,b,k=[int(x) for x in stdin.readline().rstrip().split()]
while k>0:
    if a>=1:
        a-=1
    else :
      b-=1
    k-=1
print(a,b)

### FIXED CODE ###

from sys import stdin
a,b,k=[int(x) for x in stdin.readline().rstrip().split()]
if b+a-k<0:
    print(0,0)
elif a-k<0:
    print(0,b+a-k)
else:
    print(a-k,b)
### BUGGY CODE ###

def soleve(i, m, A):
    if m == 0:
        return True
    if i >= len(A):
        return False
    res = soleve(i + 1, m, A) or soleve(i + 1, m - A[i], A)
    return res

n = int(raw_input())
A = map(int, raw_input().split())
q = int(raw_input())
M = map(int, raw_input().split())
for m in M:
    if soleve(0, m, A):
        print 'yes'
    else:
        print 'no'

### FIXED CODE ###

n = int(raw_input())
A = map(int, raw_input().split())
d = {}

def soleve(i, m, n):
    if m == 0:
        return True
    if i >= n:
        return False
    if d.has_key((i, m)):
        return d[(i, m)]
    res = soleve(i + 1, m, n) or soleve(i + 1, m - A[i], n)
    d[(i, m)] = res
    return res


q = int(raw_input())
M = map(int, raw_input().split())
for m in M:
    if soleve(0, m, n):
        print 'yes'
    else:
        print 'no'
### BUGGY CODE ###

from collections import deque
import sys

sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
que = deque()
# 始点を追加
for i in range(H):
    for j in range(W):
        if G[i][j] == '#':
            que.append([i, j])
cnt = -1
while que:
    cnt += 1
    next_que = deque()
    while que:
        h, w = que.popleft()  # BFSで探索
        dh = [1, 0, -1, 0]
        dw = [0, 1, 0, -1]
        for j in range(4):
            nh = h + dh[j]
            nw = w + dw[j]
            if 0 <= nh < H and 0 <= nw < W and G[nh][nw] == '.':
                G[nh][nw] = '#'
                next_que.append([nh, nw])
    que = next_que
print(cnt)

### FIXED CODE ###

from collections import deque
import sys

sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
que = deque()
# 始点を追加
for i in range(H):
    for j in range(W):
        if G[i][j] == '#':
            que.append([i, j])
cnt = -1
while que:
    cnt += 1
    next_que = deque()
    while que:
        h, w = que.popleft()  # BFSで探索
        dh = [1, 0, -1, 0]
        dw = [0, 1, 0, -1]
        for j in range(4):
            nh = h + dh[j]
            nw = w + dw[j]
            if 0 <= nh < H and 0 <= nw < W and G[nh][nw] == '.':
                G[nh][nw] = '#'
                next_que.append([nh, nw])
    que = next_que
print(cnt)
### BUGGY CODE ###

from itertools import combinations

EPS = 1e-8

N, K, *XYC = map(int, open(0).read().split())
PC = [(complex(x, y), c) for x, y, c in zip(*[iter(XYC)] * 3)]


def intersection(A, r, B, s):
    D = B - A
    d = abs(D)

    cos_t = (d * d + r * r - s * s) / (2 * d * r)
    sin_t = max(1 - cos_t * cos_t, 0.0) ** 0.5

    R = r * complex(cos_t, sin_t)
    D /= d

    return (
        A + D * R,
        A + D * R.conjugate(),
    )


def is_ok(T):
    A = [p for p, _ in PC]
    for (p1, c1), (p2, c2) in combinations(PC, 2):
        A += intersection(p1, T / c1, p2, T / c2)

    for a in A:
        cnt = 0
        for p, c in PC:
            if c * abs(a - p) <= T + EPS:
                cnt += 1
        if K <= cnt:
            return True
    return False


ng, ok = 0, 10000000
for _ in range(100):
    md = (ng + ok) / 2
    if is_ok(md):
        ok = md
    else:
        ng = md

print(ok)

### FIXED CODE ###

from math import hypot
from collections import deque

N, K, *XYC = map(int, open(0).read().split())
XYC = list(zip(*[iter(XYC)] * 3))

Q = deque([(0, 0, 1000.0)])

ans = float("inf")
while Q:
    X, Y, r = Q.popleft()
    if ans * 0.9999995 > sorted(c * hypot(max(abs(X - x) - r, 0), max(abs(Y - y) - r, 0)) for x, y, c in XYC)[K - 1]:
        ans = min(ans, sorted(c * hypot(X - x, Y - y) for x, y, c in XYC)[K - 1])
        for dx, dy in [(-0.5, -0.5), (-0.5, 0.5), (0.5, -0.5), (0.5, 0.5)]:
            Q.append((X + dx * r, Y + dy * r, r / 2))

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

N = int(input())
S = input()
L = [chr(ord('a') + i) for i in range(26)]
cnt = [0]*26
for i in range(len(S)):
  cnt[ord(S[i])-97] += 1
D = []
for i in range(26):
  if cnt[i] != 0:
    D.append(cnt[i])
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)
ans = 0
n = 2
for X in range(1,2**len(D)):
  k = Base_10_to_n(X, n).zfill(len(D))
  cur = 1
  for i in range(len(k)):
    if k[i] == '1':
      cur *= (D[i]%(10**9+7))
  ans += (cur%(10**9+7))
print(ans%(10**9+7))

### FIXED CODE ###

N = int(input())
S = input()
L = [chr(ord('a') + i) for i in range(26)]
cnt = [0]*26
for i in range(len(S)):
  cnt[ord(S[i])-97] += 1
D = []
for i in range(26):
  if cnt[i] != 0:
    D.append(cnt[i])
ans = 1
for i in range(len(D)):
  ans *= (D[i]+1)
  ans = ans%(10**9+7)
print((ans-1)%(10**9+7))
### BUGGY CODE ###

H, W = list(map(int,input().split()))
ans = H*W
h = H
w = W
for i in range(h//3,h//2+1):
    p1 = i*w
    for j in range((h-i)//3,(h-i)//2+1):
        p2 = (h-i-j)*W
        ans = min(ans, max(p1,p2,h*w-p1-p2)-min(p1,p2,h*w-p1-p2))
    for j in range(w//3,w//2+1):
        p2 = (h-i)*(w-j)
        ans = min(ans, max(p1,p2,h*w-p1-p2)-min(p1,p2,h*w-p1-p2))
h = W
w = H
for i in range(h//3,h//2+1):
    p1 = i*w
    for j in range((h-i)//3,(h-i)//2+1):
        p2 = (h-i-j)*W
        ans = min(ans, max(p1,p2,h*w-p1-p2)-min(p1,p2,h*w-p1-p2))
    for j in range(w//3,w//2+1):
        p2 = (h-i)*(w-j)
        ans = min(ans, max(p1,p2,h*w-p1-p2)-min(p1,p2,h*w-p1-p2))
print(ans)

### FIXED CODE ###

H, W = list(map(int,input().split()))
ans = H*W
h = H
w = W
for i in range(h//3,h//2+1):
    p1 = i*w
    for j in range((h-i)//2-1,(h-i)//2+1):
        p2 = (h-i-j)*W
        ans = min(ans, max(p1,p2,h*w-p1-p2)-min(p1,p2,h*w-p1-p2))
    for j in range(w//2-1,w//2+1):
        p2 = (h-i)*(w-j)
        ans = min(ans, max(p1,p2,h*w-p1-p2)-min(p1,p2,h*w-p1-p2))
h = W
w = H
for i in range(h//3,h//2+1):
    p1 = i*w
    for j in range((h-i)//2-1,(h-i)//2+1):
        p2 = (h-i-j)*H
        ans = min(ans, max(p1,p2,h*w-p1-p2)-min(p1,p2,h*w-p1-p2))
    for j in range(w//2-1,w//2+1):
        p2 = (h-i)*(w-j)
        ans = min(ans, max(p1,p2,h*w-p1-p2)-min(p1,p2,h*w-p1-p2))
print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
ans=[True]*n
l.sort()
for i in range(n):
    if ans[i]:
        if i!=n-1:
          if l[i]==l[i+1]:
            ans[i]=False
        for j in range(i+1,n):
            if l[j]%l[i]==0:
                ans[j]=False
print(sum(ans))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 1
cnt = [0] * M
for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for b in range(a, M, a):
        cnt[b] += 1
ans = 0
for a in A:
    if cnt[a] == 1:ans += 1
print(ans)
### BUGGY CODE ###

from operator import itemgetter

H,W,D = [int(x) for x in input().split()]
dli = [[] for _ in range(D)]
for i in range(H):
    x = [int(x) for x in input().split()]
    for ind,j in enumerate(x):
        dli[j%D].append([j,i,ind])
        dli[j%D].sort()
Q = int(input())
LR = [[int(x) for x in input().split()]for _ in range(Q)]
#%%
stims = []
dinds = []
for d in dli:
    #total dist,now pos
    #inds = num
    stim = [[0,0,0]]
    inds = []
    for i in d:
        stim.append([stim[-1][0]+abs(i[1]-stim[-1][1])+abs(i[2]-stim[-1][2]),i[1],i[2]])
        inds.append(i[0])
    stims.append(stim)
    dinds.append(inds)

for i in LR:
    dnum = i[0]%D
    l = dinds[dnum].index(i[0])+1
    r = dinds[dnum].index(i[1])+1
    print(stims[dnum][r][0]-stims[dnum][l][0])


### FIXED CODE ###

from operator import itemgetter

H,W,D = [int(x) for x in input().split()]
a = []

for i in range(H):
    x = [int(x) for x in input().split()]
    for ind,j in enumerate(x):
        a.append([j,i,ind])
a.sort(key=itemgetter(0))
Q = int(input())
LR = [[int(x) for x in input().split()]for _ in range(Q)]
#%%
stims = [[[0,0,0]]for _ in range(D)]
dinds = [{}for _ in range(D)]
for i in a:
    d = i[0]%D
    stims[d].append([stims[d][-1][0]+abs(i[1]-stims[d][-1][1])+abs(i[2]-stims[d][-1][2]),i[1],i[2]])
    dinds[d][i[0]]=len(stims[d])-1

for i in LR:
    dnum = i[0]%D
    l = dinds[dnum][i[0]]
    r = dinds[dnum][i[1]]
    print(stims[dnum][r][0]-stims[dnum][l][0])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()
a_list = []
for i in range(N):
    temp = _li_()
    temp.append(i-N)  # 番兵
    a_list.append(temp)
a_list = np.array(a_list)

n_index = np.arange(N)
a_index = np.zeros(N, dtype=int)
ans = 0
for i in range(N * (N-1) // 2):
    current = a_list[n_index, a_index]
    update = current[current] == n_index
    a_index[update] += 1

    if update.sum() == 0:
        break
    else:
        ans += 1

if a_index.sum() == (N-1) * N:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

from sys import stdin
# import numpy as np
from collections import deque
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()

move_in = [[[] for i in range(N)] for j in range(N)]
move_out = [[[] for i in range(N)] for j in range(N)]
cost = [[0] * N for _ in range(N)]
start_pair = []
for i in range(N):
    a_list = _li_()
    start_pair.append(a_list[0])
    for j in range(N-2):
        start = [min(i, a_list[j]), max(i, a_list[j])]
        end = [min(i, a_list[j+1]), max(i, a_list[j+1])]
        move_in[end[0]][end[1]].append((start[0], start[1]))
        move_out[start[0]][start[1]].append((end[0], end[1]))

count = 0
stack = deque([])
for i in range(N):
    pair = start_pair[i]
    if i < pair and i == start_pair[pair]:
        stack.append((i, start_pair[i]))
        cost[i][start_pair[i]] = 1
        count += 1


ans = 0
while stack:
    cand = stack.pop()
    for dest in move_out[cand[0]][cand[1]]:
        cost[dest[0]][dest[1]] = max(cost[dest[0]][dest[1]],
                                     cost[cand[0]][cand[1]] + 1)
        in_list = move_in[dest[0]][dest[1]]
        if in_list[0] == cand:
            del in_list[0]
        else:
            del in_list[1]
        if len(in_list) == 0:
            count += 1
            if len(move_out[dest[0]][dest[1]]) == 0:
                ans = max(ans, cost[dest[0]][dest[1]])
            else:
                stack.append(dest)

if count == (N * (N-1) // 2):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

from collections import defaultdict
N, M , Q = map(int, input().split())

LR = defaultdict(lambda: defaultdict(int))
for i in range(M):
  L, R = map(int, input().split())
  LR[L][R] += 1

for i in range(Q):
  p, q = map(int, input().split())
  S = 0
  for l,R in LR.items():
    if not p <= l <= q: continue
    for r,s in R.items():
      if q < r: continue
      S += s
  print(S)

### FIXED CODE ###

N, M , Q = map(int, input().split())

LR = [[0]*(N+2-i) for i in range(N+2)]
for i in range(M):
  L, R = map(int, input().split())
  LR[L][R-L+1] += 1

  
for i in range(2,N+2):
  for j in range(1,N-i+2):
    LR[j][i] += LR[j][i-1] + LR[j+1][i-1] - LR[j+1][i-2]
    
for i in range(Q):
  p, q = map(int, input().split())
  print(LR[p][q-p+1]-LR[q+1][0])