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

import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
input = sys.stdin.readline
mod = 998244353
n = int(input())
p2t = [1]
for i in range(n):
  p2t.append(p2t[-1]*2%mod)
xy = [list(map(int,input().split())) for i in range(n)]
xy.sort()
yls = list(zip(*xy))[1]
yd = [(yls[i],i) for i in range(n)]
yd.sort()
yind = [0 for i in range(n)]
for i in range(n):
  y = yd[i][1]
  yind[y] = i
xyd = []
for i in range(n):
  xyd.append((i,yind[i]))
ans = 0
bit = Bit(n+1)
xyd.sort()
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])%mod+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])%mod+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1)%mod)
  ans %= mod
  bit.add(y+1,1)
print(ans)

### FIXED CODE ###

import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
input = sys.stdin.readline
from collections import defaultdict
mod = 998244353
n = int(input())
p2t = [1]
for i in range(n):
  p2t.append(p2t[-1]*2%mod)
dcy = defaultdict(int)
xy = [list(map(int,input().split())) for i in range(n)]
xy.sort()
yls = list(zip(*xy))[1]
yls = list(yls)
for i in range(n):
  dcy[yls[i]] = i
yls.sort()
yind = [0 for i in range(n)]
for i in range(n):
  ind = dcy[yls[i]]
  yind[ind] = i
xyd = []
for i in range(n):
  xyd.append((i,yind[i]))
ans = 0
bit = Bit(n+1)
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])%mod+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])%mod+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1)%mod)
  ans %= mod
  bit.add(y+1,1)
print(ans)
### BUGGY CODE ###

a = list(map(int,input().split()))
n = a[0]
m = a[1]

if m != 0:
  ab = [map(int, input().split()) for _ in range(m)]
  a, b = [list(i) for i in zip(*ab)]
  
  edge = [[0 for j in range(n)] for i in range(n)]
  for i in range(m):
    edge[a[i]-1][b[i]-1] = 1
    edge[b[i]-1][a[i]-1] = 1

  #print(set_list)

  ans = 1
  for i in range(n):
    aa = sum(edge[i])+1
    ans = max(aa,ans)

  print(ans)
else:
  print(1)

### FIXED CODE ###

n, m = [int(x) for x in input().split()]

if m != 0:
  g = [set() for _ in range(n)]
  valid = [-1] * n
  set_list = []
  for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a-1].add(b-1)
    g[b-1].add(a-1)

  j = -1
  for i in range(n):
    if valid[i] == -1:
      set_list.append(set())
      j += 1
      stack = [i]
      while len(stack)!=0:
        v = stack.pop()
        set_list[j].add(v)
        valid[v] = 1
        for i in g[v]:
          if valid[i] == -1:
            stack.append(i)
            set_list[j].add(i)
            valid[i] = 1
  ans = 1
  for i in range(len(set_list)):
    ans = max(len(set_list[i]),ans)

  print(ans)

else:
  print(1)
### BUGGY CODE ###

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################
n,w,r = map(int,input().split()) #n:頂点数　w:辺の数
t = list(map(int,input().split()))

d = [[float("inf")]*n for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
res = warshall_floyd(d)

print(max([res[t[0]-1][i-1] for i in t]))

### FIXED CODE ###

import itertools
 
n,m,r_ = map(int, input().split( ))
 
r = list(map(int, input().split( )))
for i in range(r_):
  	r[i] -= 1
d = [[10**10 for _ in range(n)] for i in range(n)]
 
for i in range(m):
    ai,bi,ci = map(int, input().split( ))
    ai-=1
    bi-=1
    d[ai][bi] = d[bi][ai] = ci

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][k]+d[k][j],d[i][j])
ans= 100000000000000
for l in itertools.permutations(r,r_):
    tmp = 0
    for i in range(r_-1):
        tmp += d[l[i]][l[i+1]]
    ans = min(ans, tmp)
 
print(ans)
### BUGGY CODE ###

from fractions import gcd

P = 10**9 + 7
n = int(input())

def lcm(p,q):
    return p*q//gcd(p,q)

a = list(map(int, input().split()))
x = a[0]
for i in range(1,n):
    x = lcm(x,a[i])
ans = 0
for i in range(n):
    ans += x//a[i]

    ans = ans%P
print(ans)

### FIXED CODE ###

from fractions import gcd

P = int(1e9)+7
n = int(input())

def lcm(p,q):
    return p*q//gcd(p,q)

a = list(map(int, input().split()))
x = a[0]
for i in range(1,n):
    x = lcm(x,a[i])
ans = 0
for i in range(n):
    ans += x//a[i]
ans = ans%P
print(ans)
### BUGGY 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()))
D = [0] * (X * Y)
E = [0] * (K * Z)
m, n = 0, 0

for i in range(X):
    for j in range(Y):
        D[m] = A[i] + B[j]
        m += 1

for k in range(len(sorted(D)[:: -1][: K])):
    for l in range(Z):
        E[n] = sorted(D)[:: -1][: K][k] + C[l]
        n += 1

for p in range(K):
    print(sorted(E)[:: -1][p])


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A, B, C = [sorted(list(map(int, input().split())))[:: -1][: K] for _ in range(3)]
D = []
for ai in A:
    for bi in B:
        D.append(ai + bi)

D = sorted(D)[:: -1][: K]

res = []
for di in D:
    for ci in C:
        res.append(di + ci)

res = sorted(res)[:: -1][: K]

for ans in res:
    print(ans)
### BUGGY CODE ###

import numpy as np
from numba import njit

N, K = list(map(int, input().strip().split()))
A = np.array(input().strip().split(), dtype=np.int64)

@njit(cache=True)
def calc(a, step):
    b = np.array([0]*N)
    for i in range(N):
        left = int(max(0, i-a[i]))
        right = int(min(N-1, i+a[i]))
        b[left] += 1
        if right + 1 < N:
            b[right+1] -= 1
    b = np.cumsum(b)
    
    if step>=K:
        return b
    else:
        step += 1
        return calc(b, step)

ans = calc(A, 1)
ans = [str(x) for x in ans]
print(" ".join(ans))

### FIXED CODE ###

import numpy as np
from numba import njit

N, K = list(map(int, input().strip().split()))
A = np.array(input().strip().split(), dtype=np.int64)

@njit(cache=True)
def calc(a, step):
    b = np.array([0]*N)
    for i in range(N):
        left = int(max(0, i-a[i]))
        right = int(min(N-1, i+a[i]))
        b[left] += 1
        if right + 1 < N:
            b[right+1] -= 1
    b = np.cumsum(b)
    
    if np.all(a==b) or step>=K:
        return b
    else:
        step += 1
        return calc(b, step)

ans = calc(A, 1)
ans = [str(x) for x in ans]
print(" ".join(ans))
### BUGGY CODE ###

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

XOR_A = [0] * (N+1)
SUM_A = [0] * (N+1)
for i in range(1, N+1):
    XOR_A[i] = XOR_A[i-1] ^ A[i-1]
    SUM_A[i] = SUM_A[i-1] + A[i-1]

ans = N
for i in range(N):
    for j in range(i+1, N):
        if XOR_A[j+1] ^ XOR_A[i] == SUM_A[j+1] - SUM_A[i]:
            ans += 1
print(ans)


### FIXED CODE ###

from collections import deque

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

ans = 0
tmp = 0
buf = deque()

for a in A:
    while tmp & a:
        item = buf.popleft()
        tmp ^= item
    buf.append(a)
    tmp |= a
    ans += len(buf)
print(ans)
### BUGGY CODE ###

def solve():
  n,k=map(int,input().split())
  H=list(map(int,input().split()))
  A=[0]*n
  for i in range(1,n):
    A[i]=min(A[i-j]+abs(H[i]-H[i-j]) for j in range(1,min(i+1,k+1)))
  return A[n-1]
print(solve())

### FIXED CODE ###

def solve():
  n,k=map(int,input().split())
  H=list(map(int,input().split()))
  A=[0]*n
  for i in range(1,n):
    A[i]=min(A[i-j]+abs(H[i]-H[i-j]) for j in range(1,min(i+1,k+1)))
  return A[n-1]
print(solve())
### BUGGY CODE ###

def main():
    N,M=map( int, input().split())
    A=list( map( int, input().split()))
    for i in range(M):
        A[A.index(max(A))] = A[A.index(max(A))]//2
    print(sum(A))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import heapq
def main():
    N,M=map( int, input().split())
    A=list( map( int, input().split()))
    A = list(map(lambda x: x*(-1), A))
    heapq.heapify(A)
    for _ in range(M):
        u = heapq.heappop(A)
        heapq.heappush(A,int(u/2))
    print(-sum(A))


    

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

s = list(map(lambda x: int(x),list(input())))
p = [0 for i in range(2019)]
n = len(s)
ans = 0
kar = 0
for i in range(n):
    kar = (kar + s[n-1-i]*10**i)%2019
    p[kar] += 1

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

### FIXED CODE ###

s = list(input())
p = [0 for i in range(2019)]
n = len(s)
ans = 0
kar = 0
dig = 1
for i in range(n):
    kar = (kar + int(s[n-1-i])*dig)%2019
    dig = (dig*10)%2019
    p[kar] += 1

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

from itertools import permutations
H, W = map(int, input().split())
l = [input() for _ in range(H)]

q = [(0, 0, l[0][0], 0 if l[0][0]=="." else 1)]
ans = H * W
while q:
    y, x, c, score = q.pop()
    if y==H-1 and x==W-1:
        ans = min(ans, score)
    for y1, x1 in [(y+1, x), (y, x+1)]:
        if not (0<=x1<W and 0<=y1<H):continue
        if c=="#":
            q.append((y1, x1, l[y1][x1], score))
        else:
            q.append((y1, x1, l[y1][x1], score+1 if l[y1][x1]=="#" else score))

print(ans)


### FIXED CODE ###

def solve():
    H, W = map(int, input().split())
    l = [list(input()) for _ in range(H)]
    q = [(0, 0)]
    sc = [[H*W]*W for _ in range(H)]
    sc[0][0] = 0 if l[0][0]=="." else 1

    while q:
        y, x = q.pop()
        for y1, x1 in [(y+1, x), (y, x+1)]:
            if not (0<=x1<W and 0<=y1<H):continue
            if l[y][x]=="#":
                if sc[y1][x1] > sc[y][x]:
                    sc[y1][x1] = sc[y][x]
                    q.append((y1, x1))
            else:
                v = sc[y][x]+1 if l[y1][x1]=="#" else sc[y][x]
                if sc[y1][x1] > v:
                    sc[y1][x1] = v
                    q.append((y1, x1))

    print(sc[-1][-1])


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

# 入力
N = int(input())
A = list(map(int,input().split()))

P = 10**9+7
bit = [0 for i in range(60)]

# 各bit独立に1が何個あるか数える
for a in A:
    for i in range(60):
        if a&(1<<i):
            bit[i] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
ans = 0
for i,a in enumerate(bit):
    ans += a*(N-a)*(2**i)
    ans %= P

print(ans)


### FIXED CODE ###

# 入力
N = int(input())
A = list(map(int,input().split()))

ans = 0
P = 10**9+7
bit = [0 for i in range(70)]

# 各bit独立に1が何個あるか数える
for i in range(N):
    S = bin(A[i])
    for j in range(1,len(S)-1):
        if S[-1*j] == '1':
            bit[j-1] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
for i in range(70):
    ans += (2**i)*bit[i]*(N-bit[i])
    ans %= P

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

n,m=map(int,input().split())
a = [int(input()) for i in range(m)]

dp=[0]*(n+1)
for i in range(n,-1,-1):
  if i in a:
    dp[i] = 0
  elif i==n:
    dp[i]=1
  elif i==n-1:
    dp[i]=1
  else:
    dp[i]=dp[i+1]+dp[i+2]
print(dp[0]%1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
a = [int(input()) for i in range(m)]
dp=[0]*(n+1)
if m==0:
  for i in range(n,-1,-1):
    if i==n or i==n-1:
      dp[i]=1
    else:
      dp[i]=dp[i+1]+dp[i+2]
  print(dp[0]%1000000007)
else:
  j=-1
  for i in range(n,-1,-1):
    if i==a[j]:
      if m>j*(-1):
        j-=1
    else:
      if i==n or i==n-1:
        dp[i]=1
      else:
        dp[i]=dp[i+1]+dp[i+2]
  print(dp[0]%1000000007)
### BUGGY CODE ###

import heapq

H,W,K=map(int,input().split())
A=["" for i in range(H)]
for i in range(H):
    A[i]=input()

for i in range(H):
    for j in range(W):
        if A[i][j]=="S":
            s=(i,j)

move=[(0,1),(1,0),(0,-1),(-1,0)]
start=set([s])
que=[(0,s[0],s[1])]
heapq.heapify(que)
while que:
    count,posx,posy=heapq.heappop(que)
    if count==K:
        continue

    for i,j in move:
        nx=posx+i;ny=posy+j
        if H-1>=nx>=0 and W-1>=ny>=0 and A[nx][ny]!="#" and (nx,ny) not in start:
            start.add((nx,ny))
            heapq.heappush(que,(count+1,nx,ny))


ans=float("inf")
while start:
    x,y=start.pop()
    test=1+min((abs(x-0)-1)//K+1,(abs(H-1-x)-1)//K+1,(abs(y-0)-1)//K+1,(abs(W-1-y)-1)//K+1)
    ans=min(ans,test)

if s[0]==0 or s[0]==H-1 or s[1]==0 or s[1]==W-1:
    ans=0
print(ans)


### FIXED CODE ###

from collections import deque

H,W,K=map(int,input().split())
A=["" for i in range(H)]
for i in range(H):
    A[i]=input()

for i in range(H):
    for j in range(W):
        if A[i][j]=="S":
            s=(i,j)

move=[(0,1),(1,0),(0,-1),(-1,0)]
start=set([s])
que=deque([(0,s[0],s[1])])
while que:
    count,posx,posy=que.popleft()
    if count==K:
        continue

    for i,j in move:
        nx=posx+i;ny=posy+j
        if H-1>=nx>=0 and W-1>=ny>=0 and A[nx][ny]!="#" and (nx,ny) not in start:
            start.add((nx,ny))
            que.append((count+1,nx,ny))


ans=float("inf")
for x,y in start:
    test=1+min((abs(x-0)-1)//K+1,(abs(H-1-x)-1)//K+1,(abs(y-0)-1)//K+1,(abs(W-1-y)-1)//K+1)
    ans=min(ans,test)

if s[0]==0 or s[0]==H-1 or s[1]==0 or s[1]==W-1:
    ans=0
print(ans)
### BUGGY CODE ###

import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

x, y = map(int, input().split())
s, l = min(x,y), max(x,y)
if 2*s-l<0 or (2*s-l)%3!=0:
  print(0)
else:
  r = (2*s-l)//3
  n = 2*r+l-s
  print(comb(n,r)%1000000007)

### FIXED CODE ###

import sys

x, y = map(int, input().split())
s, l = min(x,y), max(x,y)

if 2*s-l<0 or (2*s-l)%3!=0:
    print(0)
    sys.exit()

r = (2*s-l)//3
n = (s+l)//3
mod = 10**9+7
g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1]
for i in range(2, n+1):
    g1.append((g1[-1] * i) % mod)
    inv.append((-inv[mod%i] * (mod//i)) % mod)
    g2.append((g2[-1] * inv[-1]) % mod)

def comb(n, r):
    if r<0 or r>n:
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

print(comb(n, r))
### BUGGY CODE ###

from functools import reduce

def main():
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    

    N = int(input().rstrip())
    A = list(int(_) for _ in input().split())
    s_num = N -1
    ans = 2**(N//2)
    while s_num > 0:
        count = A.count(s_num)
        if(s_num != 0 and count != 2):
            ans = 0 
            break
        elif(s_num == 0 and count !=1):
            ans = 0 
            break
        s_num -= 2
    
    print(ans)
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

from functools import reduce
import bisect

def main():
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10

    # mod用
    p=10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    

    N = int(input().rstrip())
    # A = list(map(int, input().split()))
    A = list(int(_) for _ in input().split())
    # A = list(input().split())
    A.sort()
    flag = False
    if A[0] == 0 and N%2 == 1:
        flag = True
        for i in range(N):
            if A[i] != (i + 1) // 2 * 2:
                flag = False
                break
    if A[0] == 1 and N%2 == 0:
        flag = True
        for i in range(N):
            if A[i] != i // 2 * 2 + 1:
                flag = False
                break
    if flag:
        print(2**(N//2) % p)
    else:
        print(0)
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def framod(n, mod, a=1):
    for i in range(1, n + 1):
        a = a * i % mod
    return a


def power(n, r, mod):
    if r == 0:
        return 1
    if r % 2 == 0:
        return power(n * n % mod, r // 2, mod) % mod
    if r % 2 == 1:
        return n * power(n, r - 1, mod) % mod


def cmb(n, k, mod=10**9+7):
    a = framod(n, mod)
    b = framod(k, mod)
    c = framod(n - k, mod)
    return (a * power(b, mod - 2, mod) * power(c, mod - 2, mod)) % mod


def modpow(n, m, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (modpow(n, m, p//2)**2) % m
    return (modpow(n, m, p-1)*n) % m


def resolve():
    n, a, b = map(int, input().split())
    mod = 10 ** 9 + 7
    ans = modpow(2, mod, n) - 1
    ans -= cmb(n, a)
    ans -= cmb(n, b)
    print(ans % mod)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

def comb(a, b, p=10 ** 9 + 7):
    if (b > a - b):
        return comb(a, a - b, p)
    c = d = 1
    for i in range(b):
        c *= (a - i)
        d *= (b - i)
        c %= p
        d %= p
    return c * modpow(d, p - 2, p) % p


def modpow(n, p, m=10 ** 9 + 7):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (modpow(n, p // 2, m) ** 2) % m
    return (modpow(n, p - 1, m) * n) % m


def resolve():
    n, a, b = map(int, input().split())
    mod = 10 ** 9 + 7
    ans = modpow(2, n) - 1
    ans -= comb(n, a)
    ans -= comb(n, b)
    print(ans % mod)


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

n = int(input())
list_a = list(map(int, input().split()))
list_a.sort()

for i in range(n):
    under = list_a.count(i+1)
    print(under)
    del list_a[:under]


### FIXED CODE ###

n = int(input())
list_a = list(map(int, input().split()))
from collections import Counter
under = Counter(list_a)

for i in range(1,n+1):
    print(under[i])
### BUGGY CODE ###

k, s = map(int, input().split())
ans = 0
for z in range(0, k+1):
    sz = s-z
    for xy in range(0, k+1):
        if xy+xy == sz:
            ans += 1
            break
        elif xy+xy > sz:
            break

    for x in range(0, k):
        for y in range(x+1, k+1):
            if x+y == sz:
                ans +=2
                break
            elif x+y > sz:
                break
print(ans)

### FIXED CODE ###

k, s = map(int, input().split())
ans = 0
for z in range(0, k+1):
    sz = s-z
    for x in range(0, k+1):
        szx = sz-x
        if 0 <= szx <= k:
            ans += 1
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

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

#最小公倍数でよいか？
#全てのjについてAiBiはAjで割り切れる
#計算時間は？
from fractions import gcd
mod =10**9+7
def lcd(x,y):
    g = gcd(x,y)
    return x*y//g

ag = 1
for i in range(n):
    ag = lcd(ag,a[i])

ans = 0

for i in range(n):
    ans += ag//a[i]
    ans %= mod

print(ans)

### FIXED CODE ###


from fractions import gcd
import random
n = int(input())
a = list(map(int, input().split( )))
random.shuffle(a)
#最小公倍数でよいか？
#全てのjについてAiBiはAjで割り切れる
#計算時間は？

mod =10**9+7
def lcd(x,y):
    g = gcd(x,y)
    return x*y//g

ag1 = 1
for i in range(n//2):
    ag1 = lcd(ag1,a[i])
ag2 = 1
for i in range(n//2,n):
    ag2 = lcd(ag2,a[i])

ag3 = lcd(ag1,ag2)

ans = 0

for i in range(n//2):
    ans += ag1//a[i]
ans*=ag3//ag1
ans %=mod
ans2 = 0
for i in range(n//2,n):
    ans2 += ag2//a[i]
ans2*= ag3//ag2
ans2%=mod 
ans += ans2
ans %=mod
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7
ans = 0
keta = 0
while a != [0]*n:
    b = list(map(lambda x: x % 2, a))
    a = list(map(lambda x: x//2, a))
    num_1 = b.count(1)
    ans += (num_1 * (n-num_1) * pow(2, keta, mod)) % mod
    ans %= mod
    keta += 1
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a = list(map(lambda x: (str(bin(x))[2:]).zfill(65), a))
mod = 10**9 + 7
ans = 0
for i in range(65):
    cnt = 0
    for j in a:
        if j[-1*(i+1)] == "1": cnt += 1
    ans += cnt * (n-cnt) * pow(2, i, mod) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline

######################################################

INF = 1e10

H, W, D = [int(_) for _ in input().split()]

A = [[int(_) for _ in input().split()]
     for _ in range(H)]

B = [-1] * (H * W)
for i in range(H):
    h = i * W
    for j in range(W):
        B[h + j] = (A[i][j], (i, j))
B.sort()
C = [b[0] for b in B]

import bisect

for i in range(int(input())):
    l, r = [int(_) for _ in input().split()]
    pre = None
    ans = 0
    while l <= r:
        ni = bisect.bisect_left(C, l)
        # print(B[ni])
        if pre is not None:
            ans += abs(B[ni][1][0] - pre[0]) + abs(B[ni][1][1] - pre[1])
        l = l + D
        pre = (B[ni][1])
    print(ans)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

######################################################

H, W, D = [int(_) for _ in input().split()]

A = [[int(_) for _ in input().split()]
     for _ in range(H)]

B = [None] * (H * W + 1)
for i in range(H):
    h = i * W
    for j in range(W):
        B[h + j] = (A[i][j], (i, j))
B[H * W] = (0, (-1, -1))
B = sorted(B, key=lambda x: x[0])
costs = [0] * (H * W + 1)
for i in range(H * W, 0, -1):
    if i + D <= H * W:
        costs[i] = costs[i + D] + abs(B[i][1][0] - B[i + D][1][0]) + abs(B[i][1][1] - B[i + D][1][1])

for i in range(int(input())):
    l,r = [int(_) for _ in input().split()]
    print(costs[l] - costs[r])