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

import math

import math
def Sieve_of_Eratosthenes(N):
    if N<2: return set()
    prime=set(i for i in range(2,N+1))
    for i in range(2,math.ceil(N**0.5)+1):
        tmp=set()
        for j in prime:
            if j>i and j%i==0: tmp.add(j)
        for j in tmp:
            prime.remove(j)

    return prime

def gcd(a,b):
    if b>a:
        a,b=b,a
    while b:
        a,b=b, a%b
    return a

a,b=map(int,input().split())
n=gcd(a,b)
prime=Sieve_of_Eratosthenes(int(math.sqrt(n))+2)

dic={}
ans=1
x=n
for p in prime:
    if x==1:
        break
    if x%p==0:
        ans+=1
        while x%p==0:
            x=x//p

if x!=1: ans+=1
print(ans)

### FIXED CODE ###

import math
def gcd(a,b):
    if b>a:
        a,b=b,a
    while b:
        a,b=b, a%b
    return a

a,b=map(int,input().split())
x=gcd(a,b)
s=set()
for i in range(2, min(x+1,int(math.sqrt(x))+2) ):
    while x%i==0:
        x=x//i
        s.add(i)
    if x==1: break
if x>1: s.add(x)
print(len(s)+1)
### BUGGY CODE ###

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

H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + ["#" + input().strip() +
                     "#" for _ in range(H)] + ["#" * (W+2)]

ans = 0

for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]

        q = deque()
        q.append((j, i, 0))

        while q:
            y, x, v = q.popleft()
            m[y][x] = v
            for d in ((y, x + 1), (y, x-1), (y+1, x), (y-1, x)):
                dj, di = d
                if S[dj][di] == "#" or m[dj][di] != -1:
                    continue
                q.append((dj, di, v+1))
                if ans < v+1:
                    ans = v+1
print(ans)


### FIXED CODE ###

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

H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + ["#" + input().strip() +
                     "#" for _ in range(H)] + ["#" * (W+2)]

ans = 0

for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]

        q = deque()
        q.append((j, i, 0))
        m[j][i] = 0

        while q:
            y, x, v = q.popleft()
            if ans < v:
                ans = v
            for dj, di in ((y, x+1), (y, x-1), (y+1, x), (y-1, x)):
                if S[dj][di] == "#" or m[dj][di] != -1:
                    continue
                q.append((dj, di, v+1))
                m[dj][di] = v+1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
import bisect
ans = 0
for i in range(len(a)):
    j = bisect.bisect_right(b,a[i])
    for k in range(j,len(b)):
        m = bisect.bisect_right(c,b[k])
        ans += n-m
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
import bisect
ans = 0
for j in range(len(b)):
    i = bisect.bisect_left(a,b[j])
    k = bisect.bisect_right(c,b[j])
    ans += i*(n-k)
print(ans)
### BUGGY CODE ###

import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque
from decimal import *

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
if __name__ == '__main__':
    a = int(input())

    count = 0

    for i in range(1,a+1):
        for j in range(1, a + 1):
            for k in range(1, a + 1):
                count += gcd(i,j,k)

    print(count)

### FIXED CODE ###

import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque
from decimal import *
 
import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
if __name__ == '__main__':
    a = int(input())
 
    count = 0
 
    for i in range(1,a+1):
        for j in range(1, a + 1):
            for k in range(1, a + 1):
                count += gcd(i,j,k)
 
    print(count)
### BUGGY CODE ###

import math

N = int(input())
A = list(map(int, input().split()))
C = [0] * (10 ** 6 + 1)

for i in range(N):
    C[A[i]] += 1

is_pairwise = True
max_a = max(A) + 1
X = [0] * max_a
for i in range(2, max_a):
    count = 0
    for j in range(i, max_a, i):
        count += C[j]
    if count > 1:
        is_pairwise = False

if is_pairwise:
    print('pairwise coprime')
    exit()

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])

if tmp == 1:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

import math

N = int(input())
A = list(map(int, input().split()))
C = [0] * (10 ** 6 + 1)

for i in range(N):
    C[A[i]] += 1

is_pairwise = True
max_a = max(A) + 1
X = [0] * max_a
for i in range(2, max_a):
    count = 0
    for j in range(i, max_a, i):
        count += C[j]
    if count > 1:
        is_pairwise = False

if is_pairwise:
    print('pairwise coprime')
    exit()

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])

if tmp == 1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

import heapq
class pqheap:
    def __init__(self):
        self.p = list()
        self.q = list()

    def insert(self,x):
        heapq.heappush(self.p, x)
        return

    def erase(self,x):
        heapq.heappush(self.q, x)
        return

    def minimum(self):
        while self.q and self.p[0] == self.q[0]:
            heapq.heappop(self.p)
            heapq.heappop(self.q)
        return self.p[0]
n=int(input())
b=list(map(int,input().split()))
a=list(map(int,input().split()))
pq=pqheap()
[pq.insert([-x,i]) for i,x in enumerate(a)]
ans=0
while len(pq.p)>len(pq.q):
    m=pq.minimum()
    pq.erase(m)
    v,i=m
    v=-v
    if v==b[i]:continue
    v-=a[(i-1)%n]
    v-=a[(i+1)%n]
    if v<=0:
        print(-1)
        exit()
    pq.insert([-v,i])
    a[i]=v
    ans+=1
print(ans)





### FIXED CODE ###

def main(n,a,b):
    ans=0
    while True:
        cnt=0
        for i in range(n):
            m=a[(i-1)%n]+a[(i+1)%n]
            if m<a[i] and b[i]<a[i]:
                a[i]-=b[i]
                cnt+=a[i]//m
                a[i]%=m
                a[i]+=b[i]
        if cnt==0:break
        ans+=cnt
    if a==b:
        print(ans)
    else:
        print(-1)
if __name__=='__main__':
    n=int(input())
    b=list(map(int,input().split()))
    a=list(map(int,input().split()))
    main(n,a,b)
### BUGGY CODE ###

n = int(input())
a = n - 1
p = 1
for c in range(2, int(n / 2)):
    if p == 1 and c > (n ** 0.5):
        break
    if n % c == 0:
        p = c
        w = int(n / c)
        if (w + c - 2) < a:
            a = (w + c -2)
        else:
            continue
    else:
        continue
print(a)


### FIXED CODE ###

n = int(input())
a = n - 1
p = 1
for c in range(2, int((n ** 0.5) * 2)):
    if p % 2 == 1 and c > (n ** 0.5):
        break
    if n % c == 0:
        p = c
        w = int(n / c)
        if (w + c - 2) < a:
            a = (w + c -2)
        else:
            continue
    else:
        continue
print(a)
### BUGGY CODE ###

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

for i in range(n):
    for j in range(n):
        if i == j:
            pass
        else:
            if a[i] == a[j]:
                print('NO')
                exit()
print('YES')

### FIXED CODE ###

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

a.sort()

for i in range(n-1):
    if a[i] == a[i+1]:
        print('NO')
        exit()
print('YES')
### BUGGY CODE ###

N = int(input())
numb = input().split()

def answer(N, numb):
    for i in range(N):
        for j in range(N):
            if i == j:
                continue

            if numb[i] == numb[j]:
                return "NO"

    return "YES"
 
print(answer(N,numb))

### FIXED CODE ###

N = int(input())
numb = input().split()

if len(set(numb)) == len(numb):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

class EndLoop(Exception):
    pass


def solve():
    while 1:
        try:
            N = int(input())
            D = list(map(int, input().split(" ")))
            M = int(input())
            T = list(map(int, input().split(" ")))
            if N < M:
                print("NO")
                break

            for t in T:
                if t in D:
                    D.remove(t)
                else:
                    print("NO")
                    raise EndLoop

            print("YES")
            break
        except:
            break


solve()

### FIXED CODE ###

def solve():
    while 1:
        try:
            N = int(input())
            D = list(map(int, input().split(" ")))
            M = int(input())
            T = list(map(int, input().split(" ")))
            D_dict = {}
            T_dict = {}
            for d in D:
                if d not in D_dict:
                    D_dict[d] = 1
                else:
                    D_dict[d] += 1

            for t in T:
                if t not in T_dict:
                    T_dict[t] = 1
                else:
                    T_dict[t] += 1

            for key, val in T_dict.items():
                if key not in D_dict:
                    print("NO")
                    raise EndLoop
                else:
                    if val > D_dict[key]:
                        print("NO")
                        raise EndLoop

            print("YES")
            break
        except:
            break


solve()
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

for s in sys.stdin:
  d = int(s)
  prime_list = range(d)[2:]
  for e in prime_list:
    i = 1
    while True:
      i += 1
      f = e*i
      if f > d:
        break
      if f in prime_list:
        prime_list.remove(f)
  print len( prime_list )

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

def calc_prime(n):
  p_list = [True]*n
  p_list[0] = p_list[1] = False
  for i in xrange(2,int(n**0.5)+1):
    if p_list[i]:
      for j in xrange(i*i,n,i):
        p_list[j] = False
  return [ i for i in xrange(2,n) if p_list[i] ]

prime_list = calc_prime(999999)
for s in sys.stdin:
  d = int(s)
  print len([prime_list[i] for i in range(len(prime_list)) if prime_list[i] <= d ])
### BUGGY CODE ###

total, tar = list(map(int, input().split()))
dice_array = list(map(int, input().split()))

tar2 = 0
calc_before = 0
calc_now = 0
for i in range(total+1-tar):
  calc_now = sum(dice_array[i:i+tar])
  if calc_before < calc_now:
    tar2 = i
    calc_before = calc_now
  calc_now = 0

sum_data = 0
cnt = 0
for i in range(tar2, tar+tar2):
  cnt = sum(list(range(1, dice_array[i] + 1)))
  sum_data += (cnt / dice_array[i])
  
print(sum_data)


### FIXED CODE ###

total, tar = list(map(int, input().split()))
dice_array = list(map(int, input().split()))

hope_array = [0.0] * total
for i in range(total):
   hope_array[i] = (dice_array[i] * (dice_array[i] + 1)) / 2 / dice_array[i]

dice_total = [0]
 
for i in range(total):
  dice_total.append(hope_array[i] + dice_total[i])
 
ans = dice_total[tar]
tar_num = tar
for i in range(total - tar):
  tmp = dice_total[i + 1 + tar] - dice_total[i + 1]
  if ans < tmp:
    ans = tmp

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

K = int(input())
c = 1
nana = 7
if K%2 == 0:
    print("-1")
else:
    while True:
        if nana%K == 0:
            print(c)
            break
        else:
            nana = nana%K*10 + 7
            c += 1

### FIXED CODE ###

K = int(input())
c = 1
nana = 7
if K%2 == 0:
    print("-1")
else:
    n = 7%K
    while True:
        i = nana%K
        if i == 0:
            print(c)
            break
        elif c >= 10**6:
            print("-1")
            break
        else:
            nana = (10*i+n)%K
            c += 1
### BUGGY CODE ###

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

dp = [[0]*(n+1) for i in range(n+1)]
dp[0][0] = 1

for i in range(1,n+1):
  dp[0][i] = 0
  dp[i][0] = dp[i-1][0] * (1 - a[i-1])
  
for i in range(1, n+1):
  for j in range(1, n+1):
    dp[i][j] = dp[i-1][j-1] * a[i-1] + dp[i-1][j] * (1 - a[i-1])

ans = 0
for i in range(n // 2 + 1 , n+1):
  ans += dp[n][i]

print(ans)
  

### FIXED CODE ###

n = int(raw_input())
a = list(map(float, raw_input().split()))
 
dp = [[0]*(n+1) for i in xrange(n+1)]
dp[0][0] = 1
 
for i in xrange(1,n+1):
  dp[0][i] = 0
  dp[i][0] = dp[i-1][0] * (1 - a[i-1])
  
for i in xrange(1, n+1):
  for j in xrange(1, n+1):
    dp[i][j] = dp[i-1][j-1] * a[i-1] + dp[i-1][j] * (1 - a[i-1])
ans = 0
for i in xrange(n // 2 + 1 , n+1):
  ans += dp[n][i]

print ans
### BUGGY CODE ###

N = int(input())
S = [0]
flag = 0
for i in range(N):
    if i==0:
        S[i] = input()
    else:
        temp = input()
        for j in range(len(S)):
            if S[j]==temp:
                flag = 1
        if flag==0:
            S = S + [temp]
        flag = 0

print(len(S))


### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(input())

S.sort()

dup = 0;
for i in range(N):
    if i!=0:
        if S[i] == S[i-1]:
            dup += 1

print(N-dup)
### BUGGY CODE ###

import sys
def solve(n,m,a):
    bb = {i+1:[] for i in range(n)}
    for [s1,s2] in a:
        bb[s1].append(s2)
    b = [i for i in bb.values()]
    for i in range(len(b)):
        b[i].sort()
    c = {s2:s1 for [s1,s2] in a}
    d = [s2 for [s1,s2] in a]
    #print(" a=",a,"\n","b=",b,"\n","c=",c,"\n","d=",d)
    ans = ""
    zero = ["00000","0000","000","00","0",""]
    for i in range(m):
        ken = str(c[d[i]])
        ban = str(b[c[d[i]]-1].index(d[i])+1)
        ans += zero[len(ken)-1] + ken + zero[len(ban)-1] + ban + "\n"
    
    return ans 
def readQuestion():
    ws = sys.stdin.readline().strip().split()
    N = int(ws[0])
    M = int(ws[1])
    ls_PY = [list(map(int, sys.stdin.readline().strip().split())) for j in range(M)]
    return (N, M, ls_PY)

def main():
    N, M, ls_PY = readQuestion()
    answer = solve(N, M, ls_PY)
    print(answer)

if __name__ == '__main__':
    main()

### FIXED CODE ###

N,M=map(int,input().split())
PY=[list(map(int,input().split()))+[i] for i in range(M)] #定義終了
 
PY.sort(key= lambda x:x[1])
num=[0]*N
w=[""]*M
 
for p,y,i in PY:
	num[p-1]+=1
	w[i]=str(p).zfill(6)+str(num[p-1]).zfill(6)

for i in range(M):
  	print(w[i])
### BUGGY CODE ###

import scipy as sp

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

tree = sp.array([], dtype = "int")
for i in range(N):
    tree = sp.append(tree, int(input()))

tree.sort()

min_of_sub = 0
print(min(tree[N-K+i] - tree[i] for i in range(N-K+1)))
    

### FIXED CODE ###

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

tree = [int(input()) for i in range(N)]

tree.sort()

print(min(tree[i+K-1] - tree[i] for i in range(N-K+1)))
### BUGGY CODE ###

N = int(input())
A = input().split()
B = []
for i in range(1, N+1):
    I = str(i)
    B.append(str(A.index(I)+1))
B = " ".join(B)
print(B)

### FIXED CODE ###

N = int(input())
A = input().split()
B = ["0" for i in range(0,N)]
for i in range(1, N+1):
    I = str(i)
    B[int(A[i-1])-1] = I
B = " ".join(B)
print(B)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)
def add_link(a, b):
    la = links[a]
    i, j = [(0, 1), (1, 0)][s[b] == 'B']
    if not la[i] and la[j]:
        able[a] = True
    la[i].add(b)
 
n, m = map(int, input().split())
s = input()
links = [[set(), set()] for _ in range(n)]
able = [None] * n
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    add_link(a, b)
    add_link(b, a)
 
def erase(v):
  if s[v] == "A":
    l = 0
  else:
    l = 1
  for q in links[v][0]:
    if not able[q]:
      continue
    links[q][l].remove(v)
    if links[q][l] == set():
      able[q] = None
      erase(q)
  for q in links[v][1]:
    if not able[q]:
      continue
    links[q][l].remove(v)
    if links[q][l] == set():
      able[q] = None
      erase(q)  
for i in range(n):
  if not able[i]:
    continue
  for k in range(2):
    for j in links[i][k].copy():
      if not able[j]:
        links[i][k].remove(j)
  if (links[i][0] == set() or links[i][1] == set()):
    flag =1
    able[i] = None
    erase(i)
if any(able):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n, m = map(int, input().split())
s = input()
links = [[] for _ in range(2*n)]
visit = [0] * n *2
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    if s[a] == s[b]:
      links[a].append(b+n)
      links[b].append(a+n)
    else:
      links[a+n].append(b)
      links[b+n].append(a)
def dfs(v):
  visit[v] = 1
  for i in links[v]:
    if visit[i] == 1:
      print("Yes")
      exit()
    elif visit[i] == 0:
      dfs(i)
  visit[v] = -1
  
for i in range(n):
  if visit[i] == 0:
    dfs(i)
print("No")
### BUGGY CODE ###

from operator import or_
import sys
input=sys.stdin.readline


class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x


def solve():
    N, Q = map(int, input().split())
    *c, = map(lambda x:{int(x)}, input().split())
    tree = SegTree(N, set(), or_)
    tree.set_list(c)
    for _ in range(Q):
        l, r = map(int, input().split())
        print(len(tree.get(l-1, r)))
    

solve()


### FIXED CODE ###

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [list(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(list(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


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

n, k = map(int, input().split())
aList = list(map(int, input().split()))
aKinds = list(set(aList))
if k > len(aKinds):
    print(0)
    exit()
else:
    aDict = {}
    for a in aKinds:
        aDict[a] = aList.count(a)
    aDictSorted = sorted(aDict.items(), key=lambda x: -x[1])
    count = 0
    for a in aDictSorted[k:]:
        count += a[1]
    print(count)

### FIXED CODE ###

from collections import Counter
n, k = map(int, input().split())
a = Counter(list(map(int, input().split())))
if k > len(a):
    print(0)
    exit()
else:
    print(sum(sorted(list(a.values()), reverse=True)[k:]))
### BUGGY CODE ###

n = int(input())
mentors = input().split(" ")

for i in range(1, n+1):
    print(mentors.count(str(i)))

### FIXED CODE ###

import collections

n = int(input())
mentors = input().split(" ")

a = collections.Counter(mentors)

for i in range(1, n+1):
    if str(i) in a.keys():
        print(a[str(i)])
    else:
        print(0)
### BUGGY CODE ###

n,m = map(int,input().split())
l,r = [0] * m, [0] * m
for i in range(m):
    l[i], r[i] = map(int, input().split())

max = 0
for i in range(m):
    if max < l[i]:
        max = l[i]
min = 10**5
for i in range(m):
    if min > r[i]:
        min = r[i]

ans = 0
for i in range(max,min+1):
    for j in range(m):
        if not((i) >= l[j] and (i) <= r[j]):
            break
        if j == m - 1:
            ans += 1

print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
l,r = [0] * m, [0] * m
for i in range(m):
    l[i], r[i] = map(int, input().split())

lmax = 0
rmin = 10 ** 5
for i in range(m):
    lmax = max(lmax,l[i])
    rmin = min(rmin,r[i])

if lmax <= rmin:
    print(rmin - lmax + 1)
else:
    print("0")
### BUGGY CODE ###

N,M = map(int,input().split())
A = [[] for i in range(M)]
for _ in range(N):
    a,b = map(int,input().split())
    if a<=M: A[M-a].append(b)
B = []
for m in range(M):
    B = B+A[m]
    B.sort(reverse=True)
    B = B[:m+1]
print(sum(B))

### FIXED CODE ###

import bisect
N,M = map(int,input().split())
A = []
for _ in range(N):
    a,b = map(int,input().split())
    if a<=M: A.append([a,b])
A.sort(reverse=True)
import heapq
h = []
ans = 0
for m in range(1,M+1):
    while A and A[-1][0] == m:
        heapq.heappush(h, A.pop()[1]*(-1))
    if h:
        ans -= heapq.heappop(h)
print(ans)
### BUGGY CODE ###

num = int(input())
input = 1
for i in range(1, num+1):
    input *= i

print(input % (10**9 + 7))

### FIXED CODE ###

import math



num = int(input())
input = math.factorial(num)

print(input % (10**9 + 7))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
from bisect import bisect_left
n,q=map(int,input().split())
stop=[]
for i in range(n):
	s,t,x=map(int,input().split())
	stop.append((s,t,x))
stop.sort(key=lambda x:x[2])
d=[int(input())for i in range(q)]

ans=[-1]*q
for s,t,x in stop:
    l=bisect_left(d,s-x)
    r=bisect_left(d,t-x)
    for i in range(l, r):
        if ans[i] == -1:
            ans[i] = x
            
for x in ans:
	print(x)

### FIXED CODE ###

import sys
input=sys.stdin.readline
from bisect import bisect_left
n,q=map(int,input().split())
stop=[]
for i in range(n):
	s,t,x=map(int,input().split())
	stop.append((s,t,x))
stop.sort(key=lambda x:x[2])
d=[int(input())for i in range(q)]
R=[-1]*q
ans=[-1]*q
for s,t,x in stop:
	#lからrにある区間のansをxに更新したい
	l=bisect_left(d,s-x)
	r=bisect_left(d,t-x)
	while l<r:
		if R[l]==-1:#最左がまだ確定していない場合
			ans[l]=x
			R[l]=r
			l+=1
		else:
			l=R[l]#確定しているところを飛ばす
for x in ans:
	print(x)
### BUGGY CODE ###

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

hl_s = sorted(hl, reverse=True)
delta = 10*10**9

for i in range(n-k+1):
    h_max = max(hl_s[i:i+k])
    h_min = min(hl_s[i:i+k])
    if delta > (h_max - h_min):
        delta = h_max - h_min
    if delta == 0:
        break

print(delta)

### FIXED CODE ###

n, k = map(int, input().split())
hl = [int(input()) for _ in range(n)]
hl.sort()

h_min = min(hl[i+k-1] - hl[i] for i in range(n-k+1))
print(h_min)