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

import numpy as np

N, M = [int(i) for i in input().strip().split()]
A = [int(i) for i in input().strip().split()]
B = [0] * M
C = [0] * M
for i in range(M):
    B[i], C[i] = [int(i) for i in input().strip().split()]

A = np.array(A)
for i in range(M):
    A.sort()
    for j in range(0, B[i]):
        if A[j] < C[i]:
            A[j] = C[i]
        else:
            break
print(sum(A))


### FIXED CODE ###

N, M = [int(i) for i in input().strip().split()]
A = [int(i) for i in input().strip().split()]
A.sort()

BC = [[0, 0] for _ in range(M)]
for j in range(M):
    BC[j][0], BC[j][1] = [int(i) for i in input().strip().split()]
BC.sort(key=lambda x: x[1])

res = 0
cnt = 0
i = N - 1
j = M - 1
while True:
    if cnt == N:
        break

    if j == -1:
        res += A[i]
        i -= 1
    elif A[i] > BC[j][1]:
        res += A[i]
        i -= 1
    elif A[i] <= BC[j][1]:
        res += BC[j][1]
        BC[j][0] -= 1
        if BC[j][0] == 0:
            j -= 1
    else:
        raise ValueError
    cnt += 1
print(res)
### BUGGY CODE ###

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

for b, c in zip(B, C):
    A = [a if a != b else c for a in A]
    print(sum(A))

### FIXED CODE ###

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

sum_A = sum(A)
memo = [0] * 100001
for a in A:
    memo[a] += 1

for _ in range(Q):
    B, C = map(int, input().split())
    sum_A += (C - B) * memo[B]
    memo[C] += memo[B]
    memo[B] = 0
    print(sum_A)
### BUGGY CODE ###

def gcd(x,y):
  return (y if x%y==0 else gcd(y,x%y))
def lcd(x,y):
  return x*y//gcd(x,y)
N=int(input())
A=list(map(int,input().split()))
l=1
for a in A:
  l=lcd(a,l)
ans=0
for a in A:
  ans+=l//a
print(ans%1000000007)

### FIXED CODE ###

P=1000000007
def power(x,p):
  if(p==0):
    return 1;
  if(p%2):
    return power(x,p-1)*x%P;
  a=power(x,p//2);
  return a*a%P;
def inv(x):
  return power(x,P-2);
N=int(input());A=list(map(int,input().split()));
#N=10000;A=[1000000 for i in range(N)];
L=[0 for i in range(max(A)+1)]
for a in A:
  t=a;i=2;
  while(i**2<=a):
    c=0;
    while(t%i==0):
      t//=i;c+=1;
    L[i]=max(L[i],c)
    i+=1;
  if(t!=1):
    L[t]=max(L[t],1)
    
l=1;
for i in range(2,len(L)):
  l=l*power(i,L[i])%P;
b=0;
for a in A:
  b=(b+inv(a))%P
print(l*b%P)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
  n=int(input())
  a=[list(map(int,input().split())) for _ in range(n)]
  f=lambda x:((x[0]-1)*(n-1+n-x[0]+1))//2+x[1]-x[0]-1
  m=(n*(n-1))//2
  g=[[] for _ in range(m)]
  for i in range(n):
    for j in range(n-2):
      if i+1>a[i][j]:
        t0=f((a[i][j],i+1))
      else:
        t0=f((i+1,a[i][j]))
      if i+1>a[i][j+1]:
        t1=f((a[i][j+1],i+1))
      else:
        t1=f((i+1,a[i][j+1]))
      g[t0].append(t1)
  def dfs(t):
    if v[t]:
      if c[t]==0:
        return -1
      else:
        dp[t]
    v[t]=1
    for l in g[t]:
      ret=dfs(l)
      if ret==-1:return -1
      dp[t]=max(dp[t],ret+1)
    c[t]=1
    return dp[t]
  ans=0
  v=[0]*m
  c=[0]*m
  dp=[0]*m

  for i in range(m):
    tmp=dfs(i)
    if tmp==-1:
      print(-1)
      exit()
    ans=max(ans,tmp)
  print(ans+1)

if __name__=='__main__':
  main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
  n=int(input())
  a=[list(map(int,input().split())) for _ in range(n)]
  f=lambda x:((x[0]-1)*(n-1+n-x[0]+1))//2+x[1]-x[0]-1
  m=(n*(n-1))//2
  g=[[] for _ in range(m)]
  for i in range(n):
    for j in range(n-2):
      if i+1>a[i][j]:
        t0=f((a[i][j],i+1))
      else:
        t0=f((i+1,a[i][j]))
      if i+1>a[i][j+1]:
        t1=f((a[i][j+1],i+1))
      else:
        t1=f((i+1,a[i][j+1]))
      g[t0].append(t1)
  def dfs(t):
    if v[t]:
      if c[t]==0:
        return -1
      else:
        return dp[t]
    v[t]=1
    for l in g[t]:
      ret=dfs(l)
      if ret==-1:return -1
      dp[t]=max(dp[t],ret+1)
    c[t]=1
    mi.discard(t)
    return dp[t]
  ans=0
  v=[0]*m
  c=[0]*m
  dp=[0]*m
  #print(g)
  mi=set(list(range(m)))
  while mi:
    i=mi.pop()
    tmp=dfs(i)
    if tmp==-1:
      print(-1)
      exit()
    ans=max(ans,tmp)
    #print(dp)
  print(ans+1)

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

N = int(raw_input())
R = []
for i in range(0, N):
	R.append(int(raw_input()))
R.reverse()
max_num = -999999999

for x, i in enumerate(R[:N - 1]):
	for j in R[x + 1:]:		
		if max_num <(i - j):
			max_num = i - j

print max_num

### FIXED CODE ###

n = int(raw_input())
R = [input() for i in range(n)]
maxv = -2000000000
minv = R[0]
for j in range(1, n):
	maxv = max(maxv, R[j]-minv)
	minv = min(minv, R[j])
print maxv
### BUGGY CODE ###

import sys
x = int(input())
if x == 2:
    print(2)
    sys.exit()
prime = [2]
for i in range(3, 1000000, 2):
    all(i % p != 0 for p in prime) and prime.append(i)
    if i >= x and i in prime:
        print(i)
        sys.exit()

### FIXED CODE ###

import sys
x = int(input())
if x == 2:
    print(2)
    sys.exit()
prime = [2]
for i in range(3, 1000000, 2):
    all(i % p != 0 for p in prime) and prime.append(i)
    if i >= x and i in prime:
        print(i)
        sys.exit()
### BUGGY CODE ###

# 拡張ユークリッド互除法
# gcd(a,b) と ax + by = gcd(a,b) の最小整数解を返す
def extgcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = extgcd(b % a, a)
        return g, x - (b // a) * y, y

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    gcd, x, y = extgcd(a,m)
    return (m+x%m)%m



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

mod = 998244353
ans = 0
for a in range(N+1):
    if (K - A*a) % B == 0 and A*a <= K:
        b = (K- A*a) // B
        res_a = 1
        for i in range(1,N+1):
            res_a = res_a*i%mod
        for i in range(1,a+1):
            res_a = res_a*mod_inv(i,mod)%mod
        for i in range(1,(N-a)+1):
            res_a = res_a*mod_inv(i,mod)%mod
        res_b = 1
        for i in range(1,N+1):
            res_b = res_b*i%mod
        for i in range(1,b+1):
            res_b = res_b*mod_inv(i,mod)%mod
        for i in range(1,(N-b)+1):
            res_b = res_b*mod_inv(i,mod)%mod
        ans += res_a*res_b%mod

print(ans%mod)



### FIXED CODE ###

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

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

p = 998244353
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans = 0

for a in range(N+1):
    if (K - A*a) % B == 0 and A*a <= K:
        b = (K- A*a) // B
        ans += cmb(N, a, p)*cmb(N, b, p)%p

print(ans%p)
### BUGGY CODE ###

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

for i in range(N-1):
    sum_A += A[i]*sum(A[i+1:N]) 
    sum_A %= 10**9+7
print(sum_A)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
sum_A = [0]*N
for j in range(N-1, 0, -1):
    sum_A[j] = A[j]+sum_A[(j+1) % N]
for i in range(N-1):
    ans += A[i]*sum_A[i+1]
    ans %= 10**9+7
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
for _ in range(min(K, 50)):
    counter = [0] * (N+2)
    for i, a in enumerate(A, 1):
        counter[max(0, i - a)] += 1
        counter[min(N + 1, i + a + 1)] += -1
    for i in range(1, len(counter) - 1):
        counter[i] += counter[i-1]
    A = counter[1:N+1]
print(*A)

### FIXED CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
for k in range(41):
    B = [0] * N
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        B[l] += 1
        if r + 1 < N: B[r + 1] -= 1
    for i in range(1, N): B[i] += B[i-1]
    A = B
    if k == K - 1: break
print(*A)
### BUGGY CODE ###

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

r = [0] * (n+1)
g = [0] * (n+1)
b = [0] * (n+1)
for i, c in enumerate(reversed(s), 1):
    if c == 'R':
        r[i] += r[i-1] + 1
    else:
        r[i] += r[i-1]
    
    if c == 'G':
        g[i] += g[i-1] + 1
    else:
        g[i] += g[i-1]
    
    if c == 'B':
        b[i] += b[i-1] + 1
    else:
        b[i] += b[i-1]

r = r[:-1][::-1]
g = g[:-1][::-1]
b = b[:-1][::-1]

ans=0
for i in range(n-2):
    for j in range(i+1, n-1):
        if s[i] == s[j]:
            continue
        se = set('RGB') - set(s[i] + s[j])
        c = se.pop()
        if c == 'R':
            ans += r[j]
            if 2*j-i < n and s[2*j-i] == 'R':
                ans -= 1
        elif c == 'G':
            # print('j=',j,'g[j]=',g[j])
            ans += g[j]
            if 2*j-i < n and s[2*j-i] == 'G':
                ans -= 1
        elif c == 'B':
            ans += b[j]
            if 2*j-i < n and s[2*j-i] == 'B':
                ans -= 1
        # print('i=',i,'j=',j,'c=',c, 'ans=',ans)
print(ans)

### FIXED CODE ###

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

r = [0] * (n+1)
g = [0] * (n+1)
b = [0] * (n+1)
for i, c in enumerate(reversed(s), 1):
    if c == 'R':
        r[i] += r[i-1] + 1
    else:
        r[i] += r[i-1]
    
    if c == 'G':
        g[i] += g[i-1] + 1
    else:
        g[i] += g[i-1]
    
    if c == 'B':
        b[i] += b[i-1] + 1
    else:
        b[i] += b[i-1]

r = r[:-1][::-1]
g = g[:-1][::-1]
b = b[:-1][::-1]

ans=0
for i in range(n-2):
    for j in range(i+1, n-1):
        if s[i] == s[j]:
            continue
        se = set('RGB') - set(s[i] + s[j])
        c = se.pop()
        if c == 'R':
            ans += r[j]
            if 2*j-i < n and s[2*j-i] == 'R':
                ans -= 1
        elif c == 'G':
            # print('j=',j,'g[j]=',g[j])
            ans += g[j]
            if 2*j-i < n and s[2*j-i] == 'G':
                ans -= 1
        elif c == 'B':
            ans += b[j]
            if 2*j-i < n and s[2*j-i] == 'B':
                ans -= 1
        # print('i=',i,'j=',j,'c=',c, 'ans=',ans)
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000000)

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

tree = [[] for _ in range(n)]
ope = [0]*n
opef=[False]*n
ret=[0]*n

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

def counter(target,num):
    global ret
    global ope
    global opef
    ret[target]+=num
    if not tree[target]:
        return
    for i in tree[target]:
        tmp=0
        if opef[i]==False:
            tmp=ope[i]
            opef[i]=True
        counter(i,num+tmp)

for _ in range(q):
    p,x=map(int,input().split())
    ope[p-1]+=x

for i in range(n):
    if opef[i]==False:
        opef[i]=True
        counter(i,ope[i])

print(*ret)

### FIXED CODE ###

n,q = map(int,input().split())
rl = [0] * n
al = [0] * n
for i in range(n-1):
    a,b = map(int,input().split())
    rl[b-1] = a -1
for j in range(q):
    p,x = map(int,input().split())
    al[p-1] += x
for k in range(1,n):
    al[k] += al[rl[k]]
print(*al)
### BUGGY CODE ###

# problem D

S = input()
Q = int(input())

query = []
for i in range(0,Q):
    query.append(input().split())

s = S
    
for i in query:
    if int(i[0]) == 1:
        # s を反転させる
        s = s[::-1]
    elif int(i[1]) == 1:
        # 先頭に i[2] をくっつける
        s = str(i[2]) + s
    else:
        # しっぽに i[2] をくっつける
        s = s + str(i[2])

print(s)

### FIXED CODE ###

from collections import deque

s = deque(input())
Q = int(input())
    
t = True
    
for i in range(Q):
    query = input().split()
    if query[0] == '1':
        t = not t
    else:
        if(t and query[1] == '1') or (not t and query[1] == '2'):
            s.appendleft(query[2])
        else:
            s.append(query[2])
            
s = ''.join(s)
    
if not t:
    s = s[::-1]
        
print(s)
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
sz_list = []
for i in range(k+1):
    sz_list.append(s-i)

for x in range(k+1):
    for y in range(k+1):
        s = x +y
        if s in sz_list:
            count+=1

print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if z >= 0 and z <= k:
            count+=1

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

N=input()
A=[int(x)for x in input().split()]
B=[0]
for x in A:
  B.append(B[-1]+x) 

count=0
C=list(set(B))

for x in C:
  i=B.count(x)
  if i>1:
    count+=(i-1)*i//2
print(count)

### FIXED CODE ###

import collections
N=input()
A=[int(x)for x in input().split()]
B=[0]
count=0
for x in A:
  i=B[-1]+x
  B.append(i)

dic=collections.Counter(B)
for key,c in dic.items():
  count+=c*(c-1)//2
print(count)
### BUGGY CODE ###

a,b,c = map(int, input().split())
for i in range(c):
  if a > 0:
    a -= 1
  elif b > 0:
    b -= 1
  else:
    break
    
print(a,b)

### FIXED CODE ###

a,b,c = map(int, input().split())
if a >= c:
  a -= c
  print(a,b)
elif c-a < b:
  b -= (c-a)
  a = 0
  print(a,b)
else:
  print(0,0)
### BUGGY CODE ###

from collections import deque
import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    S = A[:]
    T = [0]*N
    zeros = [0]*N
    for k in range(K-1):
        que = deque()
        T[:k+1] = zeros[:k+1]

        for i in range(k, N-1):
            a = S[i]
            while que and que[-1][1] <= a:
                que.pop()
            que.append((i, a))

            T[i+1] = que[0][1] + A[i+1]*(k+2)

            if que and que[0][0] <= i+1-M:
                que.popleft()
        S, T = T, S
    print(max(S))
solve()

### FIXED CODE ###

import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    S = A[:]
    T = [0]*N
    Q0 = [0]*N; Q1 = [0]*N
    for k in range(2, K+1):
        s = t = 0

        for i in range(k-1, N):
            a = S[i-1]
            while s < t and Q1[t-1] <= a:
                t -= 1
            Q0[t] = i-1; Q1[t] = a
            t += 1

            T[i] = Q1[s] + A[i]*k

            if s < t and Q0[s] <= i-M:
                s += 1
        S, T = T, S
    print(max(S))
solve()
### BUGGY CODE ###

n,k=map(int,input().split())
loop_=[1]
lst=list(map(int,input().split()))

Loop=True
while Loop:
    num=lst[loop_[-1]-1]
    if num in loop_:
        Loop=False
        tar=num
    else:
        loop_.append(num)
count=0
for i in loop_:
    if i==tar:
        break
    else:
        count+=1    

loop__=loop_[count:]

if k<=len(loop_):
    print(loop_[k])
else:
    num=k+1-len(loop_)
    print(loop__[num%len(loop__)-1])

### FIXED CODE ###

n,k=map(int,input().split())
loop_=[1]
l_set=set()
lst=list(map(int,input().split()))

tar=None
for i in range(k):
    num=lst[loop_[-1]-1]
    if num in l_set:
        tar=num
        break
    else:
        loop_.append(num)
        l_set.add(num)

if tar==None:
    print(loop_[k])
    exit()    
loop__=loop_[loop_.index(tar):]

num=k+1-len(loop_)
try:
  print(loop__[num%len(loop__)-1])
except:
  print(1)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))


def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    def trans(v):
    	l = [0] * (k + 1)
    	for i in range(k + 1):
        	l[i] = (v & 1)
        	v >>= 1
    	return l
  
    a.sort()
    lef = [1] * n
    rig = [1] * n
    mask = (1 << (k + 1)) - 1
    for i in range(n - 1):
        lef[i + 1] = lef[i] | (lef[i] << a[i]) & mask
        rig[-i - 2] = rig[-i - 1] | (rig[-i - 1] << a[-i - 1]) & mask
    ok = -1
    ng = n
    while ng - ok > 1:
        mid = (ng + ok) // 2
        lc = trans(lef[mid])
        rc = trans(rig[mid])
        # print(a[mid], lc, rc)
        rcs = [0] * (k + 2)
        for i in range(k + 1):
            rcs[i + 1] = rcs[i] + rc[i]
        for i in range(k + 1):
            if lc[i] and rcs[k - i] - rcs[max(k - a[mid] - i, 0)] > 0:
                ng = mid
                break
        else:
            ok = mid
    print(ok + 1)

if __name__ == '__main__':
    solve()

### FIXED CODE ###

n, k = map(int,input().split())
a = [k+1 if x > k else x for x in map(int,input().split())]
a.sort()
lef = [1]*n
rig = [1]*n
mask = (1 << (k+1)) - 1
for i in range(n-1):
  lef[i+1] = lef[i] | (lef[i] << a[i]) & mask
  rig[-i-2] = rig[-i-1] | (rig[-i-1] << a[-i-1]) & mask
ok = -1
ng = n
while ng - ok > 1:
  mid = (ng + ok) // 2
  if a[mid] >= k:
      ng = mid
      continue
  lc = lef[mid]
  rc = rig[mid]
  cov = ((1 << k) - 1) ^ ((1 << (k - a[mid])) - 1)
  for i in range(k):
    if lc & 1 and rc & cov:
      ng = mid
      break
    lc >>= 1
    cov >>= 1
  else:
    ok = mid
print(ok + 1)
### BUGGY CODE ###

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

num_r = S.count('R')
num_g = S.count('G')
num_b = N - num_r - num_g
C = [[num_r, num_g, num_b] for _ in range(N)]
r_cnt, g_cnt, b_cnt = 0, 0, 0

for i in range(N):
    if S[i] == 'R':
        r_cnt += 1
    elif S[i] == 'G':
        g_cnt += 1
    else:
        b_cnt += 1

    C[i][0] -= r_cnt
    C[i][1] -= g_cnt
    C[i][2] -= b_cnt

ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        if S[i] != S[j]:
            if 'R' not in [S[i], S[j]]:
                ans += C[j][0]
                if j+(j-i) < N and S[j+(j-i)]=='R':
                    ans -= 1
            if 'G' not in [S[i], S[j]]:
                ans += C[j][1]
                if j+(j-i) < N and S[j+(j-i)]=='G':
                    ans -= 1
            if 'B' not in [S[i], S[j]]:
                ans += C[j][2]
                if j+(j-i) < N and S[j+(j-i)]=='B':
                    ans -= 1

        #print(S[i], S[j], ans)

print(ans)

### FIXED CODE ###

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

num_r = S.count('R')
num_g = S.count('G')
num_b = N - num_r - num_g
C = [[num_r, num_g, num_b] for _ in range(N)]
r_cnt, g_cnt, b_cnt = 0, 0, 0

for i in range(N):
    if S[i] == 'R':
        r_cnt += 1
    elif S[i] == 'G':
        g_cnt += 1
    else:
        b_cnt += 1

    C[i][0] -= r_cnt
    C[i][1] -= g_cnt
    C[i][2] -= b_cnt

ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        if S[i] != S[j]:
            if 'R' not in [S[i], S[j]]:
                ans += C[j][0]
                if j+(j-i) < N and S[j+(j-i)]=='R':
                    ans -= 1
            if 'G' not in [S[i], S[j]]:
                ans += C[j][1]
                if j+(j-i) < N and S[j+(j-i)]=='G':
                    ans -= 1
            if 'B' not in [S[i], S[j]]:
                ans += C[j][2]
                if j+(j-i) < N and S[j+(j-i)]=='B':
                    ans -= 1

        #print(S[i], S[j], ans)

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

n,q=map(int,input().split())
d = {}
ans = [0]*(n+1)
for i in range(n-1):
    sta,gol = map(int,input().split())
    if gol not in d:
        d[gol] = set() 
    d[gol].add(sta)

for i in range(q):
    sta,val = map(int,input().split())
    ans[sta]+=val
    

for i in range(n):
    gol = i+1
    if gol in d:
        tmpset = d[gol]
        for t in tmpset:
            ans[gol]+=ans[t]
    

anss = ""
for i in range(n):
    anss = anss+str(ans[i+1])+" "
print(anss)

### FIXED CODE ###

n,q=map(int,input().split())
d = {}
ans = [0]*(n+1)
for i in range(n-1):
    sta,gol = map(int,input().split())
    d[gol] = sta

for i in range(q):
    sta,val = map(int,input().split())
    ans[sta]+=val
    

for i in range(n):
    gol = i+1
    if gol in d:
        ans[gol]+=ans[d[gol]]
    

for i in range(n):
    print(ans[i+1], " ",end="")
### BUGGY CODE ###

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

lst = []
for i in range(N):
    S, T , X = map(int, input().split())
    lst += [[X, max(0, S-X), max(0, T-X)]]

lst.sort()
#print (lst)

def check(a):
    for j in range(len(lst)):
            if lst[j][1] <= D and D < lst[j][2]:
                return lst[j][0]
            elif j == len(lst) - 1:
                return -1

for i in range(Q):
    D = int(input())
    print (check(D))

### FIXED CODE ###

import sys
input = sys.stdin.readline

from heapq import heappop, heappush
from collections import defaultdict

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

lst = []
for i in range(N):
    s, t, x = map(int, input().split())
    lst.append((t - x, 0, x)) #xで止まらなくなる
    lst.append((s - x, 1, x)) #xで止まる

for i in range(Q):
    lst.append((int(input()), 2, i))

lst.sort()
ans = [-1] * Q

#引っかかっている場所の管理
se = set()
se_hp = [] #heapで最小値を先頭に保つ

#小さい時刻から順に見ていく
for a, b, c in lst:
    if b == 0:
        se.remove(c)
    elif b == 1:
        se.add(c)
        heappush(se_hp, c)
    else:
        while se_hp and se_hp[0] not in se:
            heappop(se_hp)
        ans[c] = se_hp[0] if se_hp else -1

print ('\n'.join(map(str, ans)))
### BUGGY CODE ###

r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
A=2*(10**6)+3
P=[0 for i in range(A+1)]
P[1]=1
for i in range(2,A):
    P[i]=P[i-1]*i%mod
def comb(x,y):
    if y>x or x<=0:
        return(0)
    elif y==0:
        return(1)
    else:
        return(P[x]*pow(P[x-y],mod-2,mod)%mod*pow(P[y],mod-2,mod)%mod)

count=0
for i in range(c1+1,c2+2):
    count=(count+comb(i+r2,r2)-comb(i+r1-1,r1-1))%mod
print(count%mod)


### FIXED CODE ###

r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
A=2*(10**6)+3
P=[0 for i in range(A+1)]
P[1]=1
for i in range(2,A):
    P[i]=P[i-1]*i%mod

dr2=pow(P[r2],mod-2,mod)
dr1=pow(P[r1-1],mod-2,mod)
def combr2(x):
    y=r2
    if y>x or x<=0:
        return(0)
    elif y==0:
        return(1)
    else:
        return(P[x]*pow(P[x-y],mod-2,mod)%mod*dr2%mod)

def combr1(x):
    y=r1-1
    if y>x or x<=0:
        return(0)
    elif y==0:
        return(1)
    else:
        return(P[x]*pow(P[x-y],mod-2,mod)%mod*dr1%mod)
count=0
for i in range(c1+1,c2+2):
    count=(count+combr2(i+r2)-combr1(i+r1-1))%mod
print(count%mod)
### BUGGY CODE ###

str = list(input())
check = 0   #
ans = 0  # 取り除いた数
odd = 0

while True:
    check = 0

    if odd == 0:
        last = str[0]
        for j in range(len(str) - 1):
            if last != str[j + 1]:
                str.pop(j)
                str.pop(j)
                check = 1
                ans += 2
                break
            last = str[j + 1]
        odd = 1
    else:
        last = str[len(str)-1]
        for j in reversed(range(len(str) - 1)):
            if last != str[j]:
                str.pop(j)
                str.pop(j)
                check = 1
                ans += 2
                break
            last = str[j]
        odd = 0

    if check == 0:
        break
    if str == []:
        break

print(ans)


### FIXED CODE ###

str = list(input())
one = str.count("1")
zero = str.count("0")

print(min(one, zero)*2)
### BUGGY CODE ###

from collections import defaultdict

H, W, M = map(int, input().split())
dh, dw = defaultdict(int), defaultdict(int)
used = set()

for _ in range(M):
    h, w = map(int, input().split())
    dh[h] += 1
    dw[w] += 1
    used.add((h, w))

ih = sorted(dh.items(), key=lambda x:-x[1])
iw = sorted(dw.items(), key=lambda x:-x[1])

h, counth = ih[0]
w, countw = iw[0]
ans = counth + countw - ((h, w) in used)

for h, counth in ih:
    for w, countw in iw:
        b = counth + countw - ((h, w) in used)
        if b<ans:
            break
        ans = b
print(ans)


### FIXED CODE ###

from collections import Counter


def solve():
    H, W, M = map(int, input().split())
    dh, dw = Counter(), Counter()
    used = set()

    for _ in range(M):
        h, w = map(int, input().split())
        dh[h] += 1
        dw[w] += 1
        used.add((h, w))

    ih = dh.most_common()
    iw = dw.most_common()

    h, counth = ih[0]
    w, countw = iw[0]

    s = counth + countw
    ans = counth + countw - ((h, w) in used)

    for h, counth in ih:
        for w, countw in iw:
            if counth+countw < s or ans == s:
                break
            b = counth + countw - ((h, w) in used)
            ans = max(ans, b)
    print(ans)


solve()