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

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

S, T = map(int, input().split())

def f7(seq):
    seen = set()
    seen_add = seen.add
    return [ x for x in seq if x not in seen and not seen_add(x)]

graph_ken = [[]]
for i in range(1, N+1):
    now = i
    queue = graph[now][:]
    for _ in range(2):
        nextqueue = []
        for next in queue:
            nextqueue.extend(graph[next])
        queue = f7(nextqueue)
    graph_ken.append(queue)



queue = [S]
visit = [False]*(N+1)
ans = 0
while len(queue) > 0:
    nextqueue = []
    for now in queue:
        if visit[now]:
            continue
        visit[now] = True
        for next in graph_ken[now]:
            if not visit[next]:
                nextqueue.append(next)
    queue = f7(nextqueue)
    if visit[T]:
        break
    ans += 1

if visit[T]:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

S, T = map(int, input().split())

inf = 10**6
ans = [[inf, inf, inf] for i in range(N+1)]

q = deque([S])
ans[S][0] = 0
while q:
    now = q.popleft()
    for next in graph[now]:
        flag = 0
        for i in range(3):
            if ans[now][i] != inf:
                if ans[next][(i+1)%3] > ans[now][i] + 1:
                    flag = 1
                    ans[next][(i+1)%3] = ans[now][i] + 1
        if flag == 1:
            q.append(next)

if ans[T][0] == inf:
    print(-1)
else:
    print(ans[T][0]//3)
### BUGGY CODE ###

N = int(input())
S = input()

def cal(k):
    M = 0
    C = 0
    MC = 0
    res = 0
    for i in range(min(k,N)):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    for i in range(N):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if i+k < N:
            if S[i+k] == 'M':
                M += 1
            elif S[i+k] == 'C':
                C += 1
                MC += M

    return res
        
Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

### FIXED CODE ###

N = int(input())
S = input()

def cal(k):
    M = 0
    C = 0
    MC = 0
    res = 0
    k = min(k,N)
    for i in range(k):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    for i in range(N-k):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if S[i+k] == 'M':
            M += 1
        elif S[i+k] == 'C':
            C += 1
            MC += M
    for i in range(N-k,N):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1

    return res

Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))
### BUGGY CODE ###

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
c=0
for j in range(n):
  if [j,1] in l or [1,j] in l:
    if [j,n] in l or [n,j] in l:
      c+=1
      break
if c==1:print('POSSIBLE')
else:print('IMPOSSIBLE')

### FIXED CODE ###

n,m=map(int,input().split())
L=[];l=[]
for k in range(n):
  L.append(0)
for i in range(m):
  x=list(map(int,input().split()))
  l.append(x)
  if x[0]==1:
    L[x[1]]+=1
  if x[1]==1:
    L[x[0]]+=1
  if x[0]==n:
    L[x[1]]+=1
  if x[1]==n:
    L[x[0]]+=1
if max(L)==2:print('POSSIBLE')
else:print('IMPOSSIBLE')
### BUGGY CODE ###

from collections import Counter
N = int(input())
A_arr = list(map(int, input().split()))

A_arr = sorted(A_arr, reverse=True)
C_arr = Counter(A_arr)

count = 0
while len(A_arr) != 0:
    v_max = A_arr.pop(0)
    C_arr[v_max] -= 1
    v_pair = 2**v_max.bit_length() - v_max
    if C_arr[v_pair] != 0:
        A_arr.remove(v_pair)
        C_arr[v_pair] -= 1
        count += 1
    else:
        pass

print(count)

### FIXED CODE ###

from collections import Counter
N = int(input())
A_arr = list(map(int, input().split()))

A_arr = sorted(A_arr, reverse=True)
C_arr = Counter(A_arr)

count = 0
for i in range(N):
    v_max = A_arr[i]
    if C_arr[v_max] == 0:
        continue
    C_arr[v_max] -= 1
    v_pair = 2**v_max.bit_length() - v_max
    if C_arr[v_pair] > 0:
        C_arr[v_pair] -= 1
        count += 1
    else:
        pass

print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = [list(map(int,input().split())) for _ in range(Q)]
for k in range(Q):    
    A = [B[k][1] if B[k][0]==i else i for i in A]
    print(sum(A))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = [list(map(int,input().split())) for _ in range(Q)]
numList = [0]*(10**5+1)
res=sum(A)
for i in A:
    numList[i] += 1

for i in range(Q):
    dev = B[i][1]-B[i][0]
    res += numList[B[i][0]]*dev
    numList[B[i][1]] +=numList[B[i][0]]
    numList[B[i][0]] = 0
    print(res)
### BUGGY CODE ###

n, k, q = map(int, input().split())
a_list = [int(input()) for i in range(q)]

point_dic = {}
for i in range(n):
    point_dic[i + 1] = k

for a in a_list:
    for i in range(n):
        if i+1 == a:
            pass
        else:
            point_dic[i+1] -= 1

for point in point_dic.values():
    if point > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n, k, q = map(int, input().split())
a_list = [int(input()) for i in range(q)]

point_dic = []
for i in range(n):
    point_dic.append(k-q)

for a in a_list:
    point_dic[a-1] = point_dic[a-1] + 1


for point in point_dic:
    if point > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

S = list(input())
ans = ['1'] * len(S)
# split_num = [0]
# for i, s in enumerate(S[1:-1]):
#     if S[i-1] == "L" and S[i+1] == "R":
#         ans[i] = 0
#         split_num.append(i)
# split_num.append(len(S))
#
# for i in range(len(split_num)-1):
#     pre_ans = [1] * len(S[split_num[i]:split_num[i+1]])
#     for i, s in enumerate(S[split_num[i]:split_num[i+1]]):
#         print(s)

import copy
pre_ans = ['1'] * len(S)
pre_pre_ans = ['1'] * len(S)
flag = 0
# while True:
for k in range(1, 10 ** 100):
    ans[0] = '0'
    ans[-1] = '0'
    if S[1] == 'L':
        ans[0] = pre_ans[1]
    if S[-2] == "R":
        ans[-1] = pre_ans[-2]
    for i, s in enumerate(S[1:-1]):
        ans[i+1] = '0'
        if S[i] == 'R' and S[i+2] == "L":
            ans[i+1] = str(int(pre_ans[i]) + int(pre_ans[i+2]))
        elif S[i] == 'R':
            ans[i+1] = pre_ans[i]
        elif S[i+2] == 'L':
            ans[i+1] = pre_ans[i+2]
    if ans == pre_ans:
        flag = 1
        break
    elif ans == pre_pre_ans:
        if k % 2 == 0:
            flag = 1
        else:
            flag = 2
        break
    pre_pre_ans = copy.deepcopy(pre_ans)
    pre_ans = copy.deepcopy(ans)

if flag == 1:
    print(' '.join(ans))
elif flag == 2:
    print(' '.join(pre_ans))


### FIXED CODE ###

s = input()
tmp = [0]
for i in range(len(s)-1):
    if s[i] != s[i+1]:  # RとLが切り替わる時のインデックスを保存
        tmp.append(i+1)
tmp.append(len(s))
ans = [0 for i in range(len(s))]
for i in range(len(tmp)-1):
    if i % 2 == 1:
        ans[tmp[i]] = (tmp[i]-tmp[i-1])//2 + (tmp[i+1]-tmp[i]+1)//2
        ans[tmp[i]-1] = (tmp[i+1]-tmp[i])//2 + (tmp[i]-tmp[i-1]+1)//2
print(*ans)
# RRLLLLRLRRLL
### BUGGY CODE ###

N=int(input())
S=0
while N>=1:
    S+=N%10
    N=N//10

if S%9==0:print("Yes")
else:print("No")

### FIXED CODE ###

N=int(input())
if N%9==0:print("Yes")
else:print("No")
### BUGGY CODE ###

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

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

def gcd(list1) :
    global dol
    lngt = len(list1)
    list2 = tuple(list1)
    if list2 in dol.keys() :
        return dol[list2]
    elif lngt == 1 :
        return list1[0]
    else :
        rt = ea(gcd(list1[:lngt//2]), gcd(list1[lngt//2:]))
        dol[list2] = rt
        return rt

dol = {}
ans = 1
for n in range(N) :
    ans = max(ans, gcd(Alist[:n]+Alist[n+1:]))
print(ans)

### FIXED CODE ###

from functools import lru_cache
n = int(input())
aa = list(map(int, input().split()))

@lru_cache(maxsize=10**9)
def gcd(a, b) :
    if b == 0 : return a
    elif a%b : return gcd(b, a%b)
    else : return b

l = [0]
r = [0]
for i in range(n) :
    l.append(gcd(l[-1], aa[i]))
    r.append(gcd(r[-1], aa[-i-1]))

m = [gcd(l[i],r[-i-2]) for i in range(n)]
print(max(m))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
p = 10**9+7
f=[1]
for i in range(1,a[0]+1):
  f.append(f[-1] * i)

def nCk(n,k):
  return (f[n] * pow(f[n-k],p-2,p) * pow(f[k],p-2,p)) % p

start = 0
end = -1
ans = 0
for i in range(1,n):
  t = nCk(a[start], a[i])
  if ans < t:
    ans = t
    end = i
print(a[start], a[end])

### FIXED CODE ###

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

t2 = a[0]
x = a[0]//2
ans = 1
for i in range(1,n):
  t = abs(x - a[i])
  if t < t2:
    t2 = t
    ans = i
print(a[0],a[ans])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
M = N - K
A = [0] + LIST()

# dp[i][j] := 列をi個使って、最後に使ったのがj列目の時の最小コスト
dp = list2d(M+1, N+1, INF)
dp[0][0] = 0
for i in range(1, M+1):
    for j, h1 in enumerate(A):
        for k in range(max(j-N, 0), j):
            h2 = A[k]
            dp[i][j] = min(dp[i][j], dp[i-1][k] + max(h1 - h2, 0))
print(min(dp[M]))


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
M = N - K
A = [0] + LIST()

# dp[i][j] := 列をi個使って、最後に使ったのがj列目の時の最小コスト
dp = list2d(M+1, N+1, INF)
dp[0][0] = 0
for i in range(1, M+1):
    for j, h1 in enumerate(A):
        for k in range(max(j-N, 0), j):
            h2 = A[k]
            dp[i][j] = min(dp[i][j], dp[i-1][k] + max(h1 - h2, 0))
print(min(dp[M]))
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
def DP(N,K,A,i):
    Ac=A.copy()
    a_check=Ac.pop(i)
    if a_check>=K:
        return True
    dp=[0]*(K-a_check+1)
    dp[0]=1
    for a in Ac:
        dpc=dp.copy()
        for k in range(K-a_check+1):
            if dpc[k]==0:continue
            else:
                if k+a<K-a_check:
                    dp[k+a]=1
                elif K-a_check<=k+a<K:
                    return True
    return False

def bisect(N,K,A,check,maxFalse,minTrue):
    idx=N*check[0]//check[1]
    if DP(N,K,A,idx)==True:
        if maxFalse==idx-1:
            return maxFalse
        return bisect(N,K,A,(check[0]*2-1,check[1]*2),maxFalse,min(minTrue,idx))
    else:
        if minTrue==idx+1:
            return idx
        return bisect(N,K,A,(check[0]*2+1,check[1]*2),max(maxFalse,idx),minTrue)

print(bisect(N,K,A,(1,2),-1,N)+1)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
S=0
ans=0
for a in A:
    if S+a<K:
        S+=a
        ans+=1
    else:ans=0
print(ans)
### BUGGY CODE ###

N  =int(input())
la = list(map(int,input().split()))
ans = 1
if N == 0:
    print(0)
    exit()
for i in la:
    ans = ans*i

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


### FIXED CODE ###

N  =int(input())
la = list(map(int,input().split()))
ans = 1
if N == 0:
    print(0)
    exit()
if 0 in la:
    print(0)
    exit()
for i in la:
    if ans > 10**18:
        print("-1")
        exit()
    else:
        ans = ans*i
 
if ans > 10**18:
    print("-1")
else:
    print(ans)
### BUGGY CODE ###

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

ans = A

for i in range(A+1, B+1):

    ans = ans ^ i

print(ans)

### FIXED CODE ###

def f(n):
    x = n // 2

    if n % 2 == 0:
        if x % 2 == 0:
            return 0 ^ n
        else:
            return 1 ^ n

    else:
        x += 1
        if x % 2 == 0:
            return 0
        else:
            return 1


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

print(f(A-1) ^ f(B))
### BUGGY CODE ###

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

a_ol = []
a_counts = []
for i in a_uni:
    a_co = a.count(i)
    if a_co > 1:
        a_ol.append(i)
        a_counts.append(a_co)


def_count = sum([i * (i - 1) // 2 for i in a_counts])
for k in range(n):
    count = 0
    if a[k] in a_ol:
        count = def_count - (a_counts[a_ol.index(a[k])] - 1)
    else:
        count = def_count
    print(count)



### FIXED CODE ###

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


a_ol = Counter(a)
def_count = 0
for item in a_ol.items():
    a_co = item[1]
    def_count += a_co * (a_co - 1)

def_count //= 2

for k in a:
    print(def_count - a_ol[k] + 1)
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n,k=nm()
a=nl()
b=[1]*(n+1)

for i in range(n):
  b[i+1] = a[i]*b[i]

for i in range(n-k):
  if b[i+k+1]/b[i+1] > b[i+k]/b[i]:
    print('Yes')
  else:
    print('No')


### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

from math import log10

n,k=nm()
a=nl()
b=[1]*(n+1)

for i in range(n):
  b[i+1] = log10(a[i])+b[i]

for i in range(n-k):
  if b[i+k+1]-b[i+1] > b[i+k]-b[i]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

a,b=map(int,input().split())
l=range(a,b+1)
ans=1
for i in range(len(l)):
  ans=ans*l[i]
if ans>0:
  print("Positive")
elif ans<0:
  print("Negative")
else:
  print("Zero")

### FIXED CODE ###

a,b=map(int,input().split())
if (a>0 and b>0):
	print("Positive")
elif (a>=0 and b<=0) or (a<=0 and b>=0):
	print("Zero")
elif (a<0 and b<0 and (a+b)%2==0):
	print("Negative")
else:
	print("Positive")
### BUGGY CODE ###

s = input()
t = input()
S = len(s)
T = len(t)
dp = [[""]*(S+1) for _ in range(T+1)]

for i in range(T):
    for j in range(S):
        if s[j] == t[i]:
            dp[i+1][j+1] = dp[i][j] + s[j]
        else:
            if len(dp[i+1][j]) >= len(dp[i][j+1]):
                dp[i+1][j+1] = dp[i+1][j]
            else:
                dp[i+1][j+1] = dp[i][j+1]
print(dp[T][S])


### FIXED CODE ###

s = input()
t = input()
S = len(s)
T = len(t)
dp = [[0]*(T+1) for _ in range(S+1)]

for i in range(S):
    for j in range(T):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ""
while S and T:
    if dp[S][T] == dp[S-1][T]:
        S -= 1
    elif dp[S][T] == dp[S][T-1]:
        T -= 1
    else:
        ans = s[S-1]+ans
        S -= 1
        T -= 1
print(ans)
### BUGGY CODE ###

k,s=map(int,input().split())
ans=0
for x in range(k+1):
    if x>s: continue
    for y in range(k+1):
        if x+y>s: continue
        for z in range(k+1):
            if x+y+z == s:
                ans+=1

print(ans)



### FIXED CODE ###

k,s=map(int,input().split())
ans=0

for x in range(k+1):
    for y in range(k+1):
        if s-x-y>=0 and k>=(s-x-y):
            ans+=1
print(ans)
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

S = list(str(input()))
S.reverse()
extra = 0
each_extras = [[] for i in range(S.count("?"))]
cnt = 0
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
        extra %= 13
    else:
        each_extras[cnt] = []
        for x in range(10):
            each_extras[cnt].append(x * 10 ** i % 13)
            # each_extras[cnt][x * 10 ** i % 13] = 1
        cnt += 1

# print(each_extras)

# print(extra)
dp = [[0 for i in range(13)] for j in range(cnt+1)]
dp[0][extra % 13] = 1
for i in range(cnt):
    for extras in each_extras[i]:
        for j in range(13):
            dp[i+1][(extras + j)%13] += dp[i][j]
            dp[i+1][(extras + j)%13] %= mod
    for j in range(13):
        dp[i+1][j] = dp[i+1][j] % mod


# print(dp)
print(dp[-1][5] % mod)

"""
S = list(str(input()))

dp = [[0 for i in range(13)]for j in range(len(S)+1)]
dp[0][0] = 1
S.reverse()
mul = 1
for i in range(len(S)):
    if S[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(mul*j+k)%13] += dp[i][k]
                dp[i+1][(mul*j+k)%13] %= mod
    else:
        for k in range(13):
            dp[i+1][(int(S[i])*mul+k)%13] += dp[i][k]
            dp[i+1][(int(S[i])*mul+k)%13] %= mod
    mul *= 10
    mul %= 13

# print(dp)
print(dp[-1][5])
"""


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))


"""
S.reverse()
extra = 0
each_extras = [[0 for i in range(10)] for i in range(S.count("?"))]
cnt = 0
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
    else:
        each_extras[cnt] = []
        for x in range(10):
            each_extras[cnt].append(x * 10 ** i % 13)
            # each_extras[cnt][x * 10 ** i % 13] = 1
        cnt += 1

# print(each_extras)

# print(extra)
dp = [[0 for i in range(13)] for j in range(cnt+1)]
dp[0][extra % 13] = 1
for i in range(cnt):
    for extras in each_extras[i]:
        for j in range(13):
            dp[i+1][(extras + j)%13] += dp[i][j]
            dp[i+1][(extras + j)%13] %= mod
    for j in range(13):
        dp[i+1][j] = dp[i+1][j] % mod


# print(dp)
print(dp[-1][5] % mod)
"""


S = list(str(input()))

dp = [[0 for i in range(13)]for j in range(len(S)+1)]
dp[0][0] = 1
S.reverse()
mul = 1
for i in range(len(S)):
    if S[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(mul*j+k)%13] += dp[i][k]
                dp[i+1][(mul*j+k)%13] %= mod
    else:
        for k in range(13):
            dp[i+1][(int(S[i])*mul+k)%13] += dp[i][k]
            dp[i+1][(int(S[i])*mul+k)%13] %= mod
    mul *= 10
    mul %= 13

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

n, m = map(int, input().split())
xy = [list(map(int, input().split()[:2])) for i in range(m)]

s = set(sum(xy, []))

for a in xy:
    for b in xy:
        if not a == b:
            for c in b:
                if c in a:
                    a += b
                    xy.remove(b)
                    break

print(n - len(s) + len(xy))


### FIXED CODE ###

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

xy = [i for i in range(n + 1)]


def root(x):
    i = x
    while i != xy[i]:
        i = xy[i]
    xy[x] = i
    return i


for _ in range(m):
    x, y, z = map(int, input().split())
    rx = root(x)
    ry = root(y)
    if rx != ry:
        xy[ry] = rx

ans = -1
for i, v in enumerate(xy):
    if i == v:
        ans += 1

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

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

import bisect
A.sort()
A = [-1] + A
for i in range(M):
    b, c = map(int, input().split())
    idx = bisect.bisect_left(A, c)
    #print(A[:idx], A[idx:])
    A = A[:idx] + [c] * b + A[idx:]
    A = A[-(N+1):]
    #print(A)
print(sum(A[1:]))

### FIXED CODE ###


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

A.sort()

CB = []
for i in range(M):
    B, C = map(int, input().split())
    CB.append([C, B])
    
CB.sort(reverse=True)

idx = 0
c = 0
for i in range(N):
    if A[i] < CB[idx][0]:
        A[i] = CB[idx][0]
        c += 1
    if CB[idx][1] <= c:
        idx += 1
        c = 0
    if idx >= M:
        break
    #print(A)
        
print(sum(A))
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0]*n
for i in list(range(n))[1:]:
    dp[i] = min([dp[max(0, i-ki-1)]+abs(h[i]-h[max(0, i-ki-1)]) for ki in range(k)])
print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0]*n
for i in list(range(n))[1:]:
    tmp = max(0, i-k)
    dp[i] = min([dpk+abs(h[i]-hk) for dpk, hk in zip(dp[tmp:i], h[tmp:i])])
print(dp[-1])
### BUGGY CODE ###

n = int(input())
x = int(input(), 2)
for i in range(n):
    num = x ^ (2 ** (n - 1 - i))
    count = 0
    while num:
        num %= bin(num).count("1")
        count += 1
    print(count)

### FIXED CODE ###

n = int(input())
x = input()
temp = x.count("1")
mod1 = [1]
for i in range(n-1):
    mod1.append(mod1[-1] * 2 % (temp + 1))
mod1.reverse()
num1 = 0
for i in range(n):
    if x[i] == "1":
        num1 += mod1[i]
        num1 %= (temp + 1)
if temp == 1 or temp == 2:
    mod2 = [0] * n
else:
    mod2 = [1]
    for i in range(n-1):
        mod2.append(mod2[-1] * 2 % (temp - 1))
    mod2.reverse()
    num2 = 0
    for i in range(n):
        if x[i] == "1":
            num2 += mod2[i]
            num2 %= (temp - 1)
x2 = int(x, 2)
for i in range(n):
    if x[i] == "1":
        if temp == 1:
            print(0)
            continue
        elif temp == 2:
            print(1)
            continue
        else:
            num = num2 - mod2[i]
            num %= (temp - 1)
    else:
        num = num1 + mod1[i]
        num %= (temp + 1)
    count = 1
    while num:
        num %= bin(num).count("1")
        count += 1
    print(count)
### 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())
L = []
R = []
for i in range(Q):
    l,r = map(int, input().split())
    L.append(l)
    R.append(r)
    
import numpy as np
A = np.array(A)
for i in range(Q):
    MP = 0
    point = L[i]
    aa = np.array(np.where((L[i] <= A) & (A <= R[i]) & ((A - point)%D == 0))).T
    ix = np.argsort(A[aa[:,0],aa[:,1]])
    aa = aa[ix]
    MP = sum([sum(abs(aa[p]-aa[p+1])) for p in range(len(aa)-1)])
    print(MP)

### FIXED CODE ###

import numpy as np
H,W,D = map(int,input().split())
SUM = H*W
px = np.zeros(SUM+1)
py = np.zeros(SUM+1)
for i in range(1,H+1):
    A = list(map(int, input().split()))
    for j in range(len(A)):
        px[A[j]] = i
        py[A[j]] = j + 1

d = np.zeros(SUM+1)
for t in range(D+1,SUM+1):
    d[t] = d[t-D] + abs(px[t] - px[t-D])+ abs (py[t] - py[t-D]);
        
Q = int(input())
L = []
R = []
for i in range(Q): 
    l,r = map(int, input().split())
    print(int(d[r]-d[l]))