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

N = int(input())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

AB = [(a, b) for a, b in zip(A, B) if a < b]
dp = [[N] * (N + 1) for _ in range(len(AB)+1)]
for i, (a, b) in enumerate(AB):
    for w in range(N+1):
        if w >= a:
            dp[i+1][w] = max(dp[i][w], dp[i+1][w-a] + b-a)
        else:
            dp[i+1][w] = dp[i][w]

M = max(dp[-1])

BA = [(a, b) for a, b in zip(A, B) if a > b]
dp = [[M] * (M + 1) for _ in range(len(BA)+1)]
for i, (a, b) in enumerate(BA):
    for w in range(M+1):
        if w >= b:
            dp[i+1][w] = max(dp[i][w], dp[i+1][w-b] + a-b)
        else:
            dp[i+1][w] = dp[i][w]
print(max(dp[-1]))


### FIXED CODE ###

import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
N = int(input())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

dp = [0] * (N+1)
for a, b in ((a, b) for a, b in zip(A, B) if a < b):
    for w in range(a, N+1):
        dp[w] = max(dp[w], dp[w-a] + b-a)

M = max(dp) + N
dp = [0] * (M+1)
for a, b in ((a, b) for a, b in zip(A, B) if a > b):
    for w in range(b, M+1):
        dp[w] = max(dp[w], dp[w-b] + a-b)

print(max(dp) + M)
### BUGGY CODE ###

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



for j in range(M):
    idx = L.index(max(L))
    L[idx] = L[idx]//  2
    
print(sum(L))

### FIXED CODE ###

import heapq

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

q=[]
for l in L:
    heapq.heappush(q, -l)

for _ in range(M):
    p = -heapq.heappop(q)//2
    heapq.heappush(q, -p)

print(-sum(q))
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
  s.append(''.join(sorted(input())))
a = []

while len(s) > 0:
  l = s[0]
  a.append(s.count(l))
  s = [ss for ss in s if ss != l]

ans = 0
for i in range(len(a)):
  ans += a[i]*(a[i]-1)//2
print(ans)

### FIXED CODE ###

n = int(input())
s = ['']*n
for i in range(n):
  s[i] = (''.join(sorted(input())))
s.sort()

i=0
c=1
ans = 0
while i < n-1:
  while i+c < n and s[i] == s[i+c]:
    c += 1
  else:
    ans += c*(c-1)//2
    i += c
    c = 1

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

n = int(input())
a = list(map(int, input().split()))
ans = 1

for i in range(n):
  ans = ans*a[i]

if ans > 10**18:
  print(-1)
else:
  print(ans)
  

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1

if 0 in a:
  print(0)
  exit()

for i in range(n):
  ans = ans*a[i]
  if ans > 10**18:
      print(-1)
      exit()

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

def main():
    K = int(input())
    first = 7 % K
    curr = first
    S = set()
    ans = 1
    while first not in S:
        if curr == 0:
            print(ans)
            return
        curr = (curr*10+7) % K
        S.add(curr)
        ans += 1
    print(-1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    K = int(input())
    curr = 7 % K
    for i in range(1, K+1):
        if curr == 0:
            print(i)
            return
        curr = (curr*10+7) % K
    else:
        print(-1)


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

import bisect
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
for _ in range(m):
    b, c = map(int, input().split())
    k = bisect.bisect_right(a, c)
    a[:min(k, b)] = [c] * min(k, b)
    a.sort()
print(sum(a))

### FIXED CODE ###

import collections
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
k = collections.Counter(a)
for _ in range(m):
    b, c = map(int, input().split())
    k[c] += b
ans = 0
count = 0
for key in list(reversed(sorted(list(k.keys())))):
    ans += (min(k[key], n - count)) * key
    count += min(k[key], n - count)
    if count == n:
        break
print(ans)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
H = [int(h) for h in input().split()]
H = np.array(H, dtype=np.int64)

dp = np.array([0]*(N+1), dtype=np.int64)
k = np.array([i for i in range(1, K+1)])

for n in range(1, N):
    if n < K:
        dp[n] = np.amin(dp[np.maximum(n-k, 0)] + np.abs(H[n]-H[np.maximum(n-k, 0)]))
    else:
        dp[n] = np.amin(dp[n - k] + np.abs(H[n] - H[n - k]))


print(dp[N-1])


### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
# H = np.array([int(h) for h in input().split()])
H = np.array(list(map(int, input().split())))

dp = np.zeros(N, dtype=int)
k = np.array([i for i in range(1, K+1)])

for n in range(1, N):
    start = max(n-K, 0)
    #if n < K:
    #   dp[n] = np.amin(dp[start] + np.abs(H[n]-H[start]))
    #else:
    #   dp[n] = np.min(dp[n - k] + np.abs(H[n] - H[n - k]))
    dp[n] = np.min(dp[start:n] + np.abs(H[n]-H[start:n]))

print(dp[N-1])
### BUGGY CODE ###

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

for i in range(Q):
  l, r = map(int, input().split())
  deleted = S[l-1:r]
  
  print(len(''.join(deleted).split('AC'))-1)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N+1)

for i in range(1, N+1):
  t[i] = t[i-1] + (1 if S[i-1:i+1] == 'AC' else 0)
  
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1]-t[l-1])
### BUGGY CODE ###

from operator import itemgetter
import sys

input = sys.stdin.readline
n,m = map(int,input().split())

in_p = []
in_y = []
p = []

for _ in range(n):
    p.append([0])

for i in range(m):
    a,b = map(int,input().split())
    in_p.append(a)
    in_y.append(b)
    p[a-1].append(b)  

for i in range(n):
    p[i].sort()

for i in range(m):
    year=str(in_p[i]).zfill(6)
    a = p[in_p[i]-1].index(in_y[i]) 
    num=str(a).zfill(6)
    print("{0}{1}".format(year,num))



### FIXED CODE ###

import copy

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

cnt = [0]*(10**5+4)

yy = []
yp = []
for _ in range(m):
    a,b = map(int,input().split())
    a,b = b,a
    yy.append([a,0])
    yp.append([a,b])

inlist = copy.deepcopy(yp)
yp.sort()
yy = dict(yy)

for i in range(m):
    cnt[yp[i][1]]+=1
    yy[yp[i][0]] = cnt[yp[i][1]]

for key,value in inlist:
    print("{:06}{:06}".format(value,yy[key]))
### BUGGY CODE ###

N,M = map(int,input().split())
LRD = [list(map(int,input().split())) for _ in [0]*M]

E = [{} for _ in [0]*N]
for L,R,D in LRD:
    E[L-1][R-1] = D
    E[R-1][L-1] = -D

V = [-1]*N
breakFlg = False
for i in range(N):
    if V[i]!=-1:continue
    V[0] = 0
    q = [i]
    while q:
        j = q.pop()
        v = V[j]
        for k,d in E[j].items():
            if V[k] == -1:
                V[k] = v+d
                q.append(k)
            else:
                breakFlg = V[k] != v+d
            if breakFlg:break
        if breakFlg:break
    if breakFlg:break
print("No" if breakFlg else "Yes")

### FIXED CODE ###

N,M = map(int,input().split())
LRD = [(lambda x: [int(x[0])-1,int(x[1])-1,int(x[2])])(input().split()) for _ in [0]*M]

connect = [[] for _ in range(N)]
for L,R,D in LRD:
    connect[L].append([R,D])
    connect[R].append([L,-D])

ans = True
n = [None] * N
n0 = 0
while ans:
    q = [n0]
    n[n0] = 0
    for i in q:
        for j,d in connect[i]:
            if n[j] == None:
                n[j] = n[i] + d
                q.append(j)
            elif n[j]-n[i] != d:
                ans = False
                break
        if not ans:
            break
    for i in range(n0,N):
        if n[i] == None:
            n0 = i
            break
    else:
        break

if ans:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

from collections import deque

h, w = map(int,input().split())
A = [list(input()) for _ in range(h)]

def main():
    B = []

    for i,a in enumerate(A):
        for j,b in enumerate(a):
            if b == "#":
                B.append((i,j))

    dxy = [[1,0],[-1,0],[0,1],[0,-1]]

    stack = deque(B)
    darked = len(stack)
    targetd = h*w
    count = 0

    while darked < targetd:
        nextd = deque([])

        while stack:
            x, y = stack.popleft()
            for dx,dy in dxy:
                X = x + dx
                Y = y + dy
                if not(0 <= X < h) or not(0 <= Y < w):
                    continue
                if A[X][Y]==".":
                    A[X][Y]="#"
                    nextd.append((X,Y))
        count += 1
        stack = nextd
        darked += len(stack)
    print(count)
    
main()

### FIXED CODE ###

from collections import deque

def main():
    h, w = map(int,input().split())
    A = [list(input()) for _ in range(h)]
    B = []

    for i,a in enumerate(A):
        for j,b in enumerate(a):
            if b == "#":
                B.append((i,j))

    dxy = [[1,0],[-1,0],[0,1],[0,-1]]

    stack = deque(B)
    darked = len(stack)
    targetd = h*w
    count = 0

    while darked < targetd:
        nextd = deque([])

        while stack:
            x, y = stack.popleft()
            for dx,dy in dxy:
                X = x + dx
                Y = y + dy
                if not(0 <= X < h) or not(0 <= Y < w):
                    continue
                if A[X][Y]==".":
                    A[X][Y]="#"
                    nextd.append((X,Y))
        count += 1
        stack = nextd
        darked += len(stack)
    print(count)
    
main()
### BUGGY CODE ###

from sys import exit, stderr, stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    N, Q = list(map(int,input().split()))
    adjl = [[] for _ in range(N)]
    for _ in  range(N-1):
        a, b = list(map(lambda x: int(x)-1,input().split()))
        adjl[a].append(b)
        adjl[b].append(a)
    res = [0]*N
    for _ in  range(Q):
        p, x = list(map(lambda x: int(x),input().split()))
        res[p-1] += x
    def dfs(n, parent = None):
        if parent != None:
            res[n] += res[parent]
        for neigh in adjl[n]:
            if neigh == parent:
                continue
            else:
                dfs(neigh,n)
    dfs(0)
    for _ in range(N):
        print(res[_],end=" ")
    print()





if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import exit, stderr, stdin, setrecursionlimit
input = stdin.readline
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    N, Q = list(map(int,input().split()))
    adjl = [[] for _ in range(N+1)]
    for _ in  range(N-1):
        a, b = list(map(lambda x: int(x),input().split()))
        adjl[a].append(b)
        adjl[b].append(a)
    res = [0]*(N+1)
    # print(adjl)
    for _ in  range(Q):
        p, x = list(map(lambda x: int(x),input().split()))
        res[p] += x
    # def dfs(n, parent = None):
    #     if parent != None:
    #         res[n] += res[parent]
    #     for neigh in adjl[n]:
    #         if neigh == parent:
    #             continue
    #         else:
    #             dfs(neigh,n)
    # dfs(0)
    q = [(1,0)]
    while q:
        x, parent = q.pop()
        res[x] += res[parent]
        for neigh in adjl[x]:
            if neigh != parent:
                q.append((neigh,x))

    print(' '.join(map(str,res[1:])))





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

from collections import deque
from math import factorial

def perm(n, r):
    if n >= r:
        return factorial(n) // factorial(n - r)
    else:
        return 0

MOD = 1000000007
n, k = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n-1)]
edges = [set() for _ in range(n)]
visited = [False for _ in range(n)]
for a, b in AB:
    edges[a-1].add(b-1)
    edges[b-1].add(a-1)
q = deque([0])
visited[0] = True
first = True
ans = k
while q:
    v = q.popleft()
    visited[v] = True
    children = list(filter(lambda x: not visited[x], edges[v]))
    if first:
        ans *= perm(k-1, len(children))
        ans %= MOD
        first = False
    else:
        ans *= perm(k-2, len(children))
        ans %= MOD
    q.extend(children)
print(ans)


### FIXED CODE ###

from collections import deque

MOD = 1000000007
n, k = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n-1)]
edges = [set() for _ in range(n)]
visited = [False for _ in range(n)]
for a, b in AB:
    edges[a-1].add(b-1)
    edges[b-1].add(a-1)

upper = max(n, k)
fact = [1] * (upper+1)
fact_inv = [1] * (upper+1)
for i in range(1, upper+1):
    fact[i] = fact[i-1] * i % MOD
fact_inv[upper] = pow(fact[upper], MOD-2, MOD)
for i in range(upper-1, 0, -1):
    fact_inv[i] = fact_inv[i+1] * (i+1) % MOD
def perm(n, r):
    if n < r or r < 0:
        return 0
    return fact[n] * fact_inv[n-r] % MOD

q = deque([0])
visited[0] = True
first = True
ans = k
while q:
    v = q.popleft()
    visited[v] = True
    children = list(filter(lambda x: not visited[x], edges[v]))
    if first:
        ans *= perm(k-1, len(children))
        ans %= MOD
        first = False
    else:
        ans *= perm(k-2, len(children))
        ans %= MOD
    q.extend(children)
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
A = [0] * N
B = [0] * N
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
A.sort()
B.sort()
N_q, N_mod = divmod(N, 2)
if N_mod == 1:
    ans = B[N_q] - A[N_q] + 1
else:
    ans_list = []
    for x in range(A[N_q - 1], B[N_q - 1] + 1, 1):
        for y in range(A[N_q], B[N_q] + 1, 1):
            ans_list.append((x + y) / 2)
    c = collections.Counter(ans_list)
    values, counts = zip(*c.most_common())
    ans = len(values)
print(ans)

### FIXED CODE ###

import collections
N = int(input())
A = [0] * N
B = [0] * N
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
A.sort()
B.sort()
N_q, N_mod = divmod(N, 2)
if N_mod == 1:
    ans = B[N_q] - A[N_q] + 1
else:
    ans = B[N_q - 1] - A[N_q - 1] + B[N_q] - A[N_q] + 1
print(ans)
### BUGGY CODE ###

h, w = map(int, input().split())
s=[]
for i in range(h):
    s.append(list(input()))

l=[[0 for i in range(w)] for j in range(h)]
r=[[0 for i in range(w)] for j in range(h)]
u=[[0 for i in range(w)] for j in range(h)]
d=[[0 for i in range(w)] for j in range(h)]
for y in range(h):
    for x in range(w):
        if s[y][x] == '.':
            if x == 0:
                l[y][x]=1
            else:
                l[y][x]=l[y][x-1]+1
        
        if s[y][w-x-1] == '.':
            if x == 0:
                r[y][w-x-1]=1
            else:
                r[y][w-x-1]=r[y][w-x]+1

        if s[y][x] == '.':
            if y == 0:
                u[y][x]=1
            else:
                u[y][x]=u[y-1][x]+1
        
        if s[h-y-1][x] == '.':
            if y == 0:
                d[h-y-1][x]=1
            else:
                d[h-y-1][x]=d[h-y][x]+1

ans=0
for y in range(h):
    for x in range(w):
        val=l[y][x]+r[y][x]+u[y][x]+d[y][x]-3
        ans=max(ans, val)

print(ans)

### FIXED CODE ###

h, w = map(int, input().split())
s=[]
for i in range(h):
    s.append(list(input()))
 
l=[[0 for i in range(w)] for j in range(h)]
r=[[0 for i in range(w)] for j in range(h)]
u=[[0 for i in range(w)] for j in range(h)]
d=[[0 for i in range(w)] for j in range(h)]
for y in range(h):
    for x in range(w):
        if s[y][x] == '.':
            if x == 0:
                l[y][x]=1
            else:
                l[y][x]=l[y][x-1]+1
        
        if s[y][w-x-1] == '.':
            if x == 0:
                r[y][w-x-1]=1
            else:
                r[y][w-x-1]=r[y][w-x]+1
 
        if s[y][x] == '.':
            if y == 0:
                u[y][x]=1
            else:
                u[y][x]=u[y-1][x]+1
        
        if s[h-y-1][x] == '.':
            if y == 0:
                d[h-y-1][x]=1
            else:
                d[h-y-1][x]=d[h-y][x]+1
 
ans=0
for y in range(h):
    for x in range(w):
        val=l[y][x]+r[y][x]+u[y][x]+d[y][x]-3
        ans=max(ans, val)
 
print(ans)
### BUGGY CODE ###

def bfs(adj, s):
    n = len(adj)
    d = [-1 for _ in range(n)]
    c = [0 for _ in range(n)]

    d[s] = 0
    c[s] = 1

    queue = [s]

    while len(queue) > 0:
        u = queue.pop(0)
        for v in adj[u]:
            if c[v] == 0:
                c[v] = 1
                d[v] = d[u] + 1
                queue.append(v)

    return d


s = [int(x) for x in input().split()]
n = s[0]
m = s[1]
adj = [[] for _ in range(n)]
for _ in range(m):
    s = [int(x) for x in input().split()]
    adj[s[0]].append(s[1])
    adj[s[1]].append(s[0])

q = int(input())
for _ in range(q):
    s = [int(x) for x in input().split()]
    u = s[0]
    v = s[1]
    d = bfs(adj, u)
    if d[v] > 0:
        print("yes")
    else:
        print("no")


### FIXED CODE ###

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
    s = [int(x) for x in input().split()]
    adj[s[0]].append(s[1])
    adj[s[1]].append(s[0])

cc = [-1 for _ in range(n)]
cnt = 0
for i in range(n):
    if cc[i] < 0:
        cc[i] = cnt
        stack = [i]
        while stack:
            v = stack.pop()
            for u in adj[v]:
                if cc[u] < 0:
                    cc[u] = cnt
                    stack.append(u)
        cnt += 1

q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    if cc[s] == cc[t]:
        print("yes")
    else:
        print("no")
### BUGGY CODE ###

def main():
  def getCharNGram(n,s):
      charGram = [''.join(s[i:i+n]) for i in range(len(s)-n+1)]
      return charGram
  N = int(input())
  S = input()
  ans = 0
  from collections import Counter
  for i in range(1,N//2+1):
      l = getCharNGram(i,S)
      am = Counter(l)
      for j in am.values():
        if j>1:
          ans =max(i,ans)
  print(ans)
main()

### FIXED CODE ###

N = int(input())
S = input()
dp = [[0]*(N+1) for _ in range(N+1)]
res = 0
for i in range(N-1,-1,-1):
  for j in range(N-1,i,-1):
    if S[i]==S[j]:
      dp[i][j]=max(dp[i+1][j+1]+1,dp[i][j])
    res = max(res,min(j-i,dp[i][j]))
print(res)
### BUGGY CODE ###

N=int(input())
A=[input() for i in range(N)]
D=dict()
C=[]
for i in set(A):
    D[i]=0
for i in A:
    D[i]+=1
ans=0
for i in D.keys():
    if D[i]==max(D.values()):
        C.append(i)
C=sorted(C)
print(*C,sep='\n')

### FIXED CODE ###

N=int(input())
A=[input() for i in range(N)]

from collections import Counter
counter=Counter(A)
m=max(counter.values())
C=[]
for i,value in counter.items():
    if value==m:
        C.append(i)
C=sorted(C)
print(*C,sep='\n')
### BUGGY CODE ###

# 初期入力
import numpy as np
import sys
input = sys.stdin.readline
N = int(input())

#約数リストを作る
ans =0
div = np.zeros(N+1, np.int64)
for n in range(1, N+1):
    div[n:N+1:n] += 1

ans =0
for i in range(1,N+1):
    ans += i *div[i]
print(ans)

### FIXED CODE ###

#https://www.youtube.com/watch?v=3gFnZhZlAF8
#【競プロ実況】ABC172 AからD問題【かつっぱ】
# 等差数列の和
# 初期入力
import sys
input = sys.stdin.readline
N = int(input())
ans =0
for i in range(1,N+1):
    n =N//i #項数
    ans +=n*(2*i +(n-1)*i)//2
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)


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


n = int(input())
aa = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

dp = [10 ** 9] * (n + 10)
dp[0] = 0
ans1 = [0] * n
ans2 = [0] * n


def dfs(i=0, r=-1):
    global dp, ans1, ans2
    mi = 0
    ma = n
    while mi != ma:
        mm = (mi + ma) // 2
        if dp[mm] >= aa[i]:
            ma = mm
        else:
            mi = mm + 1

    be = dp[mi]
    dp[mi] = min(dp[mi], aa[i])
    ans1[i] = mi
    ans2[i] = max(ans1[i], ans2[r])

    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)

    dp[mi] = be


dfs()
print("\n".join(map(str, ans2)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)


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


n = int(input())
aa = {}
for j,i in enumerate(map(int,input().split())):
    if i in aa:
        aa[i].append(j)
    else:
        aa[i] = [j]
a = [0] * n
for k,i in enumerate(sorted(list(aa))):
    for j in aa[i]:
        a[j] = k+1


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r):
        l += self.n
        r += self.n
        s = self.one
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.b[r - 1])
            if l & 1:
                s = self.func(s, self.b[r - 1])
                l += 1
            l >>= 1
            r >>= 1
        return s


e = [[] for _ in range(n)]
for _ in range(n - 1):
    aa, bb = [int(i) - 1 for i in input().split()]
    e[aa].append(bb)
    e[bb].append(aa)
seg = SegmentTree([0] * (max(a)+2), max, 0)
ans1 = [0] * n
ans1[0] = 1
ans2 = [0] * n
ans2[0] = 1


def dfs(i=0, r=-1):

    y = seg.get_segment(0, a[i])
    ans1[i] = y + 1
    ans2[i] = max(ans2[r], ans1[i])

    be = seg.get_item(a[i])
    seg.update_func(a[i], ans1[i])
    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)
    seg.update(a[i], be)


dfs()
print("\n".join(map(str,(ans2))))
### BUGGY CODE ###

h, w, d = map(int, input().split())
num_dict = [[] for _ in range(h * w)]
for i in range(h):
    num_list = [int(i) for i in input().split()]
    for j, num in enumerate(num_list):
        num_dict[num - 1] = (i + 1, j + 1)
accum_list = [0 for _ in range(h * w)]
for i in range((h * w) - d):
    for j in range(i + d, (h * w), d):
        if j > 0:
            accum_list[i] += abs(num_dict[j][0] - num_dict[j - d][0]) + abs(num_dict[j][1] - num_dict[j - d][1])
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(accum_list[l - 1] - accum_list[r - 1])

### FIXED CODE ###

h, w, d = map(int, input().split())
num_dict = [[] for _ in range(h * w)]
for i in range(h):
    num_list = [int(i) for i in input().split()]
    for j, num in enumerate(num_list):
        num_dict[num - 1] = (i + 1, j + 1)
accum_list = [0 for _ in range(h * w)]
for i in range((h * w) - d - 1, -1, -1):
    accum_list[i] += (abs(num_dict[i + d][0] - num_dict[i][0]) +
                      abs(num_dict[i + d][1] - num_dict[i][1]) + accum_list[i + d])
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(accum_list[l - 1] - accum_list[r - 1])