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

import sys
from heapq import merge
N, M = map(int, sys.stdin.readline().split())
A = sorted([-i for i in list(map(int, sys.stdin.readline().split()))])
BC = sorted([list(map(int, sys.stdin.readline().split())) for _ in range(M)], key=lambda x: x[1], reverse=True)

card_list1 = []
for i in range(M):
    tmp_list = [-1 * BC[i][1]] * BC[i][0] 
    card_list1.extend(tmp_list)

sorted_cards = list(merge(A, card_list1))
ans = sum(sorted_cards[:N]) * -1
print(ans)

### FIXED CODE ###

import sys
N, M = map(int, sys.stdin.readline().split())
A = [[1, i] for i in list(map(int, sys.stdin.readline().split()))]
BC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

card_list = A + BC
sorted_cards = sorted(card_list, key=lambda x: x[1], reverse=True)
n = 0
cards_sum = 0
for i in range(N):
    if sorted_cards[i][0] + n <= N:
        cards_sum += sorted_cards[i][1] * sorted_cards[i][0]
        n += sorted_cards[i][0]
    elif n < N and sorted_cards[i][0] + n > N:
        cards_sum += sorted_cards[i][1] * (N - n)
        n = N
        break
    else:
        break

print(cards_sum)
### BUGGY CODE ###

q = int(input())
for _ in range(q):
    x = input()
    y = input()
    m = len(x)
    n = len(y)
    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        tmp = x[i - 1]
        for j in range(1, n + 1):
            if tmp == y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            elif c[i - 1][j] >= c[i][j - 1]:
                c[i][j] = c[i - 1][j]
            else:
                c[i][j] = c[i][j - 1]
    print(c[m][n])


### FIXED CODE ###

def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [0] * (n + 1)
    for i in range(m):
        tmp = x[i]
        c_ = c[:]
        for j in range(n):
            if tmp == y[j]:
                c[j + 1] = c_[j] + 1
            elif c[j + 1] < c[j]:
                c[j + 1] = c[j]
    return c[-1]


q = int(input())
ans = []
for _ in range(q):
    x = input()
    y = input()
    ans.append(lcs(x, y))

print(*ans, sep="\n")
### BUGGY CODE ###

#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"; exit $?
exit 0
'''
import sys

def _i(): return int(sys.stdin.readline().strip())
def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

# read input
h,w = _ia()
ab = []
for _ in range(h): ab.append(_ia())
for i in range(h):
    r = ab[i]
    for j,bj in enumerate(_ia()):
        r[j] = abs(r[j] - bj)
    t = max(r)

# initialize
dp = [[None for _ in range(w)] for _ in range(h)]
dp[0][0] = {ab[0][0]}
for ij in range(1,h+w-1):
    for i in range(min(ij+1,h)):
        j = ij - i
        if j>=w: continue
        #
        x = ab[i][j]
        nxt = dp[i][j] = set()
        if i==0: ref= dp[i][j-1]
        elif j==0: ref = dp[i-1][j]
        else: ref = dp[i][j-1] | dp[i-1][j]
        #
        im = 0
        for idx in ref: nxt|= {abs(idx-x),idx+x}
            
# stdout
ref=dp[h-1][w-1]
print(min(ref))


### FIXED CODE ###

#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"; exit $?
exit 0
'''
import sys

def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

# read input
h,w = _ia()
ab = []
for _ in range(h): ab.append(_ia())
for i in range(h):
    r = ab[i]
    for j,bj in enumerate(_ia()):
        r[j] = abs(r[j] - bj)
    t = max(r)

# initialize
dp = [[None for _ in range(w)] for _ in range(h)]
dp[0][0] = {ab[0][0]}
hw1 = h + w - 1
for ij in range(1,hw1):
    iend = ( hw1 - ij ) * 80
    for i in range(min(ij+1,h)):
        j = ij - i
        if j>=w: continue
        #
        ref = set()
        if i>0: ref|= dp[i-1][j]
        if j>0: ref|= dp[i][j-1]
        #
        x = ab[i][j]
        nxt = dp[i][j] = set()
        for idx in ref:
            ix = abs(idx-x)
            if ix<=iend: nxt.add(ix)
            ix = idx + x
            if ix<=iend: nxt.add(ix)
            
# stdout
print(min(dp[h-1][w-1]))
### BUGGY CODE ###

n = int(input())
i = 0
while True:
    ans = 0
    for j in range(len(str(bin(i)))-2):
        if i & 1 << j:
            ans += (-2)**j
    if ans == n:
        print(bin(i)[2:])
        break
    i += 1

### FIXED CODE ###

def conv(s):
    s = list(s)
    s.reverse()
    ret = 0
    for i in range(len(s)):
        ret += int(s[i]) * (-2)**i
    return ret

n = int(input())
if n == 0:
    print(0)
    exit()

s = ''
d = 2
while abs(n) > 0:
    if n % d == 0:
        s = '0' + s
    else:
        s = '1' + s
    n -= conv(s[0]+'0'*(len(s)-1))
    d *= 2

print(s)
### BUGGY CODE ###

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

flag = 0
for i in range(m):
    if t[i] in d:
        d.remove(t[i])
    else:
        flag = 1
        break

if flag == 0:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

from collections import deque
n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))
a = deque(sorted(d))
b = deque(sorted(t))
flag = 0
if n >= m:
    for i in range(n):
        if a[0] == b[0]:
            b.popleft()
        a.popleft()
        if len(b) == 0:
            print("YES")
            flag = 1
            break
if flag == 0:
    print("NO")
### BUGGY CODE ###

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

counter = 0

for x in range(K + 1):
    for y in range(K + 1):
        for z in range(K + 1):
            if x + y + z == S:
                counter += 1

print(counter)

### FIXED CODE ###

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

counter = 0

for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        if 0 <= z <= K:
            counter += 1

print(counter)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

A_minus_i = [A[i] - (i+1) for i in range(N)]

min_score = sum(A_minus_i)

scores = []

for i in range(min(A_minus_i), max(A_minus_i)+1):
    score = sum([abs(a - i) for a in A_minus_i])
    scores.append(score)

print(min(scores))


### FIXED CODE ###

import numpy as np
import statistics

N = int(input())
A = [int(i) for i in input().split()]

A_minus_i = [A[i] - (i+1) for i in range(N)]

# print(A)
# print(A_minus_i)

bf = statistics.median(A_minus_i)
# print(bf)

# b_l = int(bf)+1
# b_m = int(bf)
# b_s = int(bf)-1
#
# score_l = sum([abs(a - b_l) for a in A_minus_i])
# score_m = sum([abs(a - b_m) for a in A_minus_i])
# score_s = sum([abs(a - b_s) for a in A_minus_i])

score = sum([abs(a - bf) for a in A_minus_i])

print(int(score))
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
h = [int(x) for x in input().split()]
dp = [np.Infinity] * N
dp[0] = 0
for i in range(1, N):
    for j in range(1, K+1):
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i-j]))
print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(x) for x in input().split()]
dp = [10**10] * N
dp[0] = 0
for i in range(1, N):
    for j in range(1, K+1):
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i-j]))
print(dp[-1])
### BUGGY CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
n,m=map(int,input().split())
E=[]
for _ in range(m):
  E.append(tuple(int(i) for i in input().split()))
q=int(input())
Q=[]
for _ in range(q):
  Q.append(tuple(int(i) for i in input().split()))

DP=[[[0]*2 for i in range(n)] for j in range(11)]
for i in range(q):
  v,d,c=Q[i]
  DP[d][v-1][0]=i+1
  DP[d][v-1][1]=c

for d in range(10)[::-1]:
  for v in range(n):
    if DP[d+1][v][0]>DP[d][v][0]:
      DP[d][v]=DP[d+1][v]
  for e in range(m):
    a,b=E[e]
    a-=1
    b-=1
    if DP[d+1][a][0]>DP[d][b][0]:
      DP[d][b]=DP[d+1][a]
    if DP[d+1][b][0]>DP[d][a][0]:
      DP[d][a]=DP[d+1][b]
for i in range(n):
  print(DP[0][i][1])




### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
n,m=map(int,input().split())
E=[]
for _ in range(m):
  E.append(tuple(int(i) for i in input().split()))
q=int(input())
Q=[]
for _ in range(q):
  Q.append(tuple(int(i) for i in input().split()))

DP=[[[0]*2 for i in range(n)] for j in range(11)]
for i in range(q):
  v,d,c=Q[i]
  DP[d][v-1][0]=i+1
  DP[d][v-1][1]=c

for d in range(10)[::-1]:
  for v in range(n):
    if DP[d+1][v][0]>DP[d][v][0]:
      DP[d][v]=DP[d+1][v]
  for e in range(m):
    a,b=E[e]
    a-=1
    b-=1
    if DP[d+1][a][0]>DP[d][b][0]:
      DP[d][b]=DP[d+1][a]
    if DP[d+1][b][0]>DP[d][a][0]:
      DP[d][a]=DP[d+1][b]
for i in range(n):
  print(DP[0][i][1])
### BUGGY CODE ###

n,t,*a=map(int,open(0).read().split())
amin = [10**9+1] + [0]*n
amax = [0]*(n+1)
for i,x in enumerate(a):
	amin[i+1] = min(amin[i],x)
for i,x in enumerate(a[::-1]):
	amax[i+1] = max(amax[i],x)
d = max(i-j for i,j in zip(amax[-2::-1], amin[1:]))
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(n):
	for j in range(n):
		if a[i]-a[j]==d:
			dp[i+1][j+1] = dp[i][j] + 1
		else:
			dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
print(dp[-1][-1])

### FIXED CODE ###

from itertools import*;_,a=open(0);*a,=map(int,a.split());c=[x-y for x,y in zip(a,accumulate(a,min))];print(c.count(max(c)))
### BUGGY CODE ###

import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data)

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

_ = I()
xs = list(S())


rs, gs, bs = [], [], []
for i, x in enumerate(xs, 1):
    if x == 'R':
        rs.append(i)
    if x == 'G':
        gs.append(i)
    if x == 'B':
        bs.append(i)

ans = 0
seen = D(lambda: False)
s = sorted([rs, gs, bs], key=lambda x: len(x))
for a in s[0]:
    for b in s[1]:
        ans += len(s[2])

        if a < b:
            i, j = a, b
        else:
            j, i = a, b

        if i - (j-i) in s[2]:
            if not seen[(i - (j-i), i, j)]:
                ans -= 1
                seen[(i - (j-i), i, j)] = True
        if j + (j-i) in s[2]:
            if not seen[(i, j, j+(j-i))]:
                ans -= 1
                seen[(i, j, j+(j-i))] = True
        if (i+j)/2 in s[2]:
            if not seen[(i, (i+j)/2, j)]:
                ans -= 1
                seen[(i, (i+j)/2, j)] = True

print(ans)

### FIXED CODE ###

import sys
from math import ceil as C, floor as F, sqrt, gcd as G
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ
from operator import mul

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data) 

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def prod(list): return R(mul, list, 1)
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

n = I()
rgb = S()

cnt = CNT(list(rgb))
ans = prod([cnt[c] for c in ['R', 'G', 'B']])

for i, r in enumerate(rgb):
    for j, g in enumerate(rgb[i+1:], start=i+1):
        k = j + (j - i)
        if k < len(rgb):
            if r != g and g != rgb[k] and r != rgb[k]:
                ans -= 1

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

def permutations(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutations(data):
                ret.append([i] + j)

        return ret
        

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

bou = [1] * N
ball = [2] * (M-1)

junretsu = permutations(bou + ball)

a, b, c, d = [], [], [], []
for i in range(Q):
    A, B, C, D = map(int, input().split())
    a.append(A)
    b.append(B)
    c.append(C)
    d.append(D)

#print(junretsu)
ans = 0
for i in range(len(junretsu)):
    souwa = 0
    check = 0
    A = []
    for j in range(N+M-1):
        if junretsu[i][j] == 1:
            A.append(j - check + 1)
            check += 1
    #print(A)
    for j in range(Q):
        if (A[b[j]-1] - A[a[j]-1]) == c[j]:
            souwa += d[j]
    
    ans = max(ans, souwa)

print(ans)

### FIXED CODE ###

def permutations(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutations(data):
                ret.append([i] + j)

        return ret
        

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

bou = [1] * N
ball = [2] * (M-1)

junretsu = permutations(bou + ball)

a, b, c, d = [], [], [], []
for i in range(Q):
    A, B, C, D = map(int, input().split())
    a.append(A)
    b.append(B)
    c.append(C)
    d.append(D)

ans = 0
for i in range(len(junretsu)):
    souwa = 0
    check = 0
    A = []
    for j in range(N+M-1):
        if junretsu[i][j] == 1:
            A.append(j - check + 1)
            check += 1
    for j in range(Q):
        if (A[b[j]-1] - A[a[j]-1]) == c[j]:
            souwa += d[j]
    
    ans = max(ans, souwa)

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

n = int(input())
xy = [list(map(int,input().split()))for _ in range(n)]

xsort = sorted(xy,key=lambda x:x[0])
ysort = sorted(xy,key=lambda x:x[1])

ans = 0
for i in range(min(n,10**4)):
    for j in range(min(n,10**4)):
        ans = max(ans,abs(xsort[i][0]-xsort[-j][0])+abs(xsort[i][1]-xsort[-j][1]))
        ans = max(ans,abs(ysort[i][0]-ysort[-j][0])+abs(ysort[i][1]-ysort[-j][1]))
print(ans)

### FIXED CODE ###

n = int(input())
xy = [list(map(int,input().split()))for _ in range(n)]

iti = -float("inf")
ni = -float("inf")
san = -float("inf")
yon = -float("inf")
for x,y in xy:
    iti = max(iti,x+y)
    ni = max(ni,x-y)
    san = max(san,-x+y)
    yon = max(yon,-x-y)

print(max(iti+yon,ni+san))
### BUGGY CODE ###

#!/usr/bin/env python
from collections import defaultdict
import math
import re
import bisect

def main():
    #A, B, C, D = map(int, input().split())
    N = int(input())
    diff_list = []
    for i in range(N):
        A, B = map(int, input().split())
        bisect.insort_left(diff_list, (B, A))

    t = 0
    for i in range(N):
        B, A = diff_list[i]
        t += A
        if t > B:
            print("No")
            return

    print("Yes")

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
from collections import defaultdict
import math
import re
import bisect

def main():
    #A, B, C, D = map(int, input().split())
    N = int(input())
    diff_list = []
    for i in range(N):
        A, B = map(int, input().split())
        diff_list.append((B, A))

    diff_list = sorted(diff_list, key=lambda x: x[0])

    t = 0
    for i in range(N):
        B, A = diff_list[i]
        t += A
        if t > B:
            print("No")
            return

    print("Yes")

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

def main():
    _, K = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()
    MOD = 10 ** 9 + 7
    ans = 1

    if K % 2 == 1 and A[-1] < 0:
        for i in range(K):
            ans *= A[-(i + 1)]

        ans = ans % MOD
        print(ans)
        return

    l = 0
    r = 1
    if K % 2 == 1:
        ans = ans * A[-r]
        r += 1
    
    for _ in range(K // 2):
        ml = A[l] * A[l + 1]
        mr = A[-r] * A[-(r + 1)]
        if ml > mr:
            ans = ans * ml % MOD
            l += 2
        else:
            ans = ans * mr % MOD
            r += 2

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()
    MOD = 10 ** 9 + 7
    ans = 1

    if K % 2 == 1 and A[-1] < 0:
        for i in range(K):
            ans = ans * A[N - (i + 1)] % MOD

        print(ans)
        return

    l = 0
    r = N - 1
    if K % 2 == 1:
        ans = ans * A[r]
        r -= 1
    
    for _ in range(K // 2):
        ml = A[l] * A[l + 1]
        mr = A[r] * A[r - 1]
        if ml > mr:
            ans = ans * ml % MOD
            l += 2
        else:
            ans = ans * mr % MOD
            r -= 2

    print(ans)
    return


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

import copy
n = int(input())
ls = []
for i in range(n):
    a = int(input())
    ls.append(a) 
    
for i in range(len(ls)):
    ls2 = copy.copy(ls)
    del ls2[i]
    ls2 = sorted(ls2)
    print(ls2[-1])
    

### FIXED CODE ###

import copy
n = int(input())
ls = []
for i in range(n):
    a = int(input())
    ls.append(a) 
ls2 = copy.copy(ls)
ls.sort()
max1 = ls[-1]
max2 = ls[-2]


for i in ls2:
    if i != max1:
        print(max1)
    else:
        print(max2)
### BUGGY CODE ###

def makeRelation():
  for n in range(1,N+1):
    visited=set((n,))
    D[n].add(n)
    while visited:
      v=visited.pop()
      for i in F[v]:
        if i not in D[n]:
          visited.add(i)
          D[n].add(i)
    for i in D[n]:
      D[i]|=D[n]


def main():
  makeRelation()
  #print(D)
  ans=[0]*(N+1)
  for n in range(1, N+1):
  	ans[n]=len(D[n]) - len(F[n]) - len(D[n]&B[n]) - 1
  print(*ans[1:])


if __name__=='__main__':
  N, M, K = map(int, input().split())
  F=[set() for n in range(N+1)]
  AB=[list(map(int, input().split())) for m in range(M)]
  for a,b in AB:
    F[a].add(b)
    F[b].add(a)
  B=[set() for n in range(N+1)]
  CD=[list(map(int, input().split())) for k in range(K)]
  for c,d in CD:
    B[c].add(d)
    B[d].add(c)
  D=[set() for n in range(N+1)]
  #print(F)
  #print(B)
  main()

### FIXED CODE ###

def makeRelation():
  visited=[False]*(N+1)
  g=0 # group
  for n in range(1,N+1):
    if visited[n]:
      continue
    q={n}
    D.append(set())
    while q:
      j=q.pop()
      for i in F[j]: # search for friend
        if not visited[i]:
          visited[i]=True
          q.add(i)
          D[g]|={i}
    g+=1
    
def main():
  makeRelation()
  #print(D)
  for g in D:
    for d in g:
      ans[d]=len(g) - len(F[d]) - len(g&B[d]) - 1
  print(*ans[1:])


if __name__=='__main__':
  N, M, K = map(int, input().split())
  F=[set() for n in range(N+1)]
  AB=[list(map(int, input().split())) for m in range(M)]
  for a,b in AB:
    F[a].add(b)
    F[b].add(a)
  B=[set() for n in range(N+1)]
  CD=[list(map(int, input().split())) for k in range(K)]
  for c,d in CD:
    B[c].add(d)
    B[d].add(c)
  D=[]
  #print(F)
  #print(B)
  ans=[0]*(N+1)
  main()
### BUGGY CODE ###

import numpy as np
import sys
buf = sys.stdin.buffer

N = int(buf.readline())
M = N // 2 + 1
P = np.array(buf.readline().split(),dtype = float)
#print(P)
dp = np.zeros([N + 1,N + 1])
dp[0][0] = 1.0

for i in range(N):
  for j in range(i + 1):
    #print(P[i])
    dp[i + 1][j + 1] += dp[i][j] * P[i]
    dp[i + 1][j] += dp[i][j] * (1 - P[i])

print(sum(dp[-1][M:]))

### FIXED CODE ###

import numpy as np
import sys
buf = sys.stdin.buffer

N = int(buf.readline())
M = N // 2 + 1
P = np.array(buf.readline().split(),dtype = float)

dp = np.zeros([(N + 1),(N + 1)])
dp[0][0] = 1.0

for i in range(N):
  tmp = dp[i].copy()
  dp[i + 1] = tmp * (1 - P[i])
  tmp = np.roll(tmp,1)
  dp[i + 1] += tmp * P[i] 
  
print(sum(dp[-1][M:]))
### BUGGY CODE ###

N,Q=map(int,input().split())
import sys
def input(): return sys.stdin.readline().strip()
STX=[list(map(int,input().split())) for i in range(N)]
D=[(int(input()),i) for i in range(Q)]
X=sorted([(s-x,t-x,x) for s,t,x in STX],key=lambda x:(x[2],x[0]))
from bisect import bisect
a=[-1]*Q
for x in X:
    s=bisect(D,(x[0],-1))
    e=bisect(D,(x[1],-1))
    if s!=e:
        for i in range(s,e):
            a[D[i][1]]=x[2]
        D=D[:s]+D[e:]
for l in a:
    print(l)

### FIXED CODE ###

N,Q=map(int,input().split())
import sys
def input(): return sys.stdin.readline().strip()
STX=[list(map(int,input().split())) for i in range(N)]
D=[int(input()) for i in range(Q)]
X=[]
for s,t,x in STX:
    X.append((s-x,1,x))
    X.append((t-x,-1,x))
X.sort(key=lambda x:x[0])
a=0
k=[]
from heapq import heappop,heappush
kd={}
for x in X:
    while a<Q and D[a]<x[0]:
        if len(k)>0:
            print(k[0])
        else:
            print(-1)
        a+=1
    if x[1]==1:
        heappush(k,x[2])
        if x[2] in kd:
            kd[x[2]]=0
    else:
        kd[x[2]]=1
        while len(k)>0 and k[0] in kd and kd[k[0]]==1:
            heappop(k)
while a<Q:
    print(-1)
    a+=1
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split(' ')]
def score(C, b):
    s = 0
    for i, Ci in enumerate(C):
        s += abs(Ci - b)
    return s

C = [Ai - (i+1) for i, Ai in enumerate(A)]
min_b = min(C)
max_b = max(C)
if min_b == max_b:
    print(0)
else:
    s = float('inf')
    for b in range(min_b, max_b):
        si = score(C, b)
        if si < s:
            s = si
    print(s)

### FIXED CODE ###

import statistics
N = int(input())
A = [int(x) for x in input().split(' ')]
def score(C, b):
    s = 0
    for i, Ci in enumerate(C):
        s += abs(Ci - b)
    return int(s)

C = [Ai - (i+1) for i, Ai in enumerate(A)]
b = statistics.median(C)
b1 = int(b)
b2 = int(b) + 1
s1 = score(C, b1)
s2 = score(C, b2)
print(min(s1, s2))
### BUGGY CODE ###

import sys
import math
import itertools
import collections
from collections import deque
 
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
 
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
 
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def main():
    A, B = NMI()
    GCD = math.gcd(A, B)
    
    if A == 1 or B == 1:
      print(1)
    else:
      
      cnt = 0
      for n in get_sieve_of_eratosthenes(GCD):
          if GCD % n == 0:
              cnt += 1
      print(cnt+1)

    
 
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import math
import itertools
import collections
from collections import deque
 
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
 
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
 
def main():
    A, B = NMI()
    GCD = math.gcd(A, B)
    N=GCD
    
    cnt = 0
    
    ls=[]
    
    for n in range(2,int(N**0.5)+2):
 
        if GCD % n == 0:
            cnt += 1
 
            while GCD % n == 0:
                GCD = GCD//n
                ls.append(n)
        
    if GCD == 1:
        print(cnt+1)
    else:
        print(cnt+2) 

if __name__ == '__main__':
    main()