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

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))

V = [0] + V + [0]

# 0.前処理
# N+2個の条件をつくる
left = [0]
right = [0]

for i in range(N):
    left.append(right[i])
    right.append(left[-1]+T[i])
    
left.append(right[-1])
right.append(right[-1])

INF = float("inf")
vel = [INF]*(2*right[-1]+1)

# 1.各ステップでの許容測度の最大値の最小値を求める
for t in range(2*right[-1]+1):
    for i in range(N+2):
        if (t/2) < left[i]:
            vel[t] = min(vel[t], -(t/2)+(V[i]+left[i]))
        elif left[i] <= (t/2) and (t/2) <= right[i]:
            vel[t] = min(vel[t], V[i])
        elif (t/2) > right[i]:
            vel[t] = min(vel[t], (t/2)+(V[i]-right[i]))
            

# 2.面積を求める
ans = 0
for t in range(2*right[-1]):
    ans += (1/2)*0.5*(vel[t]+vel[t+1])
    
print(ans)

### FIXED CODE ###

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))

V = [0] + V + [0]

# 0.前処理
# N+2個の条件をつくる
left = [0]
right = [0]

for i in range(N):
    left.append(right[i])
    right.append(left[-1]+T[i])
    
left.append(right[-1])
right.append(right[-1])

INF = float("inf")
vel = [INF]*(2*right[-1]+1)

# 1.各ステップでの許容測度の最大値の最小値を求める
for t in range(2*right[-1]+1):
    for i in range(N+2):
        if (t/2) < left[i]:
            vel[t] = min(vel[t], -(t/2)+(V[i]+left[i]))
        elif left[i] <= (t/2) and (t/2) <= right[i]:
            vel[t] = min(vel[t], V[i])
        elif (t/2) > right[i]:
            vel[t] = min(vel[t], (t/2)+(V[i]-right[i]))
            

# 2.面積を求める
ans = 0
for t in range(2*right[-1]):
    ans += (1/2)*0.5*(vel[t]+vel[t+1])
    
print(ans)
### BUGGY CODE ###

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

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


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

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

def main():
    resp = 0
    k = int(input())
    for i in range(1, k + 1):
        for j in range(1, k + 1):
            for w in range(1, k + 1):
                resp += mdc(mdc(i, j), w)

    print(resp)
                
    
main()

### FIXED CODE ###

# In peace, in love, in war, everything is the same

import math

ar = [[0]*201 for i in range(201)]
for i in range(1, 201, 1):
	for j in range(1, 201, 1):
		ar[i][j] = math.gcd(i, j)
		
n, ans = int(input()), 0
for i in range(1, n+1, 1):
	for j in range(1, n+1, 1):
		for k in range(1, n+1, 1):
			ans += ar[ar[i][j]][k]
print(ans)
### BUGGY CODE ###

x=input()
lenx=len(x)
ans=0
ind=x.find("ST")
while(ind!=-1):
    ans+=2
    xlist=list(x)
    xlist.pop(ind)
    xlist.pop(ind)
    x=''.join(xlist)
    ind=x.find("ST")
print(lenx-ans)

### FIXED CODE ###

x=input()
ans=[]
for i in range(len(x)):
    if(x[i]=='S'):
        ans.append(x[i])
    elif(len(ans)>0 and ans[-1]=='S'):
        ans.pop()
    else:
        ans.append(x[i])
print(len(''.join(ans)))
### BUGGY CODE ###

import collections

h, w = map(int, input().split())

ss = [input() for _ in range(h)]
start = [0,0]
goal = [w-1,h-1]
wall_count = 0
for s in ss:
    wall_count += s.count("#")

min_count = h*w
dx = [1,-1,0,0]
dy = [0,0,1,-1]

stack = collections.deque([start])
visited = [[h*w for _ in range(h)] for _ in range(w)]
visited[start[0]][start[1]] = 1

while len(stack) > 0:
    pos = stack.popleft()
    if pos == goal:
        break
    
    for x,y in zip(dx, dy):
        next = [pos[0]+x, pos[1]+y]
        
        if next[0]<0 or w-1<next[0] or next[1]<0 or h-1<next[1]:
            continue
        if ss[next[1]][next[0]] == "#":
            continue
        if visited[next[0]][next[1]] < visited[pos[0]][pos[1]] + 1:
            continue
        stack.append(next)
        visited[next[0]][next[1]] = visited[pos[0]][pos[1]] + 1

if visited[w-1][h-1] == h*w:
    print("-1")
else:
    score = (h*w) - wall_count - visited[w-1][h-1]
    print(score)

### FIXED CODE ###

import collections

h, w = map(int, input().split())

ss = [input() for _ in range(h)]
start = [0,0]
goal = [w-1,h-1]
wall_count = 0
for s in ss:
    wall_count += s.count("#")

dx = [1,-1,0,0]
dy = [0,0,1,-1]

stack = collections.deque([start])
visited = [[-1 for _ in range(h)] for _ in range(w)]
visited[start[0]][start[1]] = 1

while len(stack) > 0:
    pos = stack.pop()
    if pos == goal:
        break
    
    for x,y in zip(dx, dy):
        next_pos = [pos[0]+x, pos[1]+y]
        
        if next_pos[0]<0 or (w-1)<next_pos[0] or next_pos[1]<0 or (h-1)<next_pos[1]:
            continue
        if ss[next_pos[1]][next_pos[0]] == "#":
            continue
        if visited[next_pos[0]][next_pos[1]] != -1:
            continue
        stack.appendleft(next_pos)
        visited[next_pos[0]][next_pos[1]] = visited[pos[0]][pos[1]] + 1

if visited[w-1][h-1] == -1:
    print("-1")
else:
    score = (h*w) - wall_count - visited[w-1][h-1]
    print(score)
### BUGGY CODE ###

from math import gcd

K = int(input())
total = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            d = gcd(a,b)
            total += gcd(d,c)
print(total)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())
total = 0
for a in range(K):
    for b in range(K):
        for c in range(K):
           total += gcd(a+1,b+1,c+1)
print(total)
### BUGGY CODE ###

n = int(input())
a = list(input().split())

b = []
for i in range(n):
    if i % 2 == 0:
        b.append(a[i])
    else:
        b.insert(0, a[i])

if n % 2 == 1:
    b = list(reversed(b))

print(' '.join(b))

### FIXED CODE ###

n = int(input())
a = list(input().split())

b = ['' for _ in range(n)]
m = n // 2

b[m] = a[0]

p = 1

for i in range(1, n):
    if i % 2 == 1:
        b[m - p] = a[i]
    else:
        b[m + p] = a[i]
        p += 1

if n % 2 == 1:
    b = list(reversed(b))

print(' '.join(b))
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x,d):
        d[x] = 0
        for y in v[x]:
            if d[y]:
                size[x] += dfs(y,d)
        return size[x]

    n = I()
    v = [[] for i in range(n)]
    size = [1]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [1]*n
    dfs(0,d)
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    for i in range(1,n):
        a = size[0]-size[i]
        b = n-a
        ans += (1-pow(inv,a,mod))*(1-pow(inv,b,mod))%mod
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    q = deque([0])
    d = [0]*n
    d[0] = 1
    pre = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                pre[y] = x
                q.append(y)
    V = list(range(1,n))
    V.sort(key = lambda x:-d[x])
    size = [1]*n
    for i in V:
        size[pre[i]] += size[i]
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    p = [pow(inv,i,mod) for i in range(n)]
    for i in range(1,n):
        a = size[i]
        b = n-a
        ans += (p[a]-1)*(p[b]-1)%mod
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

x,y,z,k=map(int, input().split())
a=sorted(list(map(int, input().split())),reverse=True)
b=sorted(list(map(int, input().split())),reverse=True)
c=sorted(list(map(int, input().split())),reverse=True)

sum_ab=[]

for i in a:
    for j in b:
      sum_ab.append(i+j)

sum_ab.sort(reverse=True)
sum_ab= sum_ab[:k]

sum_abc=[]
for i in sum_ab:
    for j in c:
      sum_abc.append(i+j)

sum_abc.sort(reverse=True)
for v in sum_abc[:k]:
    print(v)

### FIXED CODE ###

x,y,z,k=map(int, input().split())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
c=list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

t=[]

for i in a:
    for j in b:
      t.append(i+j)

t.sort(reverse=True)
t=t[:min(k,x*y)]

ans=[]
for i in c:
    for j in t:
      ans.append(i+j)

ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

S = input()
Q = int(input())

count = 0
ans = S

for i in range(Q):
    T = input().split()
    if len(T)==1:
        count+=1
        continue

    if count%2==0:
        if T[1] == '1': ans = T[2] + ans
        else: ans += T[2]
    else:
        if T[1] == '1': ans += T[2]
        else: ans = T[2] + ans

if count%2==0:
    print(ans)
else:
    print(ans[::-1])


### FIXED CODE ###

#!/usr/bin/env python3
S = input()
Q = int(input())

count = True
ans = S

ireru_mae = ''
ireru_usiro = ''
for i in range(Q):
    T = input().split()
    if len(T)==1:
        count = not(count)
        ans = ireru_mae + ans + ireru_usiro
        ireru_mae = ''
        ireru_usiro = ''
        continue

    if count:
        if T[1] == '1': ireru_mae = T[2] + ireru_mae
        else: ireru_usiro += T[2]
    else:
        if T[1] == '1': ireru_usiro += T[2]
        else: ireru_mae = T[2] + ireru_mae

ans = ireru_mae + ans + ireru_usiro
if count:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def I(): return int(input())

result = -1
num = 7
K = I()

if K % 2 == 0 or K %  5 == 0:
    print(-1)
    sys.exit()

for i in range(10**6):
    if num % K == 0:
        print(i+1)
        sys.exit()
    else:
        num += 7*10**(i+1)
        
print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
def I(): return int(input())


def main():
    K = I()
    if K % 2 == 0 or K %  5 == 0:
        print(-1)
        exit()
    if K % 7 == 0:
        K = 9*K//7
    else:
        K = 9*K
    amari = 1
    for i in range(10**6):
        amari = amari*10 % K
        if amari == 1:
            print(i+1)
            exit()
    print(-1)

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

import sys
sys.setrecursionlimit(10**9)

    
def g(to_li, from_li, dp, n):
    # nにつくパスの最大長
    if dp[n] != -1:
        return dp[n]
    if n == 0:
        return 0
    val = max([g(to_li, from_li, dp, t)+1 for t in to_li[n]])
    dp[n] = val
    return val
    

def main():
    N, M = [int(n) for n in input().split()]
    from_li = [[] for i in range(N+2)] # from[i]:=点iからつながった点
    to_li = [[] for i in range(N+2)] # to[i]:=点iにつながる点
    for i in range(M):
        x, y = [int(n) for n in input().split()]
        from_li[x].append(y)
        to_li[y].append(x)
    parents = []
    children = []
    dp = [-1]*(N+2)
    for index, to in enumerate(to_li):
        if index != N+1 and index != 0 and len(to) == 0:
            from_li[0].append(index)
            to_li[index].append(0)
    for index, fr in enumerate(from_li):
        if index != 0 and index != N+1 and len(fr) == 0:
            to_li[N+1].append(index)
            from_li[index].append(N+1)
    
    print(g(to_li, from_li, dp, N+1) - 2)




if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
def main():
    n, m = [int(n) for n in input().split()]
    paths = [[] for i in range(n+1)]
    for i in range(m):
        x, y = [int(r) for r in input().split()]
        paths[x].append(y)
    dp = [-1]*(n+1)

    ans = 0
    for i in range(n+1):
        ans = max(ans, dfs(paths, dp, i))
    print(ans-1)
def dfs(paths, dp, n):
    # nから下の最大長
    length = 0
    for p in paths[n]:
        val=0
        if dp[p] != -1:
            val = dp[p]
        else:
            val = dfs(paths, dp, p)
        length = max(length, val)
    length += 1 # pからnまでの一本もしくはnから終点までの一本
    dp[n] = length
    return length

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

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = [0 for _ in range(q)]
c = [0 for _ in range(q)]
for i in range(q):
    b[i], c[i] = map(int, input().split())

for num, rep in zip(b, c):
    a = [rep if ele == num else ele for ele in a]
    print(sum(a))

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
X = Counter(a)
q = int(input())
b = [0 for _ in range(q)]
c = [0 for _ in range(q)]
for i in range(q):
    b[i], c[i] = map(int, input().split())

ans = sum(a)
for num, rep in zip(b, c):
    ans += (rep * X[num] - num * X[num])
    X[rep] += X[num]
    del(X[num])
    print(ans)
### BUGGY CODE ###

n = int(input())
u = list(map(int,input().split()))
m = list(map(int,input().split()))
d = list(map(int,input().split()))
u.sort()
m.sort()
d.sort()

cnt = 0
a = []
for i in range(n):
    for j in range(cnt,n):
        if u[j] < m[i]:
            cnt += 1
        else:
            a.append(cnt)
            break
    else:
        a.append(cnt)

cnt = 0
ans = 0
for i in range(n):
    for j in range(cnt,n):
        if d[i] > m[j]:
            cnt += 1
        else:
            break
    ans += sum(a[:cnt])
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
u = list(map(int,input().split()))
m = list(map(int,input().split()))
d = list(map(int,input().split()))
u.sort()
m.sort()
d.sort()

ans = 0
for a in m:
    ans += bisect.bisect_left(u,a) * (n - bisect.bisect_right(d,a))
print(ans)
### BUGGY CODE ###

from sys import exit, stdin

input = stdin.readline
import copy
from collections import deque, Counter

# import numpy as np


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

if M == 0:
    print(1)
    exit()


D = [-1] * N
tmp = 0
for i in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    if D[a] == -1 and D[b] == -1:
        D[a] = tmp
        D[b] = tmp
        tmp += 1
    elif D[a] == -1 and D[b] != -1:
        D[a] = D[b]
    elif D[a] != -1 and D[b] == -1:
        D[b] = D[a]
    elif D[a] != D[b]:
        for k in range(N):
            if D[k] == D[b]:
                D[k] = a


R = Counter(D)
ans = R.most_common(2)
if ans[0][0] == -1:
    print(ans[1][1])
else:
    print(ans[0][1])


### FIXED CODE ###

from sys import exit, stdin

input = stdin.readline
import copy
from collections import deque, Counter

# import numpy as np


class BIT:
    def __init__(self, a=0):
        self.n = a
        self.d = [0] * (a + 1)

    def add(self, i, x=1):
        i += 1
        while i <= self.n:
            self.d[i] += x
            i += i & (-i)

    def sum(self, *i):
        if len(i) == 1:
            x = 0
            i += 1
            while i:
                x += self.d[i]
                i -= i & (-i)
            return x
        else:
            return sum(self, i[1] - 1) - sum(self, i[0] - 1)


class UnionFind:
    def __init__(self, N):
        # N = data size
        self.n = N
        self.parents = [-1] * N

    def find(self, x):
        # find x's root
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        # unite x and y
        rx = self.find(x)
        ry = self.find(y)

        if rx == ry:
            return False
        if -(self.parents[rx]) < -(self.parents[ry]):
            rx, ry = ry, rx
        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx
        return True

    def size(self, x):
        # size of group of x's root
        return -(self.parents[self.find(x)])

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return "\n".join("{}: {}".format(r, self.members(r)) for r in self.roots())


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

if M == 0:
    print(1)
    exit()


D = UnionFind(N)

for i in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    D.union(a, b)

num = [D.size(r) for r in D.roots()]

print(max(num))
### BUGGY CODE ###

def F(a,b):
  return max(len(str(a)), len(str(b)))

N = int(input())
ans = float('inf')
for a in range(1,N+1):
  if N % a != 0: continue
  ans = min(ans,F(a,int(N/a)))
print(ans)

### FIXED CODE ###

def sol(n):
  ans = float('inf')
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      ans = min(ans, max(len(str(i)),len(str(n//i))))
            
  return ans

print(sol(int(input())))
### BUGGY CODE ###

import numpy as np
 
n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
s = 0

for i in range(60):
    assert np.count_nonzero(arr & 1) == sum(arr & 1)
    c1 = np.count_nonzero(arr & 1)
    s += 2 ** i * c1 * (n - c1)
    arr >>= 1
print(s % mod)

### FIXED CODE ###

import sys
import numpy as np
 
n = int(input())
lst = [int(i) for i in sys.stdin.readline().split()]
arr = np.array(lst, np.int64)

mod = 10 ** 9 + 7
x_sum = 0

for i in range(60):
    c1 = np.count_nonzero(arr & 1)
    x_sum += (c1 * (n - c1) * 2 ** i)
    x_sum %= mod
    arr >>= 1
print(x_sum)
### BUGGY CODE ###

#abc133 c
L,R=map(int,input().split())
x=R-L
ans=0
R=min(R,L+2019*2)
ans=2018
for i in range(L,R+1):
    for j in range(i+1,R+1):
        amari=(i*j)%2019
        ans=min(ans,amari)
print(ans)


### FIXED CODE ###

#abc133 c
L,R=map(int,input().split())
x=R-L
ans=0
R=min(R,L+2019*2)
ans=2018
for i in range(L,R+1):
    for j in range(i+1,R+1):
        amari=(i*j)%2019
        ans=min(ans,amari)
        if ans==0:
            break
print(ans)
### BUGGY CODE ###

import heapq

def main():
    n, m = map(int, input().split())
    dic = {}
    for _ in range(m):
        l, r, c = map(int, input().split())
        ky = (l-1, r-1)
        if ky in dic:
            if c < dic[ky]:
                dic[ky] = c
        else:
            dic[ky] = c
    dist = [float("inf")]*n
    dist[0] = 0
    hq = []
    heapq.heappush(hq, [0, 0])
    while len(hq) > 0:
        v, p = heapq.heappop(hq)
        if v > dist[p]:
            continue
        if p == n-1:
            break
        rm = set()
        for l, r in dic.keys():
            u = dic[(l, r)]
            if l <= p <= r:
                rm.add((l, r))
                for i in range(l, r+1):
                    if i == p:
                        continue
                    if dist[i] > dist[p] + u:
                        dist[i] = dist[p] + u
                        heapq.heappush(hq, [dist[i], i])
        for ky in rm:
            dic.pop(ky)
    if dist[n-1] == float("inf"):
        print(-1)
    else:
        print(dist[n-1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

import heapq

def main():
    n, m = map(int, input().split())
    dics = [{} for _ in range(n)]
    for _ in range(m):
        l, r, c = map(int, input().split())
        ky = r-1
        if ky in dics[l-1]:
            if c < dics[l-1][ky]:
                dics[l-1][ky] = c
        else:
            dics[l-1][ky] = c
    dist = [float("inf")]*n
    dist[0] = 0
    hq = []
    heapq.heappush(hq, [0, 0])
    idx = 0
    while len(hq) > 0:
        v, p = heapq.heappop(hq)
        if p < idx:
            continue
        if p == n-1:
            break
        for i in range(idx+1, p):
            if len(dics[i]) > 0:
                for ky in dics[i].keys():
                    if ky in dics[p]:
                        if dics[p][ky] > dics[i][ky]:
                            dics[p][ky] = dics[i][ky]
                    else:
                        if p < ky:
                            dics[p][ky] = dics[i][ky]
        idx = p
        for r in dics[p].keys():
            if dist[r] > v + dics[p][r]:
                dist[r] = v + dics[p][r]
                heapq.heappush(hq, [v + dics[p][r], r])
    if dist[n-1] == float("inf"):
        print(-1)
    else:
        print(dist[n-1])

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

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

I = [0] * (w * h + 1)
for i in range(h):
    for j in range(w):
        I[A[i][j]] = (i, j)

s = []
g = []
for i in range(q):
    s, g = map(int, input().split())
    ans = 0
    while(g != s):
        ans += abs(I[s][0] - I[s + d][0]) + abs(I[s][1] - I[s + d][1])
        s += d
    print(ans)


### FIXED CODE ###

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

I = [0] * (w * h + 1)
for i in range(h):
    for j in range(w):
        I[A[i][j]] = (i, j)
D = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
    D[i] = D[i - d] + abs(I[i][0] - I[i - d][0]) + abs(I[i][1] - I[i - d][1])
s = []
g = []
for i in range(q):
    s, g = map(int, input().split())
    print(D[g] - D[s])
### BUGGY CODE ###

n, a, b = map(int, input().split())

MOD = 10 ** 9 + 7

def comb(n, r):
    fn = 1
    fr = 1
    for i in range(1, r+1):
        fn *= n - (i-1)
        fr *= i
    finv_r = pow(fr, MOD-2, MOD)

    return fn * finv_r % MOD
    

ans = pow(2, n, MOD) - 1 - comb(n, a) - comb(n, b)
ans %= MOD
print(ans)


### FIXED CODE ###

n, a, b = map(int, input().split())

MOD = 10 ** 9 + 7

def comb(n, r):
    ret = 1
    for i in range(r):
        ret *= n - i
        ret %= MOD
    for i in range(r):
        ret *= pow(i+1, MOD-2, MOD)
        ret %= MOD

    return ret % MOD
    

ans = pow(2, n, MOD) - 1 - comb(n, a) - comb(n, b)
ans %= MOD
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)

ans = 0
cnt = [0] * 2019
s=""

for i in range(N)[::-1]:
    s = "".join([S[i],s])
    cnt[int(s) % 2019] += 1

ans += cnt[0]
for i in range(1, 2019):
    ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)


### FIXED CODE ###

S = list(input())
N = len(S)

ans = 0
cnt = [0] * 2019
a = 1
s = 0

for i in range(N)[::-1]:
    s = int(S[i]) * a + s
    a *= 10
    a = a % 2019
    cnt[s % 2019] += 1
    s = s % 2019

ans += cnt[0]
for i in range(2019):
    ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)
### BUGGY CODE ###

from itertools import combinations
from functools import reduce
from collections import Counter


MOD = 10 ** 9 + 7
N = int(input())
S = input()
cnt = Counter(S)
ans = 0
for i in range(1, N + 1):
    for cs in combinations("abcdefghijklmnopqrstuvwxyz", i):
        ans += reduce(lambda x, y: x * y, [cnt[c] for c in cs])
        ans %= MOD
print(ans)


### FIXED CODE ###

from collections import Counter


MOD = 10 ** 9 + 7
input()
S = input()
ans = 1
for v in Counter(S).values():
    ans *= v + 1
    ans %= MOD
print(ans - 1)