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

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

b = [0]*200000
c = []
ans = 0

for x in a:
    b[x-1] += 1

for x in b:
    if x > 0:
        c.append(x)

while len(c) > k:
    ans += min(c)
    c.remove(min(c))

print(ans)

### FIXED CODE ###

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

b = [0]*200000
c = []
ans = 0

for x in a:
    b[x-1] += 1

for x in b:
    if x > 0:
        c.append(x)

c.sort()

y = len(c) - k

if y > 0:
    ans = sum(c[:y])

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

N, K = map(int,input().split())
P = list(map(int,input().split()))
count = 0
first = 1
def isSorted(ls):
    for i in range(len(ls)-1):
        if ls[i]>=ls[i+1]:
            return 0
    return 1

for i in range(N-K+1):
    if isSorted(P[i:i+K])==1:
        if first == 1:
            count += 1
            first = 0
        continue
    elif (i!=0) and (P[i-1] < min(P[i:i+K-1])) and (P[i+K-1] > max(P[i:i+K-1])):
        continue
    else:
        count += 1
print(count)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int,input().split())
P = list(map(int,input().split()))
count = 0
first = 1
def init(init_val,n):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def segfunc(x,y):
    return max([x,y])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

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

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

def init2(init_val,n):
    #set_val
    for i in range(n):
        seg2[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg2[i]=segfunc2(seg2[2*i+1],seg2[2*i+2])

def segfunc2(x,y):
    return min([x,y])

def update2(k,x):
    k += num-1
    seg2[k] = x
    while k:
        k = (k-1)//2
        seg2[k] = segfunc2(seg2[k*2+1],seg2[k*2+2])

def query2(p,q):
    if q<=p:
        return ide_ele2
    p += num-1
    q += num-2
    res=ide_ele2
    while q-p>1:
        if p&1 == 0:
            res = segfunc2(res,seg2[p])
        if q&1 == 1:
            res = segfunc2(res,seg2[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc2(res,seg2[p])
    else:
        res = segfunc2(segfunc2(res,seg2[p]),seg2[q])
    return res

#####単位元######
ide_ele2 = 10**9

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

l = [0]*(N-1)
for i in range(len(l)):
    if P[i]>=P[i+1]:
        l[i] = 1
l2 = [0]*(N-K+1)
tmp = sum(l[0:K-1])
for i in range(N-K+1):
    if tmp==0:
        l2[i]=1
    if i != N-K:
        tmp += (l[i+K-1]-l[i])
init(P,N)
init2(P,N)
for i in range(N-K+1):
    if l2[i]==1:
        if first == 1:
            count += 1
            first = 0
        continue
    elif  (P[i-1] < query2(i,i+K-1)) and (P[i+K-1] > query(i,i+K-1)) and (i!=0):
        continue
    else:
        count += 1
print(count)
### BUGGY CODE ###

N = input()
ans = 1
A = map(int, input().split())
for a in A:
  ans *= a
ans = -1 if ans > 10 ** 18 else ans
print(ans)

### FIXED CODE ###

N = int(input())
ans = 1
A = list(map(int, input().split()))
A.sort(reverse=True)
if A[N-1] == 0:
  ans = 0
else:
  for a in A:
    ans *= a
    if ans > 10 ** 18:
      ans = -1
      break
print(ans)
### BUGGY CODE ###

# E - Coprime

import math
from functools import reduce
from itertools import chain
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
assert len(a) == n

if reduce(math.gcd, a) > 1:
    print("not coprime")
    exit()

def factors(n):
    """Return the list of prime factors of n."""
    fac = set()
    d = 2
    while d <= math.sqrt(n):
        if n % d == 0:
            fac.add(d)
            n //= d
        else:
            d += 1
    if n > 1:
        fac.add(n)
    return fac

c = Counter(chain.from_iterable(map(factors, a)))
if max(c.values(), default=0) > 1:
    print("setwise coprime")
else:
    print("pairwise coprime")


### FIXED CODE ###

# E - Coprime

import math
from functools import reduce

n = int(input())
a = list(map(int, input().split()))
assert len(a) == n

if reduce(math.gcd, a) > 1:
    print("not coprime")
    exit()

def factors(n):
    """Return the list of prime factors of n."""
    fac = set()
    sqrtn = math.sqrt(n)
    d = 2
    while d <= sqrtn:
        if n % d == 0:
            fac.add(d)
            n //= d
        else:
            d += 1
    if n > 1:
        fac.add(n)
    return fac

count = [0] * (10 ** 6 + 1)
for x in a:
    for f in factors(x):
        count[f] += 1
        if count[f] > 1:
            print("setwise coprime")
            exit()
print("pairwise coprime")
### BUGGY CODE ###

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
    def find(self, x):
        if self.par[x] == x:
          return x
        else:
          self.par[x] = self.find(self.par[x])
          return self.find(self.par[x])
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

n, k, l = map(int, input().split())
uf1 = UnionFind(n)
uf2 = UnionFind(n)

for i in range(k):
  x, y = map(int, input().split())
  uf1.union(x-1, y-1)
for i in range(l):
  x, y = map(int, input().split())
  uf2.union(x-1, y-1)

ans = [1] * n

for i in range(1, n):
  for j in range(i):
    if uf1.is_same(i, j) and uf2.is_same(i, j):
      ans[i] += 1
      ans[j] += 1

print(" ".join(map(str,ans)))

### FIXED CODE ###

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
    def find(self, x):
        if self.par[x] == x:
          return x
        else:
          self.par[x] = self.find(self.par[x])
          return self.find(self.par[x])
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

n, k, l = map(int, input().split())
uf1 = UnionFind(n)
uf2 = UnionFind(n)

for i in range(k):
  x, y = map(int, input().split())
  uf1.union(x-1, y-1)
for i in range(l):
  x, y = map(int, input().split())
  uf2.union(x-1, y-1)

pair = [(uf1.find(i), uf2.find(i)) for i in range(n)]
import collections
c = collections.Counter(pair)
ans = [c[pair[i]] for i in range(n)]

print(" ".join(map(str,ans)))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(set(a))
l=len(b)
c=[0]*l
for i in range(l):
  c[i]=a.count(b[i])
c=sorted(c)
print(sum(c[:l-k]))

### FIXED CODE ###

import collections
n,k=map(int,input().split())
a = input().split()
a = sorted(list(collections.Counter(a).values()))
print(sum(a[:len(a)-k]))
### BUGGY CODE ###

import collections
import math

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

def combinations_count(n, r):
    if n < r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

counter = collections.Counter(A)

for val in counter.values():
    all_comb += combinations_count(val, 2)

for i in A:
    ans = all_comb - combinations_count(counter[i], 2) + combinations_count(counter[i] - 1, 2)
    print(ans)


### FIXED CODE ###

import collections

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

def combinations_count_two(n):
    if n < 2:
        return 0
    else:
        return (n * (n - 1)) // 2

counter = collections.Counter(A)

for val in counter.values():
    all_comb += combinations_count_two(val)

for i in A:
    ans = all_comb - combinations_count_two(counter[i]) + combinations_count_two(counter[i] - 1)
    print(ans)
### BUGGY CODE ###

from bisect import bisect_left
import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]

q = [A[0]]
for i in range(1,N):
    if q[0] >= A[i]:
        q.insert(0, A[i])
    else:
        insert_index = bisect_left(q,A[i])
        q[insert_index-1] = A[i]

print(len(q))


### FIXED CODE ###

from bisect import bisect_left
from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]

q = deque([A[0]])
for i in range(1,N):
    insert_index = bisect_left(q,A[i])
    if insert_index == 0:
        q.appendleft(A[i])
    else:
        q[insert_index-1] = A[i]

print(len(q))
### BUGGY CODE ###

from fractions import gcd
N, M = map(int, input().split())
k = 0
while True:
    if M % (N + k) == 0:
        ans = M // (N+k)
        break
    k += 1
print(ans)

### FIXED CODE ###

def is_prime(N):
    if N == 1:
        return False
    for k in range(2, int(N**0.5) + 1):
        if N % k == 0:
            return False
    return True


N, M = map(int, input().split())
k = 0
if N != 1:
    if is_prime(M):
        print(1)
        exit()
while True:
    if M % (N + k) == 0:
        ans = M // (N+k)
        break
    k += 1
print(ans)
### BUGGY CODE ###

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

d={}

for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1

for _ in range(q):
    b,c=map(int,input().split())
    ans=0
    if c in d:
        if b in d:
            d[c]+=d[b]
    else:
        if b in d:
            d[c]=d[b]

    if b in d:
        d[b]=0

    for k,v in d.items():
        ans+=k*v

    print(ans)


### FIXED CODE ###

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

s=sum(a)
d=[0]*(10**5+1)
for i in a:
    d[i-1]+=1

for _ in range(q):
    b,c=map(int,input().split())
    tmp=0
    k=d[b-1]
    d[c-1]+=k
    d[b-1]=0

    tmp = k*c-k*b
    s+=tmp
    print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 1
for c in S:
    if c == 'A':
        a += q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+q, ab*3+a, ans*3+ab, q*3
    #a %= mod
    #ab %= mod
    #ans %= mod
    #q %= mod
print(ans % mod)


### FIXED CODE ###

import sys
input = sys.stdin.readline
S = input().strip()
mod = 10**9+7
a = 0
ab = 0
ans = 0
q = 1
for c in S:
    if c == 'A':
        a += q
    elif c == 'B':
        ab += a
    elif c == 'C':
        ans += ab
    elif c == '?':
        a, ab, ans, q = a*3+q, ab*3+a, ans*3+ab, q*3
    a %= mod
    ab %= mod
    ans %= mod
    q %= mod
print(ans % mod)
### BUGGY CODE ###

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

def gcd(x, y):
    if y==0:
        return x
    return gcd(y, x%y)

def factorize(n):
    res=[]
    i=2
    while i*i<=n:
        if n%i:
            continue
        res.append([i, 0])
        while n%i==0:
            n/=i
            res[-1][0]+=1
        i+=1
    if n!=1:
        res.append([n, 1])
    return res

g=gcd(A, B)
f=factorize(g)
ans=len(f)+1
print(ans)

### FIXED CODE ###

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

def make_cd(x, y):
  div1=make_divisors(x)
  div2=make_divisors(y)
  cd=[]
  for i in div1:
    for j in div2:
      if i==j:
        cd.append(i)
        break
  cd.sort()
  return cd

A, B=map(int, input().split())
if A<B:
  A,B=B,A
cd=make_cd(A, B)
ok=[True for _ in range(len(cd))]
for i in range(1, len(cd)):
  if not ok[i]:
    continue
  for j in range(i+1, len(cd)):
    if cd[j]%cd[i]==0:
      ok[j]=False
print(sum([1 if ok[i] else 0 for i in range(len(cd))]))
### BUGGY CODE ###

import heapq
from collections import defaultdict

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

money = defaultdict(set)
snuke = defaultdict(set)
for i in range(m):
    a, b, c, d = map(int, input().split())
    money[a-1].add((b-1, c))
    money[b-1].add((a-1, c))
    snuke[a-1].add((b-1, d))
    snuke[b-1].add((a-1, d))

def dijkstra(n, v, dedic):
    d = [float('inf')] * n
    d[v] = 0

    hq = [(0, v)]

    while hq:
        u = heapq.heappop(hq)[1]
        for nv, c in dedic[u]:
            if d[nv] > d[u] + c:
                d[nv] = d[u] + c
                heapq.heappush(hq, (d[u] + c, nv))

    return d

money_cost = dijkstra(n, s - 1, money)
snuke_cost = dijkstra(n, t - 1, snuke)

result = [10 ** 15 for _ in range(n)]
for i in range(n):
    result[i] -= money_cost[i] + snuke_cost[i]

for i in range(n):
    print(max(result[i:]))


### FIXED CODE ###

import heapq
from collections import defaultdict

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

money = defaultdict(set)
snuke = defaultdict(set)
for i in range(m):
    a, b, c, d = map(int, input().split())
    money[a-1].add((b-1, c))
    money[b-1].add((a-1, c))
    snuke[a-1].add((b-1, d))
    snuke[b-1].add((a-1, d))

def dijkstra(n, v, dedic):
    d = [float('inf')] * n
    d[v] = 0

    hq = [(0, v)]

    while hq:
        u = heapq.heappop(hq)[1]
        for nv, c in dedic[u]:
            if d[nv] > d[u] + c:
                d[nv] = d[u] + c
                heapq.heappush(hq, (d[u] + c, nv))

    return d

money_cost = dijkstra(n, s - 1, money)
snuke_cost = dijkstra(n, t - 1, snuke)

result = [10 ** 15 for _ in range(n)]
temp = 10 ** 15
for i in range(n - 1, -1, -1):
    temp = min(money_cost[i] + snuke_cost[i], temp)
    result[i] -= temp

for i in range(n):
    print(result[i])
### BUGGY CODE ###

import collections
import itertools

N = int(input())
s = [input() for _ in range(N)]

comb = itertools.combinations(s,2)

cnt = 0
for x,y in comb:
  if collections.Counter(x) == collections.Counter(y):
    cnt += 1

print(cnt)

### FIXED CODE ###

from collections import Counter
from math import factorial

N = int(input())
s = [input() for _ in range(N)]

for i in range(N):
  s[i] = list(s[i])
  s[i].sort()
  s[i] = "".join(s[i])
  
x = Counter(s).most_common()
cnt = 0
for i in range(len(x)):
  if x[i][1] >1:
    cnt += factorial(x[i][1]) // 2 // factorial(x[i][1] -2)
print(cnt)
### BUGGY CODE ###

x, y, z, k = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]
c = [int(_) for _ in input().split()]
ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])
ab.sort(reverse=True)
abc = []
for i in range(min(k, x*y)):
    for j in range(z):
        abc.append(ab[i] + c[j])
abc.sort(reverse=True)
for i in range(k):
    print(abc[i])


### FIXED CODE ###

x, y, z, k = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]
c = [int(_) for _ in input().split()]
ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])
ab.sort(reverse=True)
abc = []
for i in range(min(k, x*y)):
    for j in range(z):
        abc.append(ab[i] + c[j])
abc.sort(reverse=True)
for i in range(k):
    print(abc[i])
### BUGGY CODE ###

#   ABC129　D問題
import numpy as np

H, W = map(int, input().split())    #   1 <= H, W <= 2000
S_arr = []
for _ in range(H):
    S_arr.append(list(input()))

point_arr = np.zeros((H, W))

start = 0
stop = W
for y in range(H):
    start = 0
    stop = W
    for x in range(W):
        if S_arr[y][x] == "#":
            stop = x
            point_arr[y, start:stop] += stop - start
            start = stop + 1
    point_arr[y, start:W] += W - start
    

for x in range(W):  #   コードのコピペ禁止の原則に違反してるけど、改善方法が思いつかない問題
    start = 0
    stop = H
    for y in range(H):
        if S_arr[y][x] == "#":
            stop = y
            point_arr[start:stop, x] += stop - start
            start = stop + 1
    point_arr[start:H, x] += H - start

print(int(np.max(point_arr))-1) 
#   O(H*W)程度の計算量で十分高速だと思ってたのに、そうでもない問題
#   2019/06/10 現在未解決　Numpy配列の計算量かな？ポインタ復習が必要かな？

### FIXED CODE ###

#   ABC129　D問題
H, W = map(int, input().split())    #   1 <= H, W <= 2000
S_arr = []
for _ in range(H):
    S_arr.append(list(input()))

point_arr = [[0]*W for _ in range(H)]

start = 0
stop = W
for y in range(H):
    start = 0
    stop = W
    for x in range(W):
        if S_arr[y][x] == "#":
            stop = x
            for i in range(start, stop):
                point_arr[y][i] += stop - start
            start = stop + 1
    for i in range(start, W):
        point_arr[y][i] += W - start


for x in range(W):  #   コードのコピペ禁止の原則に違反してるけど、改善方法が思いつかない問題
    start = 0
    stop = H
    for y in range(H):
        if S_arr[y][x] == "#":
            stop = y
            for i in range(start, stop):
                point_arr[i][x] += stop - start
            start = stop + 1
    for i in range(start, H):
        point_arr[i][x] += H - start

ans = 0
for i in range(H):
    for j in range(W):
        if ans < point_arr[i][j]:
            ans = point_arr[i][j]
ans -= 1
print(ans)
#   O(H*W)程度の計算量で十分高速だと思ってたのに、そうでもない問題
#   2019/06/10 現在未解決　PyPy使ったらどうなるのかやってみた。Numpy含まれてるからランタイムエラーになるのだろうか？
### BUGGY CODE ###

def divisible():
    n, p = map(int, input().strip().split())
    s = input()
    s = [int(s[i:j+1]) for i in range(n) for j in range(i, n)]
    count = 0
    for i in range(len(s)):
        if s[i] % p == 0:
            count += 1
    print(count)
divisible()

### FIXED CODE ###

def sol(s, p):
	n = len(s)
	cnt = 0
	if p == 2 or p == 5:
		for i in range(n):
			if (s[i] % p == 0):
				cnt += i + 1
	else:
		pre = [0] * (n+2)
		pre[n+1] = 0
		b = 1
		for i in range(n, 0, -1):
			pre[i] = (pre[i+1] + s[i-1] * b) % p
			b = (b * 10) % p
		rec = [0] * p
		rec[0] = 1
		for i in range(n, 0, -1):
			cnt += rec[pre[i]]
			rec[pre[i]] += 1
	return cnt

if __name__ == "__main__":
	n, p = map(int, input().split())
	s = input()
	print (sol([int(i) for i in s], p))
### BUGGY CODE ###

N, K, C, = map(int,input().split())
S = list(input())
ans = []

def solve(index):
    i = 0
    cnt = 0
    while i < N:
        if S[i] == 'o' and i != index:
            cnt += 1
            i += C + 1
        else:
            i += 1
    return cnt < K

index = 0
while index < N:
    if S[index] == 'x':
        index += 1
    elif solve(index):
        ans.append(index + 1)
        index += C + 1
    else:
        index += 1

for i in ans:
    print(i)

### FIXED CODE ###

N, K, C = map(int,input().split())
S = list(input())

def solve(List):
    ans = []
    i = 0
    while i < N:
        if List[i] == 'o':
            ans.append(i+1)
            i += C
        i += 1
    return ans

n = solve(S)

if len(n) > K:
    pass
else:
    r = solve(S[::-1])
    r = list(map(lambda x: N+1-x, r[::-1]))
    ans = list(set(n) & set(r))
    ans.sort()
    for i in ans:
        print(i)
### BUGGY CODE ###

from collections import deque
from heapq import *
import sys

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

e=[]
heapify(e)
for _ in range(n):
    s,t,x = map(int,input().split())
    heappush(e,(s-x,1,x))
    heappush(e,(t-x,-1,x))

q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()

while e:
    t,f,x = heappop(e)
    while t > q[0]:
        q.popleft()
        if s:
            print(min(s))
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
        
while q:
    q.pop()
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
n,q = map(int,input().split())
imos = []
for i in range(n):
    s,t,x = map(int,input().split())
    imos.append((s-x,x))
    imos.append((t-x,-x))
ans = set()
j = 0
for i in range(q):
    d = int(input())
    imos.append((d,1e100))
imos.sort()
m = 1e100
flag = False
for t,stop in imos:
    if stop == 1e100:
        if ans:
            if not flag:
                m = min(ans)
                flag = True
            print(m)
        else:
            print(-1)
    elif stop > 0:
        ans.add(stop)
        if stop < m:
            m = stop
            flag = True
    else:
        ans.remove(-stop)
        if m == -stop:flag = False
### BUGGY CODE ###

N = int(input())

min_l = len(str(N))
o_min_l = min_l

for i in range(1, N):
    if N % i == 0:
        j = int(N / i)
        min_l = min(min_l, max(len(str(i)), len(str(j))))
print(min_l)


### FIXED CODE ###

import math

N = int(input())

min_l = len(str(N))

for i in range(1, int(math.sqrt(N)) + 1):
    if N % i == 0:
        j = int(N / i)
        min_l = min(min_l, max(len(str(i)), len(str(j))))
print(min_l)
### BUGGY CODE ###

import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
def main():
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while(e[0] > d):
			if cont == True:
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			else:
				mini = min(kouho)
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
		
def sub():
	V = [list(map(int,inputs().split())) for p in [0]*N]
	M = [int(inputs()) for p in [0]*Q]
	V.sort(key = lambda x:(x[2],x[0],x[1]))
	for v in V:
		v[0] -= v[2]
		v[1] -= v[2] + 1
	for m in M:
		for n in range(N):
			if V[n][0] <=m and m <= V[n][1]:
				print(V[n][2])
				break
		else:
			print(-1)

#N200000
if Q>20000:
	sub()
else:
	main()

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

s = input()
n = int(input())
Q = [list(map(str, input().split())) for i in range(n)]

for i in range(n):
    op = Q[i]
    if len(op) == 1:
        s = s[::-1]
    elif op[1] == "1":
        s = op[2] + s
    else:
        s = s + op[2]
print(s)


### FIXED CODE ###

import collections

s = collections.deque(list(input()))
q = int(input())
rev = 0 #反転するなら1そうでないなら0
for i in range(q):
    tfc = list(input().split())
    if tfc[0]=='1':
        rev = abs(rev-1) #revが入力されるたびに1か0に変更される
    else:
        t,f,c = tfc
        if rev:
            if f=='1':
                s.append(c)
            else:
                s.appendleft(c)
        else:
            if f=='1':
                s.appendleft(c)
            else:
                s.append(c)
if rev: #反転される場合逆向きに出力されなければいけない 
    t = []
    for i in range(len(s)):
        t.append(s.pop())
    print(''.join(t))
else:
    print(''.join(s))