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

import sys
from bisect import bisect

def main():
    input = sys.stdin.readline
    N = int(input())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    C = sorted(list(map(int, input().split())))

    Bn = [0] * N
    for i in range(N):
        b = B[i]
        m = bisect(C, b)
        Bn[i] = (N - m)

    ans = 0
    for i in range(N):
        a = A[i]
        m = bisect(B, a)
        ans += sum(Bn[m:])

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from bisect import bisect
from itertools import accumulate

def main():
    input = sys.stdin.readline
    N = int(input())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    C = sorted(list(map(int, input().split())))

    Bn = [0] * N
    for i in range(N):
        b = B[i]
        m = bisect(C, b)
        Bn[i] = (N - m)

    Bn = list(accumulate(Bn[::-1]))[::-1]
    Bn += [0]

    ans = 0
    for i in range(N):
        a = A[i]
        m = bisect(B, a)
        ans += Bn[m]

    print(ans)


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

def main():
    s = input()
    flag = True
    l = [""]
    sm = [i for i in range(0,len(s)+1)]
    for i in range(1,len(sm)):
        sm[i] = sm[i-1]+sm[i]
    lap = l.append
    for i in range(len(s)):
        if flag:
            l[-1] = l[-1] + s[i]
        else:
            lap(s[i])
        if i < len(s)-1:
            if s[i] == "<" and s[i+1] == ">":
                flag = False
            else:
                flag = True
    xlist = []
    ylist = []
    xap = xlist.append
    yap = ylist.append
    for i in l:
        x = 0
        y = 0
        for j in list(i):
            if j == ">":
                x += 1
            else:
                y += 1
        xap(x)
        yap(y)
    for i in range(1,len(l)):
        x = xlist[i]
        y = ylist[i-1]
        if y <= x:
            xlist[i] = sm[x]
            ylist[i-1] = sm[max([0,y-1])]
        else:
          xlist[i] = sm[max([0,x-1])]
          ylist[i-1] = sm[y]
    xlist[0] = sm[xlist[0]]
    ylist[-1] = sm[ylist[-1]]
    print(sum(xlist)+sum(ylist))
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    s = input()
    f1 = False
    f2 = False
    l = [1]
    if s[0] == "<":
        f1 = True
        l.insert(0,0)
    if s[-1] == ">":
        f2 = True
    sm = [i for i in range(0,len(s)+1)]
    for i in range(1,len(sm)):
        sm[i] = sm[i-1]+sm[i]
    lap = l.append
    for i in range(1,len(s)):
        if s[i] == s[i-1]:
            l[-1] += 1
        else:
            lap(1)
    dlist = []
    plist = []
    dap = dlist.append
    pap = plist.append
    if f2:
        l.append(0)
    for i in range(len(l)//2):
        dap(l[2*i])
        pap(l[2*i+1])   
    for i in range(1,len(dlist)):
        x = dlist[i]
        y = plist[i-1]
        if y <= x:
            dlist[i] = sm[x]
            plist[i-1] = sm[max([0,y-1])]
        else:
          dlist[i] = sm[max([0,x-1])]
          plist[i-1] = sm[y]
    dlist[0] = sm[dlist[0]]
    plist[-1] = sm[plist[-1]]
    print(sum(dlist)+sum(plist))
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))

for q in range(k):
  b = [0]*(n+1)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
      
  a[0] = b[0]
  for j in range(n-1):
    a[j+1] = a[j] + b[j+1]

print(*a)

### FIXED CODE ###

#%%time
from itertools import accumulate
import numpy as np
from numba import njit

n, k = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int64)

@njit
def loop1(a):
  #b = [0]*(n+1)
  b = np.zeros(n+1, dtype=np.int64)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
  
  b = np.cumsum(b)[:-1]
  return b
  #a = list(accumulate(b))
  #a = a[:-1]
   
  #if np.all(a == n):
   # break

for q in range(min(42, k)):
  a = loop1(a)
    
print(*a)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
total = 1
for i in range(len(a)):
	total *= a[i]
if total > 10**18:
	total =-1
    
print(total)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
total = 1
k = 10**18
for i in range(len(a)):
	if a[i] == 0:
		total = 0
		break
if total != 0:
  for i in range(len(a)):	
      total *= a[i]
      if total > k:
          total =-1
          break    
print(total)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
G = [[] for _ in range(N)]
e = []
queue = deque([])
for l in range(N-1):
    temp = list(map(int,input().split()))
    temp[0] -= 1
    temp[1] -= 1
    e.append(temp)
    G[temp[0]].append(temp[1])
    G[temp[1]].append(temp[0])
    if l == 0:
        queue.append(temp[0])
#使えない色
nuc = [[0] for _ in range(N)]
#使った色
auc = []
#答え
ans = [[0] * N for _ in range(N)]
def bfs(x):
    for i in G[x]:
        if ans[x][i] ==0 and ans[i][x] == 0:
            queue.append(i)
            for k in range(1,N):
                if k not in nuc[x] and k not in nuc[i]:
                    ans[x][i] = k
                    ans[i][x] = k
                    nuc[x].append(k)
                    nuc[i].append(k)
                    if k not in auc:
                        auc.append(k)
                    break
while len(queue) > 0:
    next_ = queue.popleft()
    bfs(next_)
print(len(auc))
for m in e:
    print(ans[m[0]][m[1]])


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
G = [[] for _ in range(N)]
ans = {}
queue = deque([])
e = []
for l in range(N-1):
    temp = list(map(int,input().split()))
    temp[0] -= 1
    temp[1] -= 1
    e.append(tuple(temp))
    ans[(temp[0],temp[1])] = 0
    ans[(temp[1],temp[0])] = 0
    G[temp[0]].append(temp[1])
    G[temp[1]].append(temp[0])
    if l == 0:
        queue.append(temp[0])
#使えない色
nuc = [[0] for _ in range(N)]
#使った色
auc = []
#答え
def bfs(x):
    k = 1
    for i in G[x]:
        if ans[(x,i)] ==0:
            queue.append(i)
            flag = 1
            while flag:
                if k not in nuc[x]:         
                    ans[(x,i)] = k
                    ans[(i,x)] = k
                    nuc[x].append(k)
                    nuc[i].append(k)
                    if k not in auc:
                        auc.append(k)
                    flag = 0
                else:
                    k += 1
                
while len(queue) > 0:
    next_ = queue.popleft()
    bfs(next_)
print(len(auc))
for m in e:
    print(ans[m])
### BUGGY CODE ###

a=input().split()
N=int(a[0])
M=int(a[1])
H=[int(x) for x in input().split()]
way=[]
for i in range(M):
    way.append([int(x) for x in input().split()])

ans=0
for i in range(N):
    con_i=[]
    for j in range(M):
        if way[j][0]==i+1:
            con_i.append(way[j][1]-1)
        if way[j][1]==i+1:
            con_i.append(way[j][0]-1)
    
    higher=0    
    for k in con_i:
        if H[i]>H[k]:
            higher+=1
           
    if higher==len(con_i):
        ans+=1
    
print(ans)


            

        


### FIXED CODE ###

a=input().split()
N=int(a[0])
M=int(a[1])
H=[int(x) for x in input().split()]
way=[]
for i in range(M):
    way.append([int(x) for x in input().split()])

dic={}
for i in range(N):
    dic[i]=set()

for h in way:
    dic[h[0]-1].add(h[1]-1)
    dic[h[1]-1].add(h[0]-1)
    

print(sum(all([H[i]>H[hs] for hs in dic[i]])for i in range(N)))
### BUGGY CODE ###

import bisect
 
N, M = map(int, input().split())
Ai = list(map(int, input().split()))
 
Ai.sort()
for _ in range(M):
    value = int(Ai.pop() / 2)
    bisect.insort(Ai, value)
 
print(sum(Ai))

### FIXED CODE ###

from collections import deque

N, M = map(int, input().split())
Ai = list(map(int, input().split()))

Ai.sort(reverse=True)
Ai_deque = deque(Ai)
kari = deque()
for _ in range(M):
    try:
        if Ai_deque[0] > kari[0]:
            value = Ai_deque.popleft() // 2
        else:
            value = kari.popleft() // 2
    
    except:
        if not kari:
            value = Ai_deque.popleft() // 2
        else:
            value = kari.popleft() // 2
    
    kari.append(value)
    
print(sum(Ai_deque) + sum(kari))
### BUGGY CODE ###

# C - 100 to 105
X = int(input())

for a in range(5001):
    for b in range(5001-100*a):
        for c in range(5001-100*a-101*b):
            for d in range(5001-100*a-101*b-102*c):
                for e in range(5001-100*a-101*b-102*c-103*d):
                    for f in range(5001-100*a-101*b-102*c*103*d-104*e):
                        if 100*a+101*b+102*c+103*d+104*e+105*f == X:
                            print(1)
                            exit()
                        else:
                            pass
print(0)

### FIXED CODE ###

# C - 100 to 105
X = int(input())

for a in range(2501):
    for b in range(2501-100*a):
        for c in range(2501-100*a-101*b):
            for d in range(2501-100*a-101*b-102*c):
                for e in range(2501-100*a-101*b-102*c-103*d):
                    for f in range(2501-100*a-101*b-102*c*103*d-104*e):
                        if 100*a+101*b+102*c+103*d+104*e+105*f == X:
                            print(1)
                            exit()
                        else:
                            pass
print(0)
### BUGGY CODE ###

h, w = map(int, input().split())
mat = []
for i in range(h):
  a = list(map(int, input().split()))
  mat.append(a)
for i in range(h):
  b = list(map(int, input().split()))
  for j in range(w):
    mat[i][j] = abs(mat[i][j]-b[j])

dp = [[[False]*(80*(h+w)) for i in range(w)] for k in range(h)]
dp[0][0][mat[0][0]] = True
for y in range(h):
  for x in range(w):
      for k in range(50*(x+y)):
        if x > 0 and dp[y][x-1][k] or y > 0 and dp[y-1][x][k]:
          d = dp[y][x]
          d[k+mat[y][x]] = True
          d[abs(k-mat[y][x])] = True

for k in range(80*(h+w)):
  if dp[h-1][w-1][k]:
    print(k)
    exit()


### FIXED CODE ###

h, w = map(int, input().split())
mat = []
for i in range(h):
  a = list(map(int, input().split()))
  mat.append(a)
for i in range(h):
  b = list(map(int, input().split()))
  for j in range(w):
    mat[i][j] = abs(mat[i][j]-b[j])
m = max(map(max, mat))
dp = [[0b0 for i in range(w)] for k in range(h)]
dp[0][0] |= 0b1 << mat[0][0]
for y in range(h):
  for x in range(w):
        if x > 0:
          dp[y][x] |= dp[y][x-1] << mat[y][x]
          dp[y][x] |= dp[y][x-1] >> mat[y][x]
          anded = dp[y][x-1] & int('1'*(mat[y][x]+1), 2)
          reverse = format(anded, "0"+str(mat[y][x]+1)+"b")[::-1]

          dp[y][x] |= int(reverse, 2)
        if y > 0:
          dp[y][x] |= dp[y-1][x] << mat[y][x]
          dp[y][x] |= dp[y-1][x] >> mat[y][x]
          anded = dp[y-1][x] & int('1'*(mat[y][x]+1), 2)
          reverse = format(anded, "0"+str(mat[y][x]+1)+"b")[::-1]

          dp[y][x] |= int(reverse, 2)
        #print(bin(dp[y][x]))

keta = 0
while dp[h-1][w-1] % 2 == 0:
  keta += 1
  dp[h-1][w-1] //= 2
print(keta)
### BUGGY CODE ###

from operator import itemgetter

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    BC = []
    for i in range(M):
        bc = list(map(int, input().split()))
        BC.append(bc)

    BC.sort(key=itemgetter(1), reverse=True)
    B = []
    for b, c in BC:
        B = B + [c] * b
        if len(B) > N:
            break

    A.sort(reverse=True)
    
    i = 0
    j = 0
    r = []

    cnt = 0
    while len(r) != N:
        # print(i, j)
        if j > M - 1:
            r.append(A[i])
            i += 1
            continue

        b, c = BC[j]
        if A[i] >= c:
            r.append(A[i])
            i += 1
        else:
            r.append(c)
            cnt += 1
            if cnt == b:
                j += 1
                cnt = 0

    # print(r)
    ans = sum(r)
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from operator import itemgetter

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    BC = []
    for i in range(M):
        bc = list(map(int, input().split()))
        BC.append(bc)

    BC.sort(key=itemgetter(1), reverse=True)
    # B = []
    # for b, c in BC:
    #     B = B + [c] * b
    #     if len(B) > N:
    #         break

    A.sort(reverse=True)
    
    i = 0
    j = 0
    r = []

    cnt = 0
    while len(r) != N:
        # print(i, j)
        if j > M - 1:
            r.append(A[i])
            i += 1
            continue

        b, c = BC[j]
        if A[i] >= c:
            r.append(A[i])
            i += 1
        else:
            r.append(c)
            cnt += 1
            if cnt == b:
                j += 1
                cnt = 0

    # print(r)
    ans = sum(r)
    print(ans)


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

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

Prenum = [[] for i in range(N)]
PreYear = [1 for i in range(M)]
PY = [input().split(' ') for i in range(M)]
P = [PY[i][0] for i in range(M)]
Y = [PY[i][1] for i in range(M)]

for i in range(M):
    Pi, Yi = map(int,PY[i])

    count = 1
    for j in range(i):
        if P[j] == str(Pi):
            if int(Y[j]) > Yi:
                PreYear[j] = PreYear[j]+1
            else:
                count +=1 
    PreYear[i] = count

for i in range(M):
    Pi, Yi = map(int,PY[i])
    print('{0:06d}{1:06d}'.format(Pi,PreYear[i]))

### FIXED CODE ###

from operator import itemgetter


N, M = map(int, input().split(' '))
data = []
for i in range(M):
    Pi, Yi = map(int, input().split(' '))
    data.append([i,Pi,Yi])

sorted_data = sorted(data, key=itemgetter(1,2))

codes = []
prev_p = 0
for i,p,y in sorted_data:
    if p!=prev_p:
        x = 1
        prev_p = p
    else:
        x+=1

    code = '{0:06d}{1:06d}'.format(p,x)
    codes.append([i,code])

sorted_codes = sorted(codes, key = itemgetter(0))

for code in sorted_codes:
    print(code[1])
### BUGGY CODE ###

def main():
    import sys

    H, W = map(int, sys.stdin.readline().split())
    A = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    B = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    X = [[0] * W for i in range(H)]
    for h in range(H):
        for w in range(W):
            X[h][w] = abs(A[h][w] - B[h][w])

    dp = {}
    dp[0] = set()
    dp[0].add(X[0][0])
    dp[0].add(-X[0][0])

    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            x = X[h][w]
            s = set()

            threshold = ((H - h) + (W - w)) * 79
            if W * h + w > W - 1:
                for d in dp[W * (h - 1) + w]:

                    if d + x <= threshold:
                        s.add(d + x)
                    if d - x >= -threshold:
                        s.add(d - x)

            if (W * h + w) % W != 0:
                for d in dp[W * h + w - 1]:
                    if d + x <= threshold:
                        s.add(d + x)
                    if d - x >= -threshold:
                        s.add(d - x)

            dp[W * h + w] = s

    ans = min([abs(s) for s in dp[W * H - 1]])
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys

    H, W = map(int, sys.stdin.readline().split())
    A = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    B = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    X = [[0] * W for i in range(H)]
    for h in range(H):
        for w in range(W):
            X[h][w] = abs(A[h][w] - B[h][w])

    dp = [[set() for j in range(W)] for i in range(H)]
    dp[0][0].add(X[0][0])
    dp[0][0].add(-X[0][0])

    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            x = X[h][w]
            s = set()

            if h > 0:
                for d in dp[h - 1][w]:
                    s.add(d + x)
                    s.add(abs(d - x))

            if w > 0:
                for d in dp[h][w - 1]:
                    s.add(d + x)
                    s.add(abs(d - x))

            dp[h][w] = s

    ans = min([abs(s) for s in dp[H - 1][W - 1]])
    print(ans)


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

N, A = map(int,input().split())
x = list(map(int,input().split()))

dp = [[[0 for k in range(N*A+1)] for j in range(N+1)] for l in range(N+1)]
dp[0][0][0] = 1

for p in range(N):
    for q in range(N):
        for r in range(N*A):
            dp[p+1][q][r] += dp[p][q][r]
            if r+x[p] <= N*A:
                dp[p+1][q+1][r+x[p]] += dp[p][q][r]
                
ans = 0
for k in range(1,N+1):
    ans += dp[N][k][k*A]
print(ans)

### FIXED CODE ###

N, A = map(int,input().split())
x = list(map(int,input().split()))

dp = [[[0 for k in range(N*A+1)] for j in range(N+1)] for l in range(N+1)]
dp[0][0][0] = 1

for p in range(N):
    for q in range(N):
        for r in range(N*A):
            dp[p+1][q][r] += dp[p][q][r]
            if r+x[p] <= N*A:
                dp[p+1][q+1][r+x[p]] += dp[p][q][r]
                
ans = 0
for k in range(1,N+1):
    ans += dp[N][k][k*A]
print(ans)
### BUGGY CODE ###

R,G,B,N= map(int, input().split())
answer=0

for r in range(3001):
    for g in range(3001):
        for b in range(3001):
            if R * r + G * g + B * b == N:
                answer += 1
                break
            elif R * r + G * g + B * b > N:
                break
        if R * r + G * g> N:
            break
    if R*r>N:
        break
print(answer)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range(3001):
    for g in range(3001):
        Bb = N - R * r - G * g
        if Bb >= 0 and Bb % B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

#from heapq import nsmallest as hp
l,r = map(int,input().split())
tmp = 2019**2
tmp2 = 0
for i in range(l,r+1):
  
  for j in range(i+1,r+1):
    tmp = min(tmp,i*j%2019)
    
  if tmp == 0:
    break

print(tmp)


### FIXED CODE ###

l,r = map(int,input().split())
tmp = 2019
tmp2 = 0
for i in range(l,min(r+1,l+2018)):
  
  for j in range(i+1,min(r+1,l+2018)):
    tmp = min(tmp,i*j%2019)
    
  if tmp == 0:
    break

print(tmp)
### BUGGY CODE ###

def find_min_fuka_idx(lst, x):
  ok = -1
  ng = len(lst)
  while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if x>=lst[mid]:
      ok = mid
    else:
      ng = mid
  return ng

a,b,q = map(int, input().split())
s = [-10**18]
for i in range(a):
  s.append(int(input()))
s.append(10**18)
t = [-10**18]
for i in range(b):
  t.append(int(input()))
t.append(10**18)

for i in range(q):
  x = int(input())
  si = find_min_fuka_idx(s, x)
  tj = find_min_fuka_idx(t, x)
  print(min(abs(x-s[si])+abs(s[si]-t[tj]),\
            abs(x-s[si])+abs(s[si]-t[tj-1]),\
           abs(x-t[tj])+abs(t[tj]-s[si]),\
            abs(x-t[tj])+abs(t[tj]-s[si-1]),\
            abs(x-s[si-1])+abs(s[si-1]-t[tj]),\
            abs(x-s[si-1])+abs(s[si-1]-t[tj-1]),\
           abs(x-t[tj-1])+abs(t[tj-1]-s[si]),\
            abs(x-t[tj-1])+abs(t[tj-1]-s[si-1])))


### FIXED CODE ###

import bisect
def find_min_fuka_idx(lst, x):
  ok = -1
  ng = len(lst)
  while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if x>=lst[mid]:
      ok = mid
    else:
      ng = mid
  return ng

a,b,q = map(int, input().split())
s = [-10**18]
s_mid = [int(input()) for i in range(a)]
s.extend(s_mid)
s.append(10**18)

t = [-10**18]
t_mid = [int(input()) for i in range(b)]
t.extend(t_mid)
t.append(10**18)

for i in range(q):
  x = int(input())
  si = bisect.bisect_right(s, x)
  tj = bisect.bisect_right(t, x)
  print(min(abs(x-s[si])+abs(s[si]-t[tj]),\
            abs(x-s[si])+abs(s[si]-t[tj-1]),\
           abs(x-t[tj])+abs(t[tj]-s[si]),\
            abs(x-t[tj])+abs(t[tj]-s[si-1]),\
            abs(x-s[si-1])+abs(s[si-1]-t[tj]),\
            abs(x-s[si-1])+abs(s[si-1]-t[tj-1]),\
           abs(x-t[tj-1])+abs(t[tj-1]-s[si]),\
            abs(x-t[tj-1])+abs(t[tj-1]-s[si-1])))
### BUGGY CODE ###

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

first = []

for ab in AB:
    if ab[0] == 1:
        first.append(ab[1])

for ab in AB:
    if ab[0] in first and ab[1] == N:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')



### FIXED CODE ###

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

first_to = []
to_dest = []

for ab in AB:
    if ab[0] == 1:
        first_to.append(ab[1])
    elif ab[1] == N:
        to_dest.append(ab[0])
first_to = set(first_to)
to_dest = set(to_dest)

for f in first_to:
    if f in to_dest:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

N  = int(input())
Ai = sorted(map(int,input().split()))
Bi = sorted(map(int,input().split()))
Ci = sorted(map(int,input().split()))

def f(X,Y,S):
	i,ret = 0, [0 for _ in range(N)]
	for k,x in enumerate(X):
		while x>=Y[i]:
			i += 1
			if i==N: return ret
		ret[k] = sum(S[i:])
	return ret

Ki = f(Bi,Ci,[1]*N)
Hi = f(Ai,Bi,Ki)
print(sum(Hi))




### FIXED CODE ###

import bisect
N = int(input())
A = sorted(map(int,input().split()))
B = sorted(map(int,input().split()))
C = sorted(map(int,input().split()))
print(sum(bisect.bisect_left(A,b)*(N-bisect.bisect_right(C,b)) for b in B))
### BUGGY CODE ###

h,w,d = [int (i) for i in input().split()]
index = [[0,0] for i in range(h*w)]
sum = 0
for i in range(h):
    temp = [int(i) for i in input().split()]
    for j in range(w):
        index[temp[j]-1][0] = i
        index[temp[j]-1][1] = j
q = int(input())
empty = []
for i in range(q):
    sum = 0
    a,b = [int (i) for i in input().split()]
    c = (b-a)//d
    if c == 0:
        sum = 0
    else:
        for i in range(c):
            sum += abs(index[a-1][0] - index[a+d-1][0])+abs(index[a-1][1] - index[a+d-1][1])
            a   += d
    empty.append(sum)

for i in range(q):
    print(empty[i])

### FIXED CODE ###

h,w,d = [int (i) for i in input().split()]
index = [[0,0] for i in range(h*w)]
sum = 0
for i in range(h):
    temp = [int(i) for i in input().split()]
    for j in range(w):
        index[temp[j]-1][0] = i
        index[temp[j]-1][1] = j
q = int(input())
dick = [0 for i in range (h*w)]
for i in range (d,h*w):
    dick[i] = dick[i-d] + abs(index[i][0]-index[i-d][0])+abs(index[i][1]-index[i-d][1])
for i in range(q):
    a,b = [int(i) for i in input().split()]
    print(dick[b-1] - dick[a-1])
### BUGGY CODE ###

def main():
    import numpy as np
    k, q = map(int, input().split())
    d = np.array(list(map(int, input().split())), dtype=np.int64)
    nxm = [list(map(int, input().split())) for _ in [0]*q]
    for n, x, m in nxm:
        d2 = sum((d[:(n-2) % k+1]-1) % m+1)
        d3 = sum((d[(n-2) % k+1:]-1) % m+1)
        print(n-1-(x % m+(d2+d3)*((n-2)//k)+d2)//m)


main()


### FIXED CODE ###

def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    nxm = [list(map(int, input().split())) for _ in [0]*q]
    for n, x, m in nxm:
        d2 = sum([(i-1) % m+1 for i in d[:(n-2) % k+1]])
        d3 = sum([(i-1) % m+1 for i in d[(n-2) % k+1:]])
        print(n-1-(x % m+(d2+d3)*((n-2)//k)+d2)//m)


main()