Harryxun/stf_run huggingface dataset:
from itertools import permutations

N, M, R = map(int, input().split())
r = map(int, input().split())
 
INF = float("inf")
d = [[INF] * (N + 1) for _ in range(N + 1)]
for n in range(1, N + 1):
    d[n][n] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    d[a][b] = c
    d[b][a] = c

for k in range(1, N + 1):
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]

ans = INF
for p in permutations(r):
    cnt = 0
    for i in range(len(p) - 1):
        p1, p2 = p[i:i + 2]
        cnt += d[p1][p2]
    ans = min(cnt, ans)

print(ans)


### FIXED CODE ###

N = int(input())
n10 = N//10
n1 = N%10
if n10 == 9 or n1 == 9:
    print("Yes")
else:
    print("No")
K = int(input())
L = 0
if K % 7 == 0:
  L = 9*K//L
else:
  L = 9*K
  
t = 1
ans = -1
for i in range(1,L,1):
  t = t*10
  if t % L == 1:
    ans = i
    break
  t = t % L
print(ans)

### FIXED CODE ###

K = int(input())

if K%7 == 0:
  L = 9*K/7
else:
  L = 9*K
s = 1

for i in range(1, 9*(10**6)+1):
  s = s*10%L
  if s == 1:
    print(i)
    exit()

print("-1")
import numpy as np


def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort(reverse=True)
    A = np.array(list(map(int, input().split())))
    limit = 10 ** 18

    if np.any(A == 0):
        print(0)
    elif np.any(A > limit):
        print(-1)
    else:
        ans = 1

        for i in range(n):
            ans *= A[i]
            if ans > limit:
                print(-1)
                exit()

        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    limit = 10 ** 18
    #print(A)

    if A[-1] == 0:
        print(0)
    elif A[0] > limit:
        print(-1)
    else:
        ans = A[0]
        for i in range(1, n):
            ans *= A[i]
            if ans > limit:
                print(-1)
                exit()

        print(ans)


if __name__ == "__main__":
    main()
S_list = list(map(int,input().split()))
 
r, g, b = S_list
if (ｒ ＋ g + b) % 4 == 0 :
    result = "YES"
else:
    result = "NO"
print(result)

### FIXED CODE ###

S_list = list(map(int,input().split()))

r, g, b = S_list[0], S_list[1], S_list[2]
if (100 * r + 10 * g + b) % 4 == 0 :
    result = "YES"
else:
    result = "NO"
print(result)
n=int(input())
a=map(int,input().split()
print(max(a)-min(a))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
print(max(a)-min(a))
from sys import stdin, stdout  

N,X,Y = [int(c) for c in input().split()]


res=[0]*N        
for x in range(0,N):
    for y in range(0,N):
        #print(x,y,abs(x-y),abs(abs(X-1-x)+abs(Y-1-y)+1),min(abs(x-y),abs(abs(X-1-x)+abs(Y-1-y)+1)))
        r=min(abs(x-y),abs(abs(X-1-x)+abs(Y-1-y)+1))
        res[r]=res[r]+1
        if(x>y):
            res[r]=res[r]-1


for i in range(1,N):
    print(res[i])


### FIXED CODE ###

import sys

for S in sys.stdin:
    if(S[2]==S[3] and S[4]==S[5]):
        print("Yes")
    else:
        print ("No")
import math
A, B, N = map(int, input().split())
# xはN以下
# int(A*x/B) - A*int(x/B)の最大値を求めたい


compute_range = list(range(0, math.ceil(N / B) + 1))
# print(compute_range)


def h(x):
    return int(int((A * x) / B) - A * int(x / B))


max_num = max(h(N), h(N % B))
print(max_num)


### FIXED CODE ###


A, B, N = map(int, input().split())
# xはN以下
# int(A*x/B) - A*int(x/B)の最大値を求めたい


# print(compute_range)


def h(x):
    return int(int((A * x) / B) - A * int(x / B))


max_num = h(min(B - 1, N))
print(max_num)
#include "bits/stdc++.h"

using namespace std;

int main(){
  int A, B, T;
  cin >> A >> B >> T;

  cout << T/A*B << endl;
}

### FIXED CODE ###

A, B, T = map(int,input().split())
T += 0.5
print(int(T//A*B))
N,A,B = map(int, input().split())
ans = ""
while len(ans) <= N:
    ans += "b"*A + "r"*B
print(ans)
print(ans[:N].count("b"))

### FIXED CODE ###

N,A,B = map(int, input().split())
temp = N//(A+B)
N-=(A+B)*temp
ans = temp * A
ans += min(N,A)
print(ans)
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
dp = [INF]*(n**2)
dp[0] = 0
for i in range(m):
    val,b = inpl()
    c = inpl()
    key = 0
    for j in c:
        key += 2**(j-1)
    for _ in range(n**2):
        dp[_|key] = min(dp[_|key], dp[_]+val)
        
res = dp[-1]
print(res if res != INF else -1)
# pprint.pprint(dp)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
dp = [INF]*(2**n)
dp[0] = 0
for i in range(m):
    val,b = inpl()
    c = inpl()
    key = 0
    for j in c:
        key += 2**(j-1)
    for _ in range(2**n):
        dp[_|key] = min(dp[_|key], dp[_]+val)
        
res = dp[-1]
print(res if res != INF else -1)
if __name__ == "__main__":
    abc = input().replace("　", " ").split(" ")
    abc = [int(x) for x in abc].sort(reverse=True)
    k = int(input())
    print(abc[0] * (2**k)

### FIXED CODE ###

if __name__ == "__main__":
    abc = input().replace("　", " ").split(" ")
    abc = [int(x) for x in abc]
    abc.sort(reverse=True)
    k = int(input())
    print(abc[0] * (2**k) + abc[1] + abc[2])
a = int(input())
b = int(input())
 
if a >= 13:
  print(b)
elif a >= 6:
  print((int)b/2)
else:
  print(0)

### FIXED CODE ###

a,b = map(int, input().split())
 
ans=0
if a <= 5:
	ans = 0
elif a >= 6 and a<=12:
	ans = b/2
else:
	ans = b
 
print(int(ans))
N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]
dp=[0]*N
id=0
p=10**9+7
point=a[id]
for i in range(N):
    if i==0:
        if a[id]!=(i+1):
            dp[i]=1
        else:
            id=id+1
    elif i==1:
        if a[id]!=(i+1):
            dp[i]=dp[i-1]+1
        else:
            id=id+1
    else:
        dp[i]=dp[i-1]+dp[i-2]
        if a[id]==i+1:
            dp[i]=0
            if id<len(a)-1:
                id=id+1
print(dp[N-1]%p)





### FIXED CODE ###

N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]
dp=[0]*N
id=0
p=10**9+7
id=0
for i in range(N):
    if (i==0):
        dp[i]=1
    elif (i==1):
        dp[i]=dp[i-1]+1
    else:
        dp[i]=dp[i-1]+dp[i-2]
    if len(a)>0:
        if a[id]==i+1:
            dp[i]=0
            if id<len(a)-1:
                id=id+1
print(dp[N-1]%p)
a, b, c = int(input().split())
print(c - (a - b))


### FIXED CODE ###

a, b, c = map(int, input().split())
if c > (a - b):
	print(c - (a - b))
else:
    print(0)
t = int(input())
for i in range(t):
    able = "Yes"
    a,b,c,d = map(int, input().split())
    if a - b < 0:
        able = "No"
    else:
        x = c+(a-c)%b
        if x <= c:
            x+=d
        for i in range(1000):
            x-=b
            if x >= 0:
                if x <= c:
                    x+=d
            else:
                able = "No"
                break
    print(able)

### FIXED CODE ###

n = int(input())
a= list(input().split())
res = 0
for i in range(n-1):
    if a[i] == a[i+1]:
        a[i+1]=10001
        res +=1
print(res)
N = map(int,input())
blue = []
red = []
for i in range(N):
    blue.append(input())
M = map(int,input())
for i in range(M):
    red.append(input())
blue_list = Counter(blue)
red_list = Counter(red)
b = max(blue_list)
c=min(red_list)
print(blue_list[b] - red_list[c])

### FIXED CODE ###

n = int(input())
s = list()
counter = 0

for i in range(n):
    s.append(input())
    
m = int(input())
t = list()

for i in range(m):
    t.append(input())
    
for word in s:
    counter = max(counter,s.count(word) - t.count(word))
    
print(counter)
N, K = map(int, input().split())
ashi = list(map(int, input().split()))

if N<=K:    
    print(abs(ashi[N]-ashi[0]))
    exit()

arr = [0]*N
for i in range(1,K+1,1):
    arr[i] = abs(ashi[i]-ashi[0])


for i in range(K+1,N,1):
    x = arr[i-1]+abs(ashi[i]-ashi[i-1])
    for j in range(1,K+1,1):
        if arr[i-j]+abs(ashi[i]-ashi[i-j]) < x:
            x=arr[i-j]+abs(ashi[i]-ashi[i-j])
    arr[i] = x

print(arr[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
ashi = list(map(int, input().split()))
 
if N<=K:    
    print(abs(ashi[-1]-ashi[0]))
    exit()
 
arr = [0]*N
for i in range(1,K+1,1):
    arr[i] = abs(ashi[i]-ashi[0])
 
 
for i in range(K+1,N,1):
    x = arr[i-1]+abs(ashi[i]-ashi[i-1])
    for j in range(1,K+1,1):
        if arr[i-j]+abs(ashi[i]-ashi[i-j]) < x:
            x=arr[i-j]+abs(ashi[i]-ashi[i-j])
    arr[i] = x
 
print(arr[-1])
def gcd_(a, b):
    if a < b:  a, b = b, a
    if b == 0:  return a
    return gcd_(b, a % b)

def gcd_bl(A):

    left = [0 for _ in range(N + 1)]
    right = [0 for _ in range(N + 1)]
    ans = [0 for _ in range(N)]

    left[1] = A[0]
    for i in range(1, N):
        left[i + 1] = gcd_(left[i], A[i])
    right[-1 - 1] = A[-1]
    for i in range(1, N):
        right[-1 - i - 1] = gcd_(right[-1 - i], A[-1 - i])
    for i in range(N):
        ans[i] = gcd_(left[i], right[i + 1])
        
    return ans

def cin():
    in_ = list(map(int,input().split()))
    if len(in_) == 1:  return in_[0]
    else:  return in_

def solve():
    
    g = gcd_bl(A)

    for i in range(N):
        if A[i] == K:  return 1
        elif A[i] > K:
            temp = (K - A[i]) / g[i]
            if temp == int(temp):
                return 1

    return 0

N, K = cin()
A = cin()

ret = solve()
if ret:  print("POSSIBLE")
else:  print("IMPOSSIBLE")

### FIXED CODE ###

def gcd_(a, b):
    if a < b:  a, b = b, a
    if b == 0:  return a
    return gcd_(b, a % b)

def gcd_bl(A):

    left = [0 for _ in range(N + 1)]
    right = [0 for _ in range(N + 1)]
    ans = [0 for _ in range(N)]

    left[1] = A[0]
    for i in range(1, N):  left[i + 1] = gcd_(left[i], A[i])
    right[-1 - 1] = A[-1]
    for i in range(1, N):  right[-1 - i - 1] = gcd_(right[-1 - i], A[-1 - i])
    for i in range(N):  ans[i] = gcd_(left[i], right[i + 1])
        
    return ans

def cin():
    in_ = list(map(int,input().split()))
    if len(in_) == 1:  return in_[0]
    else:  return in_

def solve():   
    if N == 1:  return A == K    
    g = gcd_bl(A)
    for i in range(N):
        if A[i] == K:  return 1
        elif A[i] > K:
            temp = (K - A[i]) / g[i]
            if temp == int(temp):  return 1
    return 0

N, K = cin()
A = cin()
ret = solve()
if ret:  print("POSSIBLE")
else:  print("IMPOSSIBLE")
import operator as op
from functools import reduce

N, K = map(int, input().split())
num_lis = list(map(int, input().split()))
num_lis = sorted(num_lis)

#組み合わせ
def combi(N,K):
  multi = op.mul
  numer = reduce(multi, range(N, N-K, -1),1)
  denom = reduce(multi, range(1,K+1), 1)
  combi = int(numer/denom)
  return combi

ans = 0
#max
for i in range(K-1,N):
  ans += num_lis[i]*combi(i, K-1)

#min
for j in range(N-K,-1,-1):
  ans -= num_lis[j]*combi(N-j-1,K-1)
  
ans %= 10**9+7
print(ans)

### FIXED CODE ###

# フェルマーの小定理
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
m = 1000000007
 
fac = [0] * (N + 1)
fac[0] = 1
for i in range(N):
    fac[i + 1] = fac[i] * (i + 1) % m
 
 
def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], m - 2, m) * pow(fac[k], m - 2, m) % m
 
 
A.sort(reverse=True)
maxX = 0
for i in range(N - K + 1):
    maxX += A[i] * mcomb(N - (i + 1), K - 1)
    maxX %= m

A.sort()
minX = 0
for i in range(N - K + 1):
    minX += A[i] * mcomb(N - (i + 1), K - 1)
    minX %= m

print((maxX - minX) % m)
S = 0
for i in range(N)
   S += i
print(N)

### FIXED CODE ###

n = int(input())
N = int(n*(n+1)/2)
print(N)
N=int(input())
LA=[0]*N
LB=[0]*N
for i in range(N):
    A,B=[int(x) for x in input().split()]
    LA[i]=A
    LB[i]=B

PA=0
PB=0

LD=[0]*N
for i in range(N):
    LD[i]=LA[i]+LB[i]


SLD=sorted(LD)
SLD.reverse()
if N%2==0:
    for i in range(0,N,2):
        PA+=LA[LD.index(SLD[i])]
        PB+=LB[LD.index(SLD[i+1])]
else:
    for i in range(0,N-1,2):
        PA+=LA[LD.index(SLD[i])]
        PB+=LB[LD.index(SLD[i+1])]

    PA+=LA[LD.index(SLD[N-1])]

print(PA-PB)


### FIXED CODE ###

N,A,B=input().split()
N=int(N)
A=int(A)
B=int(B)
if A+B-N<0:
    print(str(min(A,B))+" 0")
else:
    print(str(min(A,B))+" "+str(A+B-N))
import math

r = 10000000
sqrt = int(math.sqrt(r))
p = [1 for i in range(r)]
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

count = 0
n = int(raw_input())
for i in range(n):
    m = int(raw_input())
    if p[m-1]:
        count += 1
    except:
        break
print count

### FIXED CODE ###

def isPrime(p):
	if p == 2: return 1
	if p < 2 or p&1 == 0: return 0
	return 1 if pow(2,p-1,p) == 1 else 0
	
n = int(raw_input())
print sum(isPrime(int(raw_input())) for i in range(n))
n = input()
sort_list = list()

for i in range(0,n):
    sort_list.append(input())

for i in range(1,n):
    
    for j in range(0,n):
        print(sort_list[j])
        if j is not n - 1:
            print(" ")
        else:
            print("\n")
    
    tmp = sort_list[i]
    j = i - 1
    while j >= 0 and sort_list[i] > v:
        sort_list[j+1] = sort_list[j]
        j = j - 1
    sort_list[j+1] = v




### FIXED CODE ###

import sys

n = input()
sort_list = list()

sort_list = map(int, raw_input().split())

for i in range(0,n):
    
    
    tmp = sort_list[i]
    j = i - 1
    while j >= 0 and sort_list[j] > tmp:
        sort_list[j+1] = sort_list[j]
        j = j - 1

    sort_list[j+1] = tmp


    for k in range(0,n):
        sys.stdout.write(str(sort_list[k]))
        if k is not n - 1:
            sys.stdout.write(" ")
        elif i is not n - 1:
            sys.stdout.write("\n")
            
print("")
import math

n,m,l=map(int,raw_raw_input().split())
INF=(10**9)+1

g=[]
f=[]
for i in xrange(n):
    g.append([INF]*(n))
    f.append([INF]*(n))

for i in xrange(len(g)):
    for j in xrange(len(g)):
        if i==j:
            g[i][j]=0
            f[i][j]=0

for i in xrange(m):
    a,b,c=map(int,raw_input().split())
    g[a-1][b-1]=c
    g[b-1][a-1]=c
    f[a-1][b-1]=c
    f[b-1][a-1]=c

for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])
            f[i][j]=min(f[i][j],f[i][k]+f[k][j])

for i in xrange(n):
    for j in xrange(n):
        if f[i][j]<=l:
            g[i][j]=1
        else:
            g[i][j]=INF
        if i==j:
            g[i][j]=0

for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])

q=int(raw_input())
for i in xrange(q):
    s,t=map(int,raw_input().split())
    u=g[s-1][t-1]

    if u>=INF:
        print (-1)
    else:
        print (u-1)

### FIXED CODE ###

n,m,l=map(int,raw_input().split())
INF=(10**9)+1

g=[]
f=[]
for i in xrange(n):
    g.append([INF]*(n))
    f.append([INF]*(n))

for i in xrange(len(g)):
    for j in xrange(len(g)):
        if i==j:
            g[i][j]=0
            f[i][j]=0

for i in xrange(m):
    a,b,c=map(int,raw_input().split())
    g[a-1][b-1]=c
    g[b-1][a-1]=c
    f[a-1][b-1]=c
    f[b-1][a-1]=c

for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])
            f[i][j]=min(f[i][j],f[i][k]+f[k][j])

for i in xrange(n):
    for j in xrange(n):
        if f[i][j]<=l:
            g[i][j]=1
        else:
            g[i][j]=INF
        if i==j:
            g[i][j]=0

for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])

q=int(raw_input())
for i in xrange(q):
    s,t=map(int,raw_input().split())
    u=g[s-1][t-1]

    if u>=INF:
        print (-1)
    else:
        print (u-1)
def func(D):
  comb = 0
  for item in D:
    if item[0]==item[1]:
      comb+=1
    else:
      comb=0
    
    if comb==3:
      return "Yes"  
  return "No"

if __name__ == "__main__":
    N = int(input())
    D = [map(int, input().split()) for _ in range(N)]
    print(func(D))

### FIXED CODE ###

def func(D):
  comb = 0
  for item in D:
    if item[0]==item[1]:
      comb+=1
    else:
      comb=0
    
    if comb==3:
      return "Yes"  
  return "No"

if __name__ == "__main__":
    N = int(input())
    D = [list(map(int, input().split())) for _ in range(N)]
    print(func(D))
import heapq
import collections
N =  int(input())
nums = list(map(int,input().split(" ")))
keta = [0] * 60
# ある桁の1の出現回数
# keta[k] → 2**k の桁
jijou = [1]
MOD = 10 ** 9 + 7
for i in range(60):
    temp = jijou[i] * 2
    temp%= MOD
    jijou.append(temp)

for num in nums:
    s = format(num,"b")
    l = len(s)
    for i in range(0,l):
        keta[i] += int(s[l - i - 1 ])
ans = 0
for j,num in  enumerate(nums[:-1]):
    s = format(num, "b")
    l = len(s)
    for i in range(0,61): #i →  2 ** i 乗 桁目に対応
        if l <= i:
            ans += (keta[i] * jijou[i]) % MOD
        else:
            if s[l - i - 1 ] == "0":
                ans += (keta[i] * jijou[i]) % MOD
            else:
#              (N - j + 1) - (keta[i] + 1 ) → 0が経っているところの個数
                ans += (( (N - j + 1) - (keta[i] + 1)  ) * ( jijou[i]) ) % MOD
                keta[i] -= 1
        ans %= MOD
    ans %= MOD


print(ans)

### FIXED CODE ###


import heapq
import collections
import math
import sys
N =  int(input())
input = sys.stdin.readline
# num = a << b →  a  * (2 ** b)
# 1 << i → i桁目のマスク
# mask = 1 << i
# num = a << b
# num & mask


#
nums = list(map(int,input().split(" ")))
keta = [0] * 62
# ある桁の1の出現回数
# keta[k] → 2**k の桁
jijou = []
MOD = 10 ** 9 + 7


for num in nums:
    s = format(num,"b")
    l = len(s)

    for i in range(0,l):
        if s[l - i - 1 ] == "1":
            keta[i] += 1

ans = 0
temp = 1
for i in range(62):

    ans += ( keta[i] * (N - keta[i])) * temp
    ans %= MOD
    temp *= 2
    temp %= MOD
print(ans)
n=int(input())
h=list(map(int,input().split()))
max_n=10**5
DP=[-1 for i in range(n)] #計算のメモ、-1は未計算
def dp(i): #足場i+1までにかかる最小のコスト
    if DP[i]!=-1: #メモがあれば使う
        return DP[i]
    if i==0: #初期条件が足場1より0
        return 0
    elif i==1: #足場2へは1から2への一通りしかない
        return abs(h[0]-h[1])
    res1=abs(h[i-1]-h[i])+dp(i-1) #1つジャンプして足場i+1につくときの最小コスト
    res2=abs(h[i-2]-h[i])+dp(i-2) #2つジャンプして足場i+1につくときの最小コスト
    DP[i]=min(res1,res2) #二つのうち小さいほうが足場i+1につく最小コスト
    return DP[i]

print(dp(n-1))

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
max_n=10**5

dp=[-1]*max_n #dp[i-1]が足場iまでのコストの最小値
dp[0]=0
dp[1]=abs(h[0]-h[1])
for i in range(2,n):
    res1=dp[i-1]+abs(h[i]-h[i-1]) #1ジャンプして足場iの時の最小値
    res2=dp[i-2]+abs(h[i]-h[i-2]) #2ジャンプして足場iの時の最小値
    dp[i]=min(res1,res2)

print(dp[n-1])
list = [int(input(''))for i in range(3)]

for i in range(3):
    if list[i] == 1:
        print(9, end="")
    elif list[i] == 9:
        print(9, end="")

print()


### FIXED CODE ###

nyu = input()
list(nyu)

for i in nyu:
    if i == "1":
        print("9", end="")
    elif  i == "9":
        print("1", end="")
print()
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int,input().split())) for _ in range(Q)]

data = {A[i][j]:j + i * W for i in range(H) for j in range(W)}
move = [0] * (H*W + 1)

for i in range(1+D,H*W+1):
    a,b = data[i],data[i-D]
    move[i] = abs(a%W - b % W) + abs(a//W - b//W)

memo = [[None] * (H*W) for _ in range(H*W)]
for l,r in LR:
    if l == r:
        print(0)
        continue
    if memo[l][r]:
        print(memo[l][r])
    else:
        t = sum(move[l+D:r+1:D])
        memo[l][r] = t
        print(t)
    

### FIXED CODE ###

H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int,input().split())) for _ in range(Q)]

data = {A[i][j]:j + i * W for i in range(H) for j in range(W)}

memo = [0] * (H*W+1)
for i in range(1+D,H*W+1):
    a,b = data[i],data[i-D]
    memo[i] = memo[i-D] + abs(a%W - b % W) + abs(a//W - b//W)

for l,r in LR:
    if l == r:
        print(0)
        continue
    print(memo[r] - memo[l])
N = int(input())
arr = list(map(int, input().split()))
memo = [0]*(max(arr)*2+1000)
ans = 0
for i in range(N):
    if (i+1)-arr[i] >= 0:
        ans += memo[(i+1)-arr[i]]
    if (i+1)+arr[i] > 0:
        memo[(i+1)+arr[i]] += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict
d = defaultdict(int)
N = int(input())
arr = list(map(int, input().split()))
ans = 0
for i in range(N):
    ans += d[(i+1)-arr[i]]
    d[(i+1)+arr[i]] += 1
print(ans)
a, b, c = map(int, input().solit())
answer = c - (a- b)
print(answer)

### FIXED CODE ###

a, b, c = map(int, input().split())
capacity = a - b
if c > capacity:
    answer = c - capacity
else:
    answer = 0
    
print(answer)
s = input()
N = len(s)
K = int(input())
word = []
for i in range(N):
    for j in range(i, N):
        word.append(s[i:j+1])

word.sort()
print(word[K])

### FIXED CODE ###

s = input()
N = len(s)
K = int(input())
word = []
for i in range(N):
    for j in range(i, min(N, i+K)):
        word.append(s[i:j+1])

word.sort()
word_set = list(set(word))
word_set.sort()
print(word_set[K-1])
#from collections import *
from itertools import *
#from bisect import *
#from heapq import *
#import copy
#N=int(input())
#X,Y=map(int,input().split())
#S=list(map(int,input().split()))
#S=[list(map(int,input().split())) for i in range(N)]
#import math

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
Zlst=set([i for i in range(N)])
count=-1
for lst in combinations(range(N),N//2+N%2):
    odds=[[A[i],i] if i%2==0 else [B[i],i] for i in lst]
    even=[[B[i],i] if i%2==0 else [A[i],i] for i in list(Zlst-set(lst))]
    oddsst=sorted(odds,key=lambda  x:x[0])
    evenst=sorted(even,key=lambda  x:x[0])

    temp=oddsst[0][0]
    lst=[oddsst[0][1]]
    for i in range(1,N):
        if i%2==1:
            ntemp=evenst[i//2]
        else:
            ntemp=oddsst[i//2]
        if temp>ntemp[0]:
            flag=0
            break
        else:
            flag=1
            temp=ntemp[0]
            lst.append(ntemp[1])

    if flag:
        if count==-1:
            count=10**10
        tempcount=0
        while flag:
            flag=0
            for i in range(len(lst)-1):
                if lst[i]>lst[i+1]:
                    lst[i],lst[i+1]=lst[i+1],lst[i]
                    tempcount+=1
                    flag=1
        count=min(count,tempcount)


print(count)


### FIXED CODE ###

#from collections import *
from itertools import *
#from bisect import *
#from heapq import *
#import copy
#N=int(input())
#X,Y=map(int,input().split())
#S=list(map(int,input().split()))
#S=[list(map(int,input().split())) for i in range(N)]
#import math

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
Zlst=set([i for i in range(N)])
if N==1:
    print(0)
    exit()
count=-1
for lst in combinations(range(N),N//2+N%2):
    odds=[[A[i],i] if i%2==0 else [B[i],i] for i in lst]
    even=[[B[i],i] if i%2==0 else [A[i],i] for i in list(Zlst-set(lst))]
    oddsst=sorted(odds,key=lambda  x:x[0])
    evenst=sorted(even,key=lambda  x:x[0])

    temp=oddsst[0][0]
    lst=[oddsst[0][1]]
    for i in range(1,N):
        if i%2==1:
            ntemp=evenst[i//2]
        else:
            ntemp=oddsst[i//2]
        if temp>ntemp[0]:
            flag=0
            break
        else:
            flag=1
            temp=ntemp[0]
            lst.append(ntemp[1])

    if flag:
        if count==-1:
            count=10**10
        tempcount=0
        while flag:
            flag=0
            for i in range(len(lst)-1):
                if lst[i]>lst[i+1]:
                    lst[i],lst[i+1]=lst[i+1],lst[i]
                    tempcount+=1
                    flag=1
        count=min(count,tempcount)


print(count)