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

s = list(input())
s.reverse()
n = len(s)
mod = 10**9+7
#dp[i][j] := 下からi桁目まで決めたとき、13で割った余りがjの個数
dp = [[0 for i in range(13)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(13):
        char = s[i]
        if char == '?':
            for k in range(10):
                #i+1桁目をkにする
                tmp = (k * (10 ** i)) % 13
                dp[i+1][(j + tmp) % 13] += dp[i][j]
                dp[i+1][(j + tmp) % 13] %= mod
        else:
            x = int(char)
            tmp = x * (10**i)
            dp[i+1][(j + tmp) % 13] += dp[i][j]
            dp[i+1][(j + tmp) % 13] %= mod
print(dp[n][5])



### FIXED CODE ###

s = input()
#文字の昇順に処理していきたいため、逆順にしておく
s = s[::-1]
mod = 7 + 10**9
keta = 1
dp = [[0 for i in range(13)] for j in range(len(s) + 1)]
dp[0][0] = 1
for i in range(len(s)):
    if s[i] != "?":
        k = (int(s[i]) * keta) % 13
        for j in range(13):
            dp[i + 1][(j + k) % 13] = dp[i][j]
    else:
        for j in range(13):
            for k in range(10):
                l = ( k * keta ) % 13
                dp[i + 1][(j + l) % 13] += dp[i][j] % mod
    keta = keta *10 % 13 
print(dp[-1][5] % mod)
### BUGGY CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
A = [0] + A
L = []
S = set()
i = 1
cnt = 0
while not i in S or cnt != K:
    S.add(i)
    L.append(i)
    cnt += 1
    i = A[i]

if cnt == K:
    print(i)
else:
    j = L.index(i)
    ans = L[(j + (K - j) % (cnt - j)) % cnt]
    print(ans)

### FIXED CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
A = [0] + A
L = []
S = set()
i = 1
cnt = 0
while (not i in S) and cnt != K:
    S.add(i)
    L.append(i)
    cnt += 1
    i = A[i]

if cnt == K:
    print(i)
else:
    j = L.index(i)
    ans = L[(j + (K - j) % (cnt - j)) % cnt]
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n=int(input())
count=0
a=[int(input()) for _ in range(n)]
for x in a:
    if a.count(x)%2==1:
        count+=1
print(count)


### FIXED CODE ###

import collections
n=int(input())
count=0
a=[int(input()) for _ in range(n)]
a=collections.Counter(a)

for key,value in a.items():
    if value%2==1:
        count+=1
print(count)
### BUGGY CODE ###

x,y = [int(i) for i in input().split(" ")]

if x%y == 0:
    print(-1)
    quit()

for i in range(x*2,10**18+1,x):
    if (i < y*2):
        continue
    elif (i%y != 0):
        print(i)
        quit()
print(-1)



### FIXED CODE ###

x,y = [int(i) for i in input().split(" ")]

if x%y == 0:
    print(-1)
    quit()

if x==1:
    print(y*2+1)
    quit()

for i in range(x*2,10**18+1,x):
    if (i < y*2):
        continue
    elif (i%y != 0):
        print(i)
        quit()
print(-1)
### BUGGY CODE ###

#coding:utf-8
import bisect,math
import multiprocessing
A,B,Q=map(int,raw_input().split())
s=[]
t=[]
for a in range(A):
    s.append(input())
for a in range(B):
    t.append(input())
buf=[]    
def f(x):
    sl=bisect.bisect_left(s,x)-1
    sr=bisect.bisect_left(s,x)
    tl=bisect.bisect_left(t,x)-1
    tr=bisect.bisect_left(t,x)
    ans=float("inf")
    if sl!=-1 and tl!=-1:
        A=max(s[sl],t[tl])
        B=min(s[sl],t[tl])
        L=abs(x-A)+abs(A-B)
        ans=min(ans,L)
    if sl!=-1 and tr!=len(t):
        L=abs(x-s[sl])*2 + abs(t[tr]-x)        
        ans=min(ans,L)
        ans=min(ans,abs(x-s[sl])+abs(t[tr]-x)*2)
    if tl!=-1 and sr!=len(s):
        ans=min(ans,abs(x-t[tl])*2+abs(s[sr]-x))
        ans=min(ans,abs(x-t[tl])+abs(s[sr]-x)*2)
    if tr!=len(t) and sr!=len(s):
        A=min(s[sr],t[tr])
        B=max(s[sr],t[tr])
        L=abs(A-x)+abs(B-A)
        ans=min(ans,L)
    return str(ans)

I=[0]*Q
for i in xrange(Q):
    I[i]=input()
r=map(f,I)
print("\n".join(r))

### FIXED CODE ###

#coding:utf-8
import bisect,sys
A,B,Q=map(int,raw_input().split())
s=[0]*A
t=[0]*B
for i in range(A):    
    s[i]=int(sys.stdin.readline())
for i in range(B):
    t[i]=int(sys.stdin.readline())
buf=[]
def f(x):
    sl=bisect.bisect_left(s,x)-1
    sr=sl+1
    tl=bisect.bisect_left(t,x)-1
    tr=tl+1
    ans=float("inf")
    if sl!=-1 and tl!=-1:
        A=max(s[sl],t[tl])
        B=min(s[sl],t[tl])
        L=abs(x-A)+abs(A-B)
        ans=min(ans,L)
    if sl!=-1 and tr!=len(t):
        L=abs(x-s[sl])*2 + abs(t[tr]-x)        
        ans=min(ans,L)
        ans=min(ans,abs(x-s[sl])+abs(t[tr]-x)*2)
    if tl!=-1 and sr!=len(s):
        ans=min(ans,abs(x-t[tl])*2+abs(s[sr]-x))
        ans=min(ans,abs(x-t[tl])+abs(s[sr]-x)*2)
    if tr!=len(t) and sr!=len(s):
        A=min(s[sr],t[tr])
        B=max(s[sr],t[tr])
        L=abs(A-x)+abs(B-A)
        ans=min(ans,L)
    return str(ans)

I=[0]*Q
for i in xrange(Q):
    I[i]=int(sys.stdin.readline())
r=map(f,I)
print("\n".join(r))
### BUGGY CODE ###

import numpy as np
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))

def leng(n, f):
    ret = math.ceil(n / f) - 1
    if ret > 0:
        return math.ceil(n / f) - 1
    else:
        return 0

logs = np.array(A)
vleng = np.vectorize(leng)

#めぐる式二分探索
def is_ok(i):
    if sum(vleng(logs, i)) <= K:
        return True
    else:
        return False

def meguru_bisect(ng, ok):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

print(meguru_bisect(0, 10 ** 9 + 1))

### FIXED CODE ###

import numpy as np
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))

#めぐる式二分探索
def is_ok(i):
    su = 0
    for a in A:
        su += (a-1) // i
    if su <= K:
        return True
    else:
        return False

def meguru_bisect(ng, ok):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

print(meguru_bisect(0, max(A) + 1))
### BUGGY CODE ###

from collections import Counter
N=int(input())
A=Counter(input().split())
B=Counter(input().split())
C=Counter(input().split())
ans=0
for a_key,a_count in A.most_common():
    for b_key,b_count in B.most_common():
        for c_key,c_count in C.most_common():
            a_key,b_key,c_key=int(a_key),int(b_key),int(c_key)
            if a_key<b_key and b_key<c_key:
                ans+=a_count*b_count*c_count
print(ans)


### FIXED CODE ###

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

def lcm(x, y):
	if x > y:
		z = x
	else:
		z = y
	ans = 0
	while True:
		if z % x == 0 and z % y == 0:
			ans = z
			break
		z += 1
	return ans

def resolve():
	n = int(input())
	T = []
	for _ in range(n):
		T.append(int(input()))
	ans = 1
	for i in range(n):
		ans = lcm(ans, T[i])
	print(ans)
resolve()

### FIXED CODE ###

def gcd(a, b):
	"""Compute the greatest common divisor of a and b"""
	while b > 0:
		a, b = b, a % b
	return a

def lcm(a, b):
	"""Compute the lowest common multiple of a and b"""
	return a * b // gcd(a, b)

def resolve():
	n = int(input())
	T = []
	for _ in range(n):
		T.append(int(input()))
	ans = 1
	for i in range(n):
		ans = lcm(ans, T[i])
	print(int(ans))
resolve()
### BUGGY CODE ###

N = int(input())
AS = input().split()
for i in AS:
    i = int(i)
result = 0
result_f = 0
result_rf = 0
for j in range (1, N+1):
    result += abs(int(AS[j-1]) - 0 - j)
for j in range (1, N+1):
    result_f += abs(int(AS[j-1]) - 1 - j)
for j in range (1, N+1):
    result_rf += abs(int(AS[j-1]) - ( - 1) - j)
if result < result_f and result < result_rf:
    print(result)
else:
    old_list= [0]
    b = 1
    while(not b in old_list):
        counter = 0
        for j in range (1,N+1):
            counter += abs(int(AS[j-1]) - b - j)
        if counter <= result:
            old_list.append(b)
            b += 1
            result = counter
        else:
            old_list.append(b)
            continue
    result_1 = result
    b = -1
    while(not b in old_list):
        counter = 0
        for j in range (1,N+1):
            counter += abs(int(AS[j-1]) - b - j)
        if counter <= result:
            old_list.append(b)
            b -= 1
            result = counter
        else:
            old_list.append(b)
            continue
    result_2 = result
    print (min(result_1,result_2))

### FIXED CODE ###

N = int(input())
AS = input().split()
AS = [int(i) for i in AS]
BS = [int(AS[j-1] - j) for j in range(1,N+1)]
BS_s = BS.sort()
b = BS[N//2]
result_a = 0
result_b = 0
result_c = 0
for j in range (1, N+1):
    result_a += abs(int(AS[j-1]) - b - j)
for j in range (1, N+1):
    result_b += abs(int(AS[j-1]) - b - 1 - j)
for j in range (1, N+1):
    result_c += abs(int(AS[j-1]) - b + 1 - j)
print (int(min(result_a,result_b,result_c)))
### BUGGY CODE ###

import itertools
n,p = [int(x) for x in input().split()]
s = input()
if p!=2 and p!=5:
  r = [0]
  for i in range(n):
    a = int(s[i:])%p
    r.append(a)
  #print(r)
  r.sort()
  ans = 0
  for key, group in itertools.groupby(r):
    l = len(list(group))
    ans +=l*(l-1)//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)

### FIXED CODE ###

from collections import defaultdict,deque
import itertools
n,p = [int(x) for x in input().split()]
s = list(input())
if p!=2 and p!=5:
  r = defaultdict(int)
  a =[]
  s1 = s[::-1]
  for i in range(n):
    a.append((int(s1[i])%p*pow(10,i,p))%p)
  a = [0]+a[::-1]
  b = list(itertools.accumulate(a))
  for i in b:
    r[i%p]+=1
  ans = 0
  for i in r.values():
    ans+=(i*(i-1))//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)
### BUGGY CODE ###

from collections import Counter
n=int(input())
a=[int(A) for A in input().split()]
for k in range(1, n+1):
    ball = a[0:k-1] + a[k:]
    cnt=0
    for s in set(ball):
        bc = ball.count(s)
        if bc<2:
            continue
        cnt+= bc*(bc-1)/2
    print(int(cnt))


### FIXED CODE ###

from collections import Counter
n=int(input())
a=[int(A) for A in input().split()]

cnt=Counter(a)
s=sum([c*(c-1)//2 for c in cnt.values()])

for k in a:
    print(s-(cnt[k]-1))
### BUGGY CODE ###

import collections
import sys
input = sys.stdin.readline

def solve():
  n = int(input())
  query = []
  query2 = []
  ans = []
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query.append((a,b))
    query2.append(a)
    query2.append(b)
  c = list(int(i) for i in input().split())
  c = sorted(c,reverse =True)
  
  d = collections.Counter(query2)
  for i in range(len(d)):
    tmp = d.most_common()[i][0]
    #print(tmp)
    ans.insert(tmp-1,c[i])
  print(sum(c) +(-1)*max(c))
  #dの処理
  print(*ans)
  
solve()

### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline
import heapq
from array import array
def solve():
  n = int(input())

  query2 = collections.deque([])
  edge = [[] for _ in range(n)]
  ans = array('I', [ 0 for i in range(n)])
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query2.append(a)
    query2.append(b)
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
  c = list(int(i) for i in input().split())
  if n == 1:
    print(1)
    print(c[0])
    exit()
  c = collections.deque(sorted(c,reverse =True))
  d = collections.Counter(query2)
  d2 = d.most_common()
  bfs = []
  heapq.heappush(bfs,(-1*d2[0][1],d2[0][0]-1,-1))#回数,場所、親
  ct = 0
  visit = [False]*n
  while bfs:
    times,place,parent = heapq.heappop(bfs)
    if visit[place]:
      continue
    else:
      visit[place] = True

      for i in range(len(edge[place])):
        newp = edge[place][i]
        newtimes = len(edge[newp])
        if not visit[newp]:
          heapq.heappush(bfs,(-1*newtimes,newp,place))
      #print(place,parent,times)
      ans[place] = c.popleft()

      #print(c,place)

  print(sum(ans)-max(ans))
  print(*ans)
  
solve()
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int,input().split()))

mi = min(A)

def mak(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)

        return divisor_list
    
P = mak(mi)[::-1]
lenp = len(P)

Q = np.array(A)

an = 1
for i in range(lenp):
    R = Q % P[i]
    if any(R) == 0:
        an = P[i]
        break
    else:
        Q = R

print(an)

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int,input().split()))
flag = 0
#mi = min(A)
Q = np.array(A)
an = 1
def toku(Q):
    mi = min(Q)
    R1 = Q % mi
    if any(R1) == 0:
        flag = 1
        an = mi
        return flag, an, R1
    else:
        flag = 0
        an = 1
        ind = np.argmin(Q)
        R1[ind] = mi
        R = R1[R1!=0]
        return flag, an, R

while flag == 0:
    flag,an,PP = toku(Q)
    Q = PP

print(an)
### BUGGY CODE ###

N = int(input())
Alist = list(map(int, input().split()))

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

def gcd(list1) :
    global dol
    lngt = len(list1)
    tuple1 = tuple(list1)
    if lngt == 1 :
        return list1[0]
    elif tuple1 in dol.keys() :
        return dol[tuple1]
    else :
        rt = ea(gcd(list1[:lngt//2]), gcd(list1[lngt//2:]))
        dol[tuple1] = rt
        return rt

dol = {}
anslist = []
for n in range(N) :
    anslist.append(gcd(Alist[:n]+Alist[n+1:]))
print(max(anslist))

### FIXED CODE ###

from functools import lru_cache
n = int(input())
aa = list(map(int, input().split()))

@lru_cache(maxsize=10**9)
def gcd(a, b) :
    if b == 0 : return a
    elif a%b : return gcd(b, a%b)
    else : return b

l = [0]
r = [0]
for i in range(n) :
    l.append(gcd(l[-1], aa[i]))
    r.append(gcd(r[-1], aa[-i-1]))

m = [gcd(l[i],r[-i-2]) for i in range(n)]
print(max(m))
### BUGGY CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def main():
    N, K = NMI()
    edges = [NLI() for _ in range(N-1)]
    tree = make_adjlist_nond(N, edges)
    stack = deque()
    stack.append(1)
    ans = K
    seen = [False] * (N+1)
    while stack:
        now = stack.pop()
        seen[now] = True
        tmp = K - 2
        if now == 1:
            tmp += 1
        cnt = 0
        for i, goto in enumerate(tree[now]):
            if seen[goto]:
                cnt += 1
                continue
            ans *= (tmp - i + cnt) % MOD
            stack.append(goto)

    print(ans % MOD)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def main():
    N, K = NMI()
    edges = [NLI() for _ in range(N-1)]
    tree = make_adjlist_nond(N, edges)
    stack = deque()
    stack.append(1)
    ans = K
    seen = [False] * (N+1)
    while stack:
        now = stack.pop()
        seen[now] = True
        tmp = K - 2
        if now == 1:
            tmp += 1
        cnt = 0
        for i, goto in enumerate(tree[now]):
            if seen[goto]:
                cnt += 1
                continue
            ans = ans * (tmp - i + cnt) % MOD
            stack.append(goto)

    print(ans % MOD)


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

N, W = map(int, input().split())
ws = []
vs = []

for i in range(N):
	w, v = map(int, input().split())
	ws.append(w)
	vs.append(v)

w1 = ws[0]
s = 0

for i in range(N):
	ws[i] -= w1
	s += ws[i]

dp = [[[0]*(s+1) for i in range(N+1)] for k in range(N)]
for k in range(N):
	for i in range(1,N+1):
		for j in range(s+1):
			if j >= ws[i-1]:
				dp[k][i][j] = max(dp[k-1][i-1][j-ws[i-1]]+vs[i-1], dp[k][i-1][j])
			else:
				dp[k][i][j] = max(dp[k][i][j], dp[k][i-1][j])
			if j > 0:
				dp[k][i][j] = max(dp[k][i][j], dp[k][i][j-1])
ans = 0
for k in range(N):
	if W < (k+1)*w1:
		break
	ans = max(ans, dp[k][N][min(W-(k+1)*w1, s)])
print(ans)
from sys import stderr
print(dp, file=stderr)

### FIXED CODE ###

N, W = map(int, input().split())
ws = []
vs = []

for i in range(N):
	w, v = map(int, input().split())
	ws.append(w)
	vs.append(v)

w1 = ws[0]
s = 0

for i in range(N):
	ws[i] -= w1
	s += ws[i]

dp = [[[0]*(s+1) for i in range(N+1)] for k in range(N)]
for k in range(N):
	if (k+1)*w1 > W:
		break
	for i in range(1,N+1):
		for j in range(s+1):
			if j >= ws[i-1]:
				dp[k][i][j] = max(dp[k-1][i-1][j-ws[i-1]]+vs[i-1], dp[k][i-1][j])
			else:
				dp[k][i][j] = max(dp[k][i][j], dp[k][i-1][j])
			if j > 0:
				dp[k][i][j] = max(dp[k][i][j], dp[k][i][j-1])
ans = 0
for k in range(N):
	if W < (k+1)*w1:
		break
	ans = max(ans, dp[k][N][min(W-(k+1)*w1, s)])
print(ans)
from sys import stderr
print(dp, file=stderr)
### BUGGY CODE ###

from fractions import Fraction
N, K = map(int, input().split())
F = []

for i in range(1, N + 1):
    point = i
    j = 0
    while point < K:
        point *= 2
        j += 1
    F.append(Fraction(1, N) * (Fraction(1, 2) ** j))

print(float(sum(F)))

### FIXED CODE ###

from fractions import Fraction
N, K = map(int, input().split())
F = 0

for i in range(1, N + 1):
    point = i
    j = 0
    while point < K:
        point *= 2
        j += 1
    F += float((1/N) * ((1/2) ** j))

print(F)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for _ in range(M):
  b, c = map(int, input().split())
  A.extend([c] * b)
A = sorted(A, reverse=True)
print(sum(A[:N]))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for _ in range(M):
  BC.append(list(map(int, input().split())))
BC = sorted(BC, key=lambda x:x[1],reverse=True)  
for b, c in BC:
  A.extend([c] * b)
  if len(A)>=2*N:
    break
A = sorted(A, reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

def main():
    N = int(input())
    a = [0 for i in range(N)]
    for i in range(N):
        a[i] = int(input())
    d = [1]
    ans = 0
    for i in range(N):
        if a[d[i]-1] == 2:
            ans += 1
            break
        elif a[d[i]-1] in d:
            ans = -1
            break
        else:
            d.append(a[d[i]-1])
            ans += 1
    print(ans)
main()


### FIXED CODE ###

def main():
    N = int(input())
    a = [0 for i in range(N)]
    for i in range(N):
        a[i] = int(input())
    now = 1
    for i in range(N):
        if a[now - 1] == 2:
            break
        elif i == N - 1:
            i = -2
        else:
            now = a[now - 1]
        #print('{}: {}'.format(i, now))
    print(i + 1)
main()
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


H, W, D = map(int, input().split())

MAP  = {}
COST = {}

for i in range(H):
    for j, l in enumerate(list(map(int, input().split()))):
        MAP[l] = (i, j)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    keys = COST.keys()
    while L != R:
        way = '%s,%s' % (L, L+D)
        if way in keys:
            pass
        else:
            COST[way] = abs(MAP[L][0] - MAP[L+D][0]) + abs(MAP[L][1] - MAP[L+D][1])
            COST.keys()
        cost += COST[way]
        L    += D
    print(cost)


### FIXED CODE ###

# speed-test
# https://abc089.contest.atcoder.jp/submissions/2206669

h,w,d = map(int,input().split())
 
dic = {}
for i in range(h):
    a = input().split()
    for j in range(w):
        dic[int(a[j])] = (i+1,j+1)
        
q = int(input())
c = [0]*(h*w+1)
for i in range(d+1,h*w+1):
    pi,pj = dic[i]; qi,qj = dic[i-d]
    c[i] = c[i-d] + abs(pi-qi) + abs(pj-qj)
    
for i in range(q):
    l,r = map(int,input().split())
    print(c[r]-c[l])
### BUGGY CODE ###

s = input() # これを繰り返しまくる
t = input() # これを探す

# 判定
s_set = set(s)
s_len = len(s)

if all((t_ in s_set) for t_ in t):
    ans = 0

    # loop
    ss = s

    for t_ in t:
        find_plus_one = ss.find(t_) + 1
        ss = ss[find_plus_one:]
        if len(ss) < s_len:
            ss += s
        ans += find_plus_one
    print(ans)
else:
    print(-1)


### FIXED CODE ###

s = input() # これを繰り返しまくる
t = input() # これを探す

# 判定
s_set = set(s)
s_len = len(s)

if all((t_ in s_set) for t_ in t):
    ans = 0
    ss = s + s
    found_index_old = -1

    for t_ in t:
        found_index = ss.find(t_, found_index_old + 1)
        # print(ss, found_index_old + 1, found_index, found_index + 1 - (found_index_old + 1))
        ans += found_index - found_index_old # found_index + 1 - (found_index_old + 1)
        found_index_old = found_index % s_len
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

from collections import Counter

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

import numpy as np
for _ in range(Q):
    B,C=map(int,input().split())
    A[C]+=A[B]
    A[B]=0
    print(sum(np.array(list(A.keys())) * np.array(list(A.values()))))

### FIXED CODE ###

from collections import Counter

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
init=sum(A)
A=Counter(A)

for _ in range(Q):
    B,C=map(int,input().split())
    A[C]+=A[B]
    init=init-(B*A[B])+(C*A[B])
    print(init)
    A[B]=0
### BUGGY CODE ###

H, W, D = map(int, input().split())
C = {}
for i in range(H):
    A = [int(i) for i in input().split()]
    for j in range(W):
        C[A[j]] = (i, j)

memo = {}
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    if (l, r) in memo:
        print(memo[(l, r)])
    else:
        MP, now = 0, l
        while now < r:
            nowx, nowy = C[now]
            nextx, nexty = C[now + D]
            MP += abs(nowx-nextx) + abs(nowy-nexty)
            now += D
        print(MP)
        memo[(l, r)] = MP

### FIXED CODE ###

H, W, D = map(int, input().split())
C = {}
for i in range(H):
    A = [int(i) for i in input().split()]
    for j in range(W):
        C[A[j]] = (i, j)

MaxD = D * ((H*W)//D)
Cost = [[0] for i in range(D)]
for i in range(D):
    now = (D if i == 0 else i)
    nowx, nowy = C[now]
    while now + D <= H * W:
        nextx, nexty = C[now+D]
        MP = abs(nowx - nextx) + abs(nowy - nexty)
        Cost[i].append(Cost[i][-1] + MP)
        now += D
        nowx, nowy = nextx, nexty

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    mod = l % D
    if mod == 0:
        print(Cost[mod][r//D - 1] - Cost[mod][l//D - 1])
    else:
        print(Cost[mod][r//D] - Cost[mod][l//D])