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

from collections import deque
import copy
def main():
  n = int(input())
  p = list(map(int, input().split()))
  for i in range(len(p)):
      p[i] -= 1

  to_outsides = [[0 for _ in range(n)] for _ in range(n)]
  not_exist = [["■" for _ in range(n)] for _ in range(n)]


  for i in range(n):
      for j in range(n):
          to_outside = [i,n-1-i,j,n-1-j]
          to_outsides[i][j] = min(to_outside)

  directions = [[-1,0],[1,0],[0,-1],[0,1]]

  all_loss = 0
  answer = 0
  for i, person in enumerate(p):
      exited = [person//n, person%n]
      answer += to_outsides[exited[0]][exited[1]]
      not_exist[exited[0]][exited[1]] = "□"
      seen = []
      seen.append([exited[0],exited[1]])
      todo = deque([exited])
      renews = []
      while len(todo)>0:
          now = todo.pop()
          renews.append(now)
          for direction in directions:
              try:
                  checking = [now[0]+direction[0],now[1]+direction[1]]
                  to_outsides[checking[0]][checking[1]]
              except:
                  continue
              if [checking[0],checking[1]] not in seen and\
              ((not_exist[checking[0]][checking[1]] == "□" and  to_outsides[checking[0]][checking[1]]==to_outsides[now[0]][now[1]])or\
              to_outsides[checking[0]][checking[1]]>to_outsides[now[0]][now[1]]):
                  todo.append([checking[0],checking[1]])
                  seen.append([checking[0],checking[1]])

      for renew in renews:
          if to_outsides[renew[0]][renew[1]] != 0:
              to_outsides[renew[0]][renew[1]]-=1
  print(answer)

main()

### FIXED CODE ###

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

dp = [[min(i, N - i - 1, j, N - j - 1) for j in range(N)] for i in range(N)]

presence = [[1 for j in range(N)] for i in range(N)]

ans = 0
for i in range(len(P)):
    P[i] -= 1
    x, y = divmod(P[i], N)
    ans += dp[x][y]
    presence[x][y] = 0

    Q = [(x, y)]
    #%%
    while Q:
        x, y = Q.pop()
        new_value = dp[x][y] + presence[x][y]
        if 1 <= x and dp[x - 1][y] > new_value:
            dp[x - 1][y] = new_value
            Q.append((x - 1, y))
        if x < N - 1 and dp[x + 1][y] > new_value:
            dp[x + 1][y] = new_value
            Q.append((x + 1, y))
        if 1 <= y and dp[x][y - 1] > new_value:
            dp[x][y - 1] = new_value
            Q.append((x, y - 1))
        if y < N - 1 and dp[x][y + 1] > new_value:
            dp[x][y + 1] = new_value
            Q.append((x, y + 1))

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

import math
S=input()
Q=int(input())
Rev=True
front=''
back=''
for i in range(Q):
    a=input()
    if a=='1':
        Rev=not(Rev)
    else:
        b,c,x=a.split()
        if c == '1':
            if Rev:
                front += x
            else:
                back += x
        else:
            if Rev:
                back += x
            else:
                front += x
if Rev:
    print(front[::-1] + S + back)
else:
    print(back[::-1]+S[::-1]+front)


### FIXED CODE ###

S=input()
Q=int(input())
Rev=True
front=''
back=''
for i in range(Q):
    a=input()
    if a=='1':
        Rev=not(Rev)
    else:
        b,c,x=a.split()
        if c == '1':
            if Rev:
                front += x
            else:
                back += x
        else:
            if Rev:
                back += x
            else:
                front += x
if Rev:
    print(front[::-1] + S + back)
else:
    print(back[::-1]+S[::-1]+front)
### BUGGY CODE ###

from sys import stdin

N = int(stdin.readline())
A = list(map(int, stdin.readline().split()))

ans = 1

for i in range(N):
    if A[i] == 0:
        ans = 0

if ans:
    for i in range(N):
        ans *= A[i]
        if ans > pow(10, 18):
            ans = -1

print(ans)


### FIXED CODE ###

from sys import stdin

N = int(stdin.readline())
A = list(map(int, stdin.readline().split()))

ans = 1

if 0 in A:
    ans = 0

if ans:
    for a in A:
        ans *= a
        if ans > pow(10, 18):
            ans = -1
            break

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

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)


N = int(input())

G = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b, c = [int(_) for _ in input().split()]
    G[a].append((b, c))
    G[b].append((a, c))
Q, K = [int(_) for _ in input().split()]

# make tree
G2 = [-1] * (N + 1)


def f(v, c, p):
    if G2[v] != -1: return
    G2[v] = c

    for nv, nc in G[v]:
        if nv == p: continue
        f(nv, nc + c, v)


f(K, 0, 0)

for i in range(Q):
    x,y = [int(_) for _ in input().split()]
    print(G2[x]+G2[y])


### FIXED CODE ###

import sys
from collections import deque

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

N = int(input())
edges = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b, c = [int(_) for _ in input().split()]
    edges[a].append((b, c))
    edges[b].append((a, c))

L = [-1] * (N + 1)


def w(k):
    que = deque()
    L[k] = 0
    que.append((k, -1))
    while que:
        n, p = que.popleft()
        for nn, nv in edges[n]:
            if nn == p: continue
            L[nn] = L[n] + nv
            que.append((nn, n))


def main():
    q, k = [int(_) for _ in input().split()]
    w(k)
    for i in range(q):
        a, b = [int(_) for _ in input().split()]
        print(L[a] + L[b])

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

def pow_r(x, n):
    if n == 0: 
        return 1
    if n % 2 == 0: 
        return pow_r(x ** 2, n // 2)
    else: 
        return x * pow_r(x ** 2, (n - 1) // 2)


x = int(input())
for a in range(-1000, 1000):
    for b in range(-1000, 1000):
        if x == (pow_r(a, 5)) - (pow_r(b, 5)):
            print(a, b)
            exit()



### FIXED CODE ###

def pow_r(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2, n // 2)
    else:
        return x * pow_r(x ** 2, (n - 1) // 2)


x = int(input())
for a in range(-100, 1000):
    for b in range(-100, 1000):
        if x == (pow_r(a, 5)) - (pow_r(b, 5)):
            print(a, b)
            exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().strip().split())
hs = list(map(int, input().strip().split()))

dp = [0] * n

for i in range(1, n):
    min_cost = 1e9
    costs = [
        dp[i - j] + abs(hs[i] - hs[i - j])
        for j in range(1, min(k + 1, i + 1))
    ]
    dp[i] = min(costs)

print(dp[n - 1])


### FIXED CODE ###

n, k = map(int, input().strip().split())
hs = list(map(int, input().strip().split()))

dp = [0] * n

for i in range(1, n):
    costs = []
    for j in range(1, k + 1):
        if i - j >= 0:
            cost = dp[i - j] + abs(hs[i] - hs[i - j])
            costs.append(cost)
    dp[i] = min(costs)

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

import math
import fractions
import collections
import itertools
from collections import deque
S=input()
N=len(S)
cnt=0
l=[]
"""
cnt=0
p=10**9+7
for i in range(K,N+2):
    cnt=(cnt+((N-i+1)*i)+1)%p
    #print(((N-i+1)*i)+1)
print(cnt)
"""
amari=[0]*(N+1)
num=0
for i in range(N):
    num=num+pow(10,i)*int(S[N-1-i])
    amari[i+1]=num%2019
#print(amari)
c=collections.Counter(amari)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
#for i in range(len(key)):
#    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#xprint(l)
for i in range(len(values)):
    cnt=cnt+(values[i]*(values[i]-1))//2
print(cnt)

### FIXED CODE ###

import math
import fractions
import collections
import itertools
from collections import deque
d=collections.deque()
S=list(input())
N=len(S)
cnt=0

amari=[0]*(N+1)
num=0
for i in range(N):
    d.append(int(S[i]))
#print(d)
for i in range(N):
    n=d.pop()
    num=(num+pow(10,i,2019)*n)%2019
    amari[i+1]=num
#print(amari)
#c=collections.Counter(amari)
#values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
amari.sort()
#for i in range(len(key)):
#    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#xprint(l)
buf=0
#print(amari)
c=collections.Counter(amari)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
#for i in range(len(key)):
#    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#xprint(l)
for i in range(len(values)):
    cnt=cnt+(values[i]*(values[i]-1))//2
print(cnt)
### BUGGY CODE ###

import sys
import bisect
inputs = sys.stdin.readlines()

N, M = map(int, inputs[0].split())
A = sorted(list(map(int, inputs[1].split())))

for _ in range(M):
    tmp = A.pop() // 2
    A.insert(bisect.bisect_left(A, tmp), tmp)
print(sum(A))

### FIXED CODE ###

import sys
inputs = sys.stdin.readlines()

from heapq import heappush, heappop
N, M = map(int, inputs[0].split())
A = list(map(int, inputs[1].split()))

queue = []
for a in A:
    heappush(queue, -a)

for _ in range(M):
    heappush(queue, -(-heappop(queue) // 2))
print(-sum(queue))
### BUGGY CODE ###

#!/usr/bin/env python3
MOD = 1000000007
n, *a = map(int, open(0).read().split())
ans = 0
for i in range(61):
    zero = one = 0
    for x in a:
        if (x>>i)&1: one += 1
        else: zero += 1
    ans += pow(2, i, MOD) * zero * one % MOD
    ans %= MOD
print(ans)


### FIXED CODE ###

MOD = 1000000007
n, *a = map(int, open(0).read().split())

ans = 0
w = 1
for i in range(61):
    zero = one = 0
    for j in range(n):
        if a[j]&1: one += 1
        else: zero += 1
        a[j] >>= 1;
    ans += w * zero * one
    ans %= MOD
    w = w * 2 % MOD
print(ans)
### BUGGY CODE ###

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

N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in range(N)]
kyuyu = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    if c <= L:  # 移動出来ない経路は消す
        roads[a-1][b-1] = c
        roads[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            roads[i][j] = min(roads[i][j], roads[i][k]+roads[k][j])

for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            kyuyu[i][j] = min(kyuyu[i][j], kyuyu[i][k]+kyuyu[k][j])

Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)


### FIXED CODE ###

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


def WF(mat, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
    return mat


N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    roads[a-1][b-1] = c
    roads[b-1][a-1] = c

roads = WF(roads, N)
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1
kyuyu = WF(kyuyu, N)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)
### BUGGY CODE ###

n,q=map(int,raw_input().split())
ans=[0]*n
t=-1
for i in range(q):
    a,v=map(int,raw_input().split())
    ans[a-1]+=v
    if v<0:
        t=-1
    if t==-1:
        t=ans.index(max(ans))
    elif ans[t]<ans[a-1] or (ans[t]==ans[a-1] and t>a-1):
        t=a-1
    print t+1,ans[t]
exit()

### FIXED CODE ###

n,q=map(int,raw_input().split())
ans=[0]*n
key=value=0
for i in range(q):
    a,v=map(int,raw_input().split())
    a-=1
    ans[a]+=v
    if a==key and v<0:
        value=max(ans)
        key=ans.index(value)
    elif ans[a]>value:
        key=a
        value=ans[a]
    elif ans[a]==value and a<key:
        key=a
    print key+1,value
### BUGGY CODE ###

from math import gcd
from functools import reduce

n=int(input())
s=input()

ret=0

for i,x in enumerate(s):
	for j,y in enumerate(s[i+1:],start=i+1):
		if x==y:
			continue
		if i+(j-i)*2 < n :
			z=s[i+(j-i)*2]
			if y!=z!=x:
				ret-=1

dic={}
for x in s:
	if not x in dic: 
		dic[x]=0
	dic[x]+=1

for i,x in dic.items():
	for j,y in dic.items():
		for k,z in dic.items():
			if i<j<k:
				ret+=x*y*z
print(ret)


### FIXED CODE ###

from math import gcd
from functools import reduce
 
n=int(input())
s=input()
 
ret=0
 
for i,x in enumerate(s):
	for j,y in enumerate(s[i+1:],start=i+1):
		if x==y:
			continue
		if i+(j-i)*2 < n :
			z=s[i+(j-i)*2]
			if y!=z!=x:
				ret-=1
 
dic={}
for x in s:
	if not x in dic: 
		dic[x]=0
	dic[x]+=1
 
for i,x in dic.items():
	for j,y in dic.items():
		for k,z in dic.items():
			if i<j<k:
				ret+=x*y*z
print(ret)
### BUGGY CODE ###

class Max_Bit:
    """区間の最大値のＢＩＴ

    viの更新をする。
    v1からｖiまでの最大値を取得する。
    どちらもO(logn)時間にできる

    Attributes:
        size (int): BITのサイズ
        tree (list of int): 区間の最大値を管理するための二分木
    """
    def __init__(self, n):
        """
        Args:
            n(int): BITのサイズ
        """
        self.size = n
        self.tree = [0] * (n + 1)

    def get_max(self, i=None):
        if i is None:
            i = self.size
        m = -(10 ** 18)  # -INF
        while i > 0:
            m = max(m, self.tree[i])
            i -= i & -i
        return m

    def update(self, i, x):
        while i <= self.size:
            self.tree[i] = max(x, self.tree[i])
            i += i & -i

N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = Max_Bit(N)
for i in range(N):
    dp.update(i+1,A[i])
for i in range(2,N + 1):
    mask = []
    for j in range(1, i):
        if H[i-1] >= H[j-1]:
            mask.append(j)
    if mask:
        dp.update(i, max([dp.tree[k] for k in mask]) + A[i-1])
print(dp.get_max())

### FIXED CODE ###

class Max_Bit:
    """区間の最大値のＢＩＴ

    viの更新をする。
    v1からｖiまでの最大値を取得する。
    どちらもO(logn)時間にできる

    Attributes:
        size (int): BITのサイズ
        tree (list of int): 区間の最大値を管理するための二分木
    """
    def __init__(self, n):
        """
        Args:
            n(int): BITのサイズ
        """
        self.size = n
        self.tree = [0] * (n + 1)

    def get_max(self, i=None):
        if i is None:
            i = self.size
        m = 0  # -INF
        while i > 0:
            m = max(m, self.tree[i])
            i -= i & -i
        return m

    def update(self, i, x):
        while i <= self.size:
            self.tree[i] = max(x, self.tree[i])
            i += i & -i
def main():
    """
    dp: 花iを使うとした場合の1からiまでつかった美しさの最大値
    短い花から更新する

    """
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    dp = Max_Bit(N)
    sort_H_i = sorted((h, i) for i, h in enumerate(H))
    for h, i in sort_H_i:
        dp.update(i+1,dp.get_max(i) + A[i])
    print(dp.get_max())

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

a,b=map(int,input().split())
i=0
while i <= 10000:

    if a==int(i*0.08) and b==int(i*0.1):
        print(i)
print(-1)

### FIXED CODE ###

import sys
a,b=map(int,input().split())
i=0
while i <= 10000:
    c=int(i*0.08)
    d=int(i*0.1)
    if c==a and d==b:

        print(i)
        sys.exit()
    i+=1

print(-1)
### BUGGY CODE ###

n = input()
l = [int(e) for e in input().split(" ")]
res = 1
for e in l:
    res = res*e
if res > 1e+18:
    print("-1")
else:
    print(res)

### FIXED CODE ###

from operator import mul
from functools import reduce
n = input()
tmp = input().split(" ")
l = sorted([int(e) for e in tmp])
def solve():
    res = 1
    for e in l:
        res = e*res
        if res > 1e+18:
            print("-1")
            return
    print(res)
solve()
### BUGGY CODE ###

s=input()
k=int(input())
lis=set()
for i in range(len(s)+1):
    for j in range(i+1,len(s)+1):
        lis.add(s[i:j])
lis=list(lis)
lis.sort()
print(lis[k-1])

### FIXED CODE ###

s=input()
k=int(input())
lis=set()
for i in range(len(s)+1):
    for j in range(i+1,min(i+100,len(s)+1)):
        lis.add(s[i:j])
lis=list(lis)
lis.sort()
print(lis[k-1])
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
r, g, b = 0, 0, 0
ans = 0

for r in range(N//R+1, -1, -1):
    Rr = R*r
    for g in range(N//G+1, -1, -1):
        Gg = G*g
        b = (N-Rr-Gg)/B
        if b >= 0 and b.is_integer():
            ans += 1

print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
r, g, b = 0, 0, 0
ans = 0
 
for r in range(N//R+1):
    Rr = R*r
    for g in range(N//G+1):
        Gg = G*g
        Bb = N-Rr-Gg

        if Bb < 0:
            break
        if Bb%B == 0:
            ans += 1
 
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
MIN = float('inf')
for i in range(N):
  left = S[:i].count('W')
  right = S[i+1:].count('E')
  MIN = min(left+right,MIN)
print(MIN)
  

### FIXED CODE ###

N = int(input())
S = input()
left = 1 if S[0] == 'W' else 0
right = S[1:].count('E')
MIN =  right 
for i in range(1,N):
  if S[i] == 'W':
    MIN = min(MIN,left+right)
    left += 1
  else:
    MIN = min(MIN,left+right)
    right -= 1
  
  if i==N-1:
    MIN = min(MIN,S[:i].count('W'))

print(MIN)
### BUGGY CODE ###

num = int(input())
wr = str(input())

wr_list = list(wr)
i_counts = []
for i in range(num):
  w_counts = 0
  r_counts = 0
  for j in range(num):
    if i > j and wr_list[j] == "W":
      w_counts += 1
    elif i < j and wr_list[j] == "R":
      r_counts += 1
  i_count = max(w_counts, r_counts)
  i_counts.append(i_count)

ans = min(i_counts)
print(ans)

### FIXED CODE ###

num = int(input())
wr = str(input())

r_num = wr.count("R")
i_counts = [r_num]
rw_count = r_num
wr_count = 0
for i in range(num):
  if wr[i] == "W":
    wr_count += 1
  else:
    rw_count -= 1
  i_count = max(wr_count, rw_count)
  i_counts.append(i_count)

ans = min(i_counts)

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

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N = I()
S = S()

def check(i, j, k):
    return j-i != k-j

chars = list(S)

cnt = 0

for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if not check(i, j, k):
                continue
            if chars[i] == chars[j] or chars[j] == chars[k]:
                continue
            if chars[i] != chars[j] and chars[i] != chars[k] and chars[j] != chars[k]:
                cnt += 1

print(cnt)

### FIXED CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N = I()
S = S()


def check(i, j, k):
    return j-i != k-j

chars = list(S)
cnts = Counter(chars)

cnt = 0

for i in range(N):
    for j in range(i+1, N):
        k = j + j - i
        if k > N-1:
            continue
        if chars[i] != chars[j] and chars[i] != chars[k] and chars[j] != chars[k]:
                cnt += 1

print(cnts["R"] * cnts["G"] * cnts["B"] - cnt)
### BUGGY CODE ###

n = int(input())

a = list(int(i) for i in input().split())
b = [i for i in a]


def solve(cnt,A,N):
    for i in range(1, N):
        if sum(A[0:i])>0:
            if sum(A[0:i+1])>=0:
                r = A[i]
                A[i]=-sum(A[0:i])-1
                cnt+=abs(r-A[i])
        else:
            if sum(A[0:i+1])<=0:
                r = A[i]
                A[i]=-sum(A[0:i])+1
                cnt+=abs(r-A[i])
    return cnt

cnt1=0
if b[0]<=0:
    ini=b[0]
    b[0]=1
    cnt1=abs(1-ini)


ans1=solve(cnt1,b,n)
cnt2=0
if a[0]>=0:
    ini=a[0]
    a[0]=-1
    cnt2=abs(-1-ini)


ans2=solve(cnt2,a,n)
print(min(ans1,ans2))


### FIXED CODE ###

n = int(input())

a = list(map(int,input().split()))
b = [i for i in a]


def solve(cnt,A,N):
    sumA=A[0]
    for i in range(1, N):
        if sumA>0:
            if sumA+A[i]>=0:
                r = A[i]
                A[i]=-sumA-1
                cnt+=abs(r-A[i])
        else:
            if sumA+A[i]<=0:
                r = A[i]
                A[i]=-sumA+1
                cnt+=abs(r-A[i])

        sumA+=A[i]
    return cnt

cnt1=0
if b[0]<=0:
    ini=b[0]
    b[0]=1
    cnt1=abs(1-ini)


ans1=solve(cnt1,b,n)
cnt2=0
if a[0]>=0:
    ini=a[0]
    a[0]=-1
    cnt2=abs(-1-ini)


ans2=solve(cnt2,a,n)

print(min(ans1,ans2))
### BUGGY CODE ###

import sys
from heapq import heappush, heappop
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    events = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        events.append((t - x, 0, x))
        events.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        events.append((d, 2, -1))
    events.sort(key=itemgetter(0, 1))
    
    pos_set = set()
    pos_hq = []
    ans = []
    for _, com, pos in events:
        if com == 0:
            pos_set.remove(pos)
        elif com == 1:
            pos_set.add(pos)
            heappush(pos_hq, pos)
        else:
            while pos_hq:
                if pos_hq[0] not in pos_set:
                    heappop(pos_hq)
                else:
                    break
            ans.append(pos_hq[0] if pos_hq else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import heapq as hq
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    event = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        event.append((t - x, 0, x))
        event.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        event.append((d, 2, -1))
    event.sort(key=itemgetter(0, 1))
    
    pos_set = set()
    pos_hq = []
    ans = []
    for _, com, pos in event:
        if com == 0:
            pos_set.remove(pos)
        elif com == 1:
            pos_set.add(pos)
            hq.heappush(pos_hq, pos)
        else:
            while pos_hq:
                if pos_hq[0] not in pos_set:
                    hq.heappop(pos_hq)
                else:
                    break
            ans.append(pos_hq[0] if pos_hq else -1)
    print(*ans, sep='\n')


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

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

x = [[0 for j in range(N + 1)] for i in range(N + 1)]
c = [[0 for j in range(N + 1)] for i in range(N + 1)]

for _ in range(M):
    L, R = map(int, input().split())
    x[L][R] += 1

for i in range(1, N + 1):
    for j in range(1, N + 1):
        c[i][j] = sum(x[i][k] for k in range(1, j + 1))

for _ in range(Q):
    p, q = map(int, input().split())
    print(sum(c[i][q] - c[i][p - 1] for i in range(p, q + 1)))



### FIXED CODE ###

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

x = [[0 for j in range(N + 1)] for i in range(N + 1)]

for _ in range(M):
    L, R = map(int, input().split())
    x[N - L][R] += 1

for i in range(1, N + 1):
    for j in range(1, N + 1):
        x[i][j] += x[i][j - 1]

for j in range(1, N + 1):
    for i in range(1, N + 1):
        x[i][j] += x[i - 1][j]

for _ in range(Q):
    p, q = map(int, input().split())
    print(x[N - p][q])