Harryxun/stf_run huggingface dataset:
n, q = map(int, input().split())

graph = [[] for _ in range(n+1)] 
for i in range(1, n):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

point = [0]*(n+1)
for i in range(q):
  p, x = map(int, input().split())
  point[p] += x

seen = [False]*(n+1)
counter = [0]*(n+1)
sum_point = 0

def dfs(v):
  
  global graph
  global seen
  global sum_point
  global counter
  
  seen[v] = True
  sum_point += point[v]
  
  for next_v in graph[v]:
    
    if seen[next_v]: 
      continue
    dfs(next_v)
  
  counter[v] = sum_point
  sum_point -= point[v]

dfs(1)
print(counter[1::])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

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

graph = [[] for _ in range(n+1)] 
for i in range(1, n):
  a, b = map(int, sys.stdin.readline().split())
  graph[a].append(b)
  graph[b].append(a)

point = [0]*(n+1)
for i in range(q):
  p, x = map(int, sys.stdin.readline().split())
  point[p] += x

seen = [False]*(n+1)
counter = [0]*(n+1)
sum_point = 0

def dfs(v):
  
  global graph
  global seen
  global sum_point
  global counter
  
  seen[v] = True
  sum_point += point[v]
  
  for next_v in graph[v]:
    
    if seen[next_v]: 
      continue
    dfs(next_v)
  
  counter[v] = sum_point
  sum_point -= point[v]

dfs(1)
print(*counter[1::])
N, K = map(int, input().split())
A = list(map(int, input().split()))
l=[]           
seen={}
k=1
for i in range (K):
  if not k in seen.keys():
      l.append(k)
      seen[k]=i
      k=A[k-1]
  else:
    r_start=seen[k]
    roop=i-r_start
    c=K//roop
    K=K-roop*c
    break
ans=l[K]
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
l=[1]           
seen={}
k=1
for i in range (K):
  if not k in seen.keys():
      seen[k]=i
      k=A[k-1]
      l.append(k)
  else:
    r_start=seen[k]
    roop=i-r_start
    K=(K-r_start)%roop+r_start
    break
ans=l[K]
print(ans)
n,k=map(int,input().split())
a=list(map(int,input().split()))
for _ in range(n**0.5+1):
  add_a=[0]*(n+1)
  for i in range(n):
    a[i]
    add_a[max(0,i-a[i])]+=1
    add_a[min(n,i+a[i]+1)]-=1
  tmp=0
  for i in range(n):
    tmp+=add_a[i]
    a[i]=tmp
print(' '.join(map(str,a)))


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
for _ in range(min(k,int(n**0.5)+10)):
  add_a=[0]*(n+1)
  for i in range(n):
    a[i]
    add_a[max(0,i-a[i])]+=1
    add_a[min(n,i+a[i]+1)]-=1
  tmp=0
  for i in range(n):
    tmp+=add_a[i]
    a[i]=tmp
print(' '.join(map(str,a)))
def main():
  l = input()

  print(l**3/27)

if __name__ == '__main__':
  main()


### FIXED CODE ###

def main():
  l = input()

  print(int(l)**3/27)

if __name__ == '__main__':
  main()
N, X = map(int, input().split())
li = list(map(int, input().split()))
i = 0
D = 0
while D <= X:
    D += li[i]
    i += 1
    if i > N + 1:
        break
if i > N + 1:
    print(N+1)
else:
    print(i)


### FIXED CODE ###

N, X = map(int, input().split())
li = list(map(int, input().split()))
D = [0]*(N+1)
flag = "0"
for i in range(N):
    D[i+1] = D[i] + li[i]
    if D[i+1] > X:
        flag = "1"
        break
if flag == "1":
    print(i + 1)
else:
    print(N + 1)
a,b=map(int,input().split())
if a==b:
  ans=a*2
else:
  a*2-1
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
if a==b:
  ans=a*2
else:
  ans=max(a,b)*2-1
print(ans)
# coding:utf-8
import sys 
def main():
    n = int(input())
    t = [0]*n
    x = [0]*n
    y = [0]*n
    for i in range(n):
        t[i],x[i],y[i]=map(int,input().split())

    for i in range(1,n+1):
        idou  =  abs(x[i]-x[i-1])+abs(y[i]-y[i-1])
        jikan = t[i]-t[i-1]
        if idou > jikan:
            print('No')
            exit()
        elif jikan %2 != idou%2:
            print('No')
            exit()
    print('Yes')


if __name__ == '__main__' :
    main()

### FIXED CODE ###

# coding:utf-8
import sys 
def main():
    n = int(input())
    t = [0]*(n+1)
    x = [0]*(n+1)
    y = [0]*(n+1)
    for i in range(1,n+1):
        t[i],x[i],y[i]=map(int,input().split())

    for i in range(1,n+1):
        idou  =  abs(x[i]-x[i-1])+abs(y[i]-y[i-1])
        jikan = t[i]-t[i-1]
        if idou > jikan:
            print('No')
            exit()
        elif jikan %2 != idou%2:
            print('No')
            exit()
    print('Yes')


if __name__ == '__main__' :
    main()
s = input()
a = 0
for i in range(3):
  if s[i] = "1": a += 1
print (a)

### FIXED CODE ###

s = input()
a = 0
for i in range(3):
  if s[i] == "1": a += 1
print (a)
str = input()
#days = ["SUN","MON","TUE","WED","THU","FRI","SAT"]

if str =="SUN":
  print(str(7))
else if str = "MON":
  print(str(6))
else if str = "TUE":
  print(str(5))
else if str = "WED":
  print(str(4))
else if str = "THU":
  print(3)
else if str = "FRI":
  print(2)
else if str = "SAT":
  print(1)
 

### FIXED CODE ###

string = input()
#days = ["SUN","MON","TUE","WED","THU","FRI","SAT"]

if string =="SUN":
  print(str(7))
elif string == "MON":
  print(str(6))
elif string == "TUE":
  print(str(5))
elif string == "WED":
  print(str(4))
elif string == "THU":
  print(str(3))
elif string == "FRI":
  print(str(2))
elif string == "SAT":
  print(str(1))
n=int(input())
t,a=map(int,input().split())
h=list(map(int,input().split()))
temp=9999
for i in h:
    if temp>abs((t-h[i]*0.006)-a):
        temp=abs((t-h[i]*0.006)-a)
        ans=i+1
print(ans)


### FIXED CODE ###

n=int(input())
t,a=map(int,input().split())
h=list(map(int,input().split()))
temp=9999
for i in range(len(h)):
    if temp>abs((t-h[i]*0.006)-a):
        temp=abs((t-h[i]*0.006)-a)
        ans=i+1
print(ans)
print(*inpur().split(","))

### FIXED CODE ###

s = input().split(",")
print(" ".join(s))
N, K = map(int, input().split())
M = list(map(lambda x: int(x)-1, input().split()))
s = 0
order = [s]
sets = set(order)
while True:
  if M[s] in sets:
    #print(order, M[s])
    
    if K < order.index(M[s]):
      print(order[K-1]+1)
    else:
      K -= order.index(M[s])
      order = order[order.index(M[s]):]
      print(order[K%len(order)]+1)
    break
  order.append(M[s])
  sets.add(M[s])
  s = M[s]



### FIXED CODE ###

A = input()
B = input()
print("Yes") if len(A)+1==len(B) and A == B[:len(A)] else print("No")
s = get_input()
v = int(s)
print( v * v * v )

### FIXED CODE ###

s = input()
v = int(s)
print(v ** 3)
Sd = input()
T = input()
if len(Sd) < len(T):
    print("UNRESTORABLE")
else:
    D = []
    for i in range(len(Sd) - len(T) + 1):
        flag = 1
        S = Sd
        for j in range(len(T)):
            if Sd[i+j] == "?" or Sd[i+j] == T[j]:
                S = S[:i+j]+T[j]+S[i+j+1:]
            else:
                flag = 0
        if flag == 1:
            D.append(S.replace("?", "a"))
D.sort()
if len(D) == 0:
    print("UNRESTORABLE")
else:
    print(D[0])


### FIXED CODE ###

Sd = input()
T = input()
if len(Sd) < len(T):
    print("UNRESTORABLE")
else:
    D = []
    for i in range(len(Sd) - len(T) + 1):
        flag = 1
        S = Sd
        for j in range(len(T)):
            if Sd[i+j] == "?" or Sd[i+j] == T[j]:
                S = S[:i+j]+T[j]+S[i+j+1:]
            else:
                flag = 0
        if flag == 1:
            D.append(S.replace("?", "a"))
    D.sort()
    if len(D) == 0:
        print("UNRESTORABLE")
    else:
        print(D[0])
def Switches():
    from math import log2
    N, M = map(int, input().split())
    # m行n列
    switchList = []

    # スイッチの組み合わせ取得
    for i in range(M):
        k = list(map(int, input().split()))
        k = k[1:]
        # print(k)
        switchList.append([True * (i+1 in k) for i in range(N)])
    p = list(map(int, input().split()))
    # print(switchList)
    result = 0

    # 2bit化し、条件比較を行い結果がpと等しければ正解とする
    for i in range(2**N):
        tmp = format(i, "0"+str(N)+"b")
        tmp = [int(j) for j in tmp]
        # print(tmp)
        tmp = [sum([switchList[k][j] * tmp[j] for j in range(N)]) % 2 for k in range(M)]
        if p == tmp:
            result += 1

    print(result)

if __name__ == "__main__":
    Switches()

### FIXED CODE ###

def Switches():
    from math import log2
    N, M = map(int, input().split())
    # m行n列
    switchList = []

    # スイッチの組み合わせ取得
    for i in range(M):
        k = list(map(int, input().split()))
        k = k[1:]
        # print(k)
        switchList.append([True * (i+1 in k) for i in range(N)])
    p = list(map(int, input().split()))
    # print(switchList)
    result = 0

    # 2bit化し、条件比較を行い結果がpと等しければ正解とする
    for i in range(2**N):
        tmp = format(i, "0"+str(N)+"b")
        tmp = [int(j) for j in tmp]
        # print(tmp)
        tmp = [sum([switchList[k][j] * tmp[j] for j in range(N)]) % 2 for k in range(M)]
        if p == tmp:
            result += 1

    print(result)

if __name__ == "__main__":
    Switches()
n, x = map(int, input().split())


def p(level):
    if level == 0:
        return 1
    return 2*p(level-1)+1


def a(level):
    if level == 0:
        return 1
    return 2*a(level-1)+3


def f(level, x):
    if x == 1:
        return 0
    else:
        ai_1 = a(level-1)
        if 1 < x < 1 + ai_1:
            return f(level-1, x-1)
        else:
            pi_1 = p(level-1)
            if x == 2 + ai_1:
                return 1 + pi_1
            elif 2+ai_1 < x < 2 + 2*ai_1:
                return 1 + pi_1+f(level-1, x-2-ai_1)
            elif x == 3 + 2*ai_1:
                return 1 + 2*pi_1


print(f(n, x))

### FIXED CODE ###

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


def p(level):
    if level == 0:
        return 1
    return 2*p(level-1)+1


def a(level):
    if level == 0:
        return 1
    return 2*a(level-1)+3


def f(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1 + a(N-1):
        return f(N-1, X-1)
    else:
        return p(N-1) + 1 + f(N-1, X-2-a(N-1))



print(f(n, x))
import Sample Input
S = Sample Input
h = (S / 3600)
m = (S / 60)
s = (for S in range(0,60))
print('h:m:s')

### FIXED CODE ###

S = int(input())

s = S % 60
m = S // 60 % 60
h = S // 60 // 60

print("{0}:{1}:{2}".format(h,m,s))
from math import pi
r=int(input())
print("{0:.6f}".format(r*r*pi),"{0:.6f}".format(2*r*pi))


### FIXED CODE ###

from math import pi
r=float(input())
print("{0:.6f}".format(r*r*pi),"{0:.6f}".format(2*r*pi))
n,a,b=map(int,input().split())
mod=10**9+7
bikkuri=[0 for i in range(n+5)]
bikkuri[0]=1
gyaku=[0 for i in range(n+5)]
gyaku[0]=1
for i in range(1,n+5):
    bikkuri[i] = (i * bikkuri[i-1])%mod
for i in range(n+4, -1, -1)
    gyaku[i]=pow(bikkuri[i], mod-2, mod)
def comb(a,b):
    return bikkuri[a]*gyaku[b]*gyaku[a-b]
ans=(2**n)-1-comb(n,a)-comb(n,b)
print(ans%mod)

### FIXED CODE ###

n,a,b=map(int,input().split())
mod=10**9+7
bunbo=1
bunshi=1
for i in range(1,max(a+1, b+1)):
    bunbo*=i
    bunshi*=n-i+1
    bunshi%=mod
    bunbo%=mod
    if i==a:
        comba=bunshi*(pow(bunbo,mod-2,mod))
    if i==b:
        combb=bunshi*(pow(bunbo,mod-2,mod))
print((2**n-1-comba-combb)%mod)
n=int(input())
mod=10**9+7
print((pow(10,n,mod)-2*pow(9,n,mod)+pow(8,n,mod)%mod)

### FIXED CODE ###

n=int(input())
mod=10**9+7
print((pow(10,n,mod)-2*pow(9,n,mod)+pow(8,n,mod))%mod)
N, K = map(int, input().split())
print(min[N%K,K-N%K])

### FIXED CODE ###

N, K = map(int, input().split())
print(min([N%K,K-N%K]))
n, m = map(int, input().split())
l = list("")
ac, wa = 0, 0
for i in range(m):
    p, s = input().split()
    p = int(p)
    if l[p - 1] != -1 and s == "AC":
        ac += 1
        wa += l[p - 1]
        l[p - 1] = -1
    if l[p - 1] != -1 and s == "WA":
        l[p - 1] += 1
print(ac, wa)

### FIXED CODE ###

n, m = map(int, input().split())
l = [0] * n
ac, wa = 0, 0
for i in range(m):
    p, s = input().split()
    p = int(p)
    if l[p - 1] != -1 and s == "AC":
        ac += 1
        wa += l[p - 1]
        l[p - 1] = -1
    if l[p - 1] != -1 and s == "WA":
        l[p - 1] += 1
print(ac, wa)
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0 for _ in range(n+1)]
dp[2]=abs(h[1]-h[0])
for i in range(2,n):
    dp[i+1]=999999999
    for x in range(min(k,i)):
        if dp[i+1]>dp[i-x]+abs(h[i]-h[i-1-x]):
            dp[i+1]=dp[i-x]+abs(h[i]-h[i-1-x])
print(dp[n])


### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
dp=[0 for _ in range(n+1)]
dp[2]=abs(h[1]-h[0])
for i in range(2,n):
    dp[i+1]=min(dp[i]+abs(h[i]-h[i-1]),dp[i-1]+abs(h[i]-h[i-2]))
print(dp[n])
#####segfunc######
def segfunc(x,y):
    return x + y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

n, Q = map(int, input().split())
Cs = [0] + list(map(int, input().split()))
Qs = []
for i in range(Q):
  l,r = map(int, input().split())
  Qs.append((i,l,r))
Qs.sort(key=lambda x:x[2])  

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

ans = [-1]*Q
dic = {}
b = 1
 
for i,l,r in Qs:
  if b < r + 1:
    st = set()
    for j in range(b,r+1):
      if not Cs[j] in st and Cs[j] in dic:
        update(dic[Cs[j]], 0)
      st.add(Cs[j])
      dic[Cs[j]] = j
    for s in st:
      update(dic[s], 1)
    b = r + 1
  ans[i] = query(l,r+1)
    
for a in ans:
  print(a)

### FIXED CODE ###

from sys import stdin
input = stdin.readline
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
 
n, q = map(int, input().split())
tmp = list(map(int, input().split()))
color = [-1]
for v in tmp:
    color.append(v)
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 1
bit = Bit(n)
for l, r, i in qry:
    if last_update_idx < r+1:
        st = set()
        for j in range(last_update_idx, r+1):
            if not color[j] in st and color[j] in dic:
                bit.add(dic[color[j]], -1)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            bit.add(dic[v], 1)
        last_update_idx = r+1
    ans[i] = bit.sum(r) - bit.sum(l)
for v in ans:
    print(v)
a,b=input().split()
print(a*b)

### FIXED CODE ###

a,b=input().split()
print(int(a)*int(b))
import sympy
N = int(input())
div_arr = sympy.divisors(N)

if len(div_arr) == 1:
    print(1)
if len(div_arr) == 2:
    ans_num = max(div_arr)
else:
    memo = []
    if len(div_arr) % 2 == 0:
        last_idx = -1
        count = 0
        for i in range(len(div_arr)):
            count += 1
            if N == div_arr[i] * div_arr[last_idx] and count != len(div_arr) // 2:
                last_idx -= 1
                memo.append(len(str(div_arr[last_idx])))
            else:
                break
    else:
        target_index = len(div_arr) // 2
        memo.append(len(str(div_arr[target_index])))
    print(min(memo))

### FIXED CODE ###

N = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
div_arr = make_divisors(N)

if len(div_arr) == 1:
    print(1)
elif len(div_arr) == 2:
    ans_num = max(div_arr)
    print(len(str(ans_num)))
else:
    memo = []
    if len(div_arr) % 2 == 0:
        last_idx = -1
        count = 0
        for i in range(len(div_arr)):
            count += 1
            if N == div_arr[i] * div_arr[last_idx] and count != len(div_arr) // 2:
                last_idx -= 1
                memo.append(len(str(div_arr[last_idx])))
            else:
                break
    else:
        target_index = len(div_arr) // 2
        memo.append(len(str(div_arr[target_index])))
    print(min(memo))
n = input()
P = []
mx = {}
my = {}
for i in xrange(n):
    x, y = map(int, raw_input().split())
    if x > y: x, y = y, x
    mx[x] = i
    my[y] = i
    P.append((x, y))

kx = sorted(mx)
mi_x = min(mx); ma_x = max(mx)
ky = sorted(my)
mi_y = min(my); ma_y = max(my)

if ma_x < mi_y or ma_y < mi_x:
    print (ma_x - mi_x) * (ma_y - mi_y)
    exit(0)

ans = (ma_x - mi_x) * (ma_y - mi_y)
xm = ()
for i in xrange(n):
    i = mx[kx[i]]
    if xm <= kx[i]:
        break
    y = P[i][1]
    if y <= min(ma_x, ma_y):
        xm = min(xm, y)
    else:
        break
ans = min((ma_x - xm) * (ma_y - kx[0]), ans)

ym = 0
for i in xrange(n-1, -1, -1):
    i = my[ky[i]]
    if ky[i] <= ym:
        break
    x = P[i][0]
    if max(mi_x, mi_y) <= x:
        ym = max(ym, x)
    else:
        break
ans = min((ky[-1] - mi_x) * (ym - mi_y), ans)


### FIXED CODE ###

# seishin.py
from heapq import heappush, heappop, heapify

N = int(input())
P = []
for i in range(N):
    x, y = map(int, input().split())
    P.append((x, y) if x < y else (y, x))

X = [x for x, y in P]
Y = [y for x, y in P]

MIN = min(X)
MAX = max(Y)

# R_min = MIN, B_max = MAX
res = (max(X) - MIN) * (MAX - min(Y))

# R_min = MIN, R_max = MAX
base = MAX - MIN
heapify(P)

# 出来る限りスライドさせながら(B_max - B_min)を最小化
r = max(X)
while P:
    x, y = heappop(P)
    res = min(res, base * (r - x))
    if y != -1:
        # Bに入ってたxをRに入れて代わりにyをBに入れる
        heappush(P, (y, -1))
        r = max(r, y)
    else:
        # (x, y) のyの方がB_minに該当
        # => これ以上B_minを落とせない
        break

print(res)
a , b = map(int(), input().split)
print(a*b a*2+b*2)

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b , a*2+b*2)
def main():
    mod=1000000007
    S=input()
    l=len(s)
    DP=[[0]*13 for _ in range(l+1)]
    DP[0][0]=1
    for i in range(1,l+1):
        d=s[-i]
        tmp=pow(10,i-1,13)
        if d=='?':
            for j in range(10):
                for k in range(13):
                    m=(k+tmp*j)%13
                    DP[i][m]+=DP[i-1][k]
                    if DP[i][m]>=mod:
                        DP[i][m]-=mod
        else:
            d=int(d)
            for k in range(13):
                m=(k+tmp*d)%13
                DP[i][m]+=DP[i-1][k]
                if DP[i][m]>=mod:
                    DP[i][m]-=mod
    print(DP[-1][5])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    mod=1000000007
    s=input()
    l=len(s)
    DP=[[0]*13 for _ in range(l+1)]
    DP[0][0]=1
    for i in range(1,l+1):
        d=s[-i]
        tmp=pow(10,i-1,13)
        if d=='?':
            for j in range(10):
                for k in range(13):
                    m=(k+tmp*j)%13
                    DP[i][m]+=DP[i-1][k]
                    if DP[i][m]>=mod:
                        DP[i][m]-=mod
        else:
            d=int(d)
            for k in range(13):
                m=(k+tmp*d)%13
                DP[i][m]+=DP[i-1][k]
                if DP[i][m]>=mod:
                    DP[i][m]-=mod
    print(DP[-1][5])

if __name__ == '__main__':
    main()
k = int(input())
s = input()

if len(s) <= k:
    print(S)
else:
    t_s = s[:k] + "..."
    print(t_s)

### FIXED CODE ###

k = int(input())
s = input()

if len(s) <= k:
    print(s)
else:
    t_s = s[:k] + "..."
    print(t_s)
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

h,w,d = li()
a = [list(li()) for _ in range(h)]

num2point = [(-1,-1)]*(h*w+1)
for r, ai in enumerate(a):
    for c, aij in enumerate(ai):
        num2point[aij] = (r, c)
    

dist = [[] for _ in range(d)]
for num in range(h*w):
    i = num+1
    if i // d == 0 or i == d:
        dist[i%d].append(0)
        
    else:
        dist[i%d].append(abs(num2point[i][0]-num2point[i-d][0]) + abs(num2point[i][1]-num2point[i-d][1]))
        
dist_cum = [list(accumulate(dist_row)) for dist_row in dist]


q = ni()
for _ in range(q):
    l,r = li()
    print(dist_cum[l%d][r//d] - dist_cum[l%d][l//d])

### FIXED CODE ###

import sys
sdin = sys.stdin.readline

H,W,D = map(int, sdin().split())
A = []
for h in range(H):
    A.append(list(map(int, sdin().split())))
Q = int(sdin())
RL = []
for q in range(Q):
    RL.append(tuple(map(int, sdin().split())))


codn = {}
for h in range(H):
    for w in range(W):
        codn[A[h][w]] = (h+1, w+1)
        
# mod D上での累積和
cums = []
for d in range(D):
    cum = []
    res = D
    if d!=0:
        res = d
    
    cum = [0]
    while res+D <= H*W:
        prev = codn[res]
        nex = codn[res+D]
        cost = abs(nex[0]-prev[0]) + abs(nex[1]-prev[1])
        cum.append(cum[-1]+cost)
        
        res += D
    
    cums.append(cum)
    
# 各クエリの処理
ans = 0
for query in range(Q):
    q = RL[query]
    mod = q[0] % D
    start = (q[0]-mod) // D
    last = (q[1]-mod) // D
    if mod == 0:
        start -= 1
        last -= 1
    
    ans = cums[mod][last] - cums[mod][start]   
    
    print(ans)
import collections
N=int(input())
l=[input() for i in range(N)]
c=collections.Counter(l)
c=c.most_common()
l2=[]
 
M=c.[0][1]
for i in range(N):
    if c.[i][1]==M:
        l2.append(c.[i][0])
    else:
        break
l2.sort()
for j in range(len(l2)):
    print(l2[j])

### FIXED CODE ###

A, B, C=map(int, input().split())

if A==B and B!=C:
    print("Yes")
elif B==C and C!=A:
    print("Yes")
elif C==A and A!=B:
    print("Yes")
else:
    print("No")
import math
import sys

def prime_calc(n):
    rootN = int(n**0.5)
    prime = [2]
    data = [i + 1 for i in range(2,n,2)]
    while True:
        p = data[0]
        if rootN <= p:
            return len(prime + data)
        prime.append(p)
        data = [e for e in data if e % p != 0]

def main():
    l = []

    for line in sys.stdin:
        l.append(line)        

    for line in l:
        print(prime_calc(line))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import math
import sys

sup = 1000000

is_prime = [0] * sup

count = [0] * sup

def setup():
    is_prime[2] = 1
    for n in range(3,sup,2):
        flag = True
        for i in range(3, int(math.floor(math.sqrt(n) + 1)), 2):
            if n % i == 0:
                flag = False
                break
        if flag:
            is_prime[n] = 1

def precount():
    for n in range(2, sup):
        count[n] = count[n-1] + is_prime[n]

def main():
    setup()
    precount()

    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
         print(count[line])

if __name__ == "__main__":
    main()