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

from collections import Counter
N = int(input())
S = list(input())
dic = Counter(S)
dic2 = {"R":0,"G":0,"B":0}
ans = 0
for i in range(N-2):
    RGB = {"R","G","B"} - {S[i]}
    dic2[S[i]]+=1
    dic3 = {"R":0,"G":0,"B":0}
    for j in range(i+1,N-1):
        dic3[S[j]]+=1
        if len(RGB - {S[j]})!=1:
            continue
        else:
            target = list(RGB - {S[j]})[0]
            ans+=dic[target]-dic2[target]-dic3[target]
            if((j - i)+ j <= N -1):
                if(S[(j - i)+ j] == target):
                    ans-=1
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
S = list(input())
dic = Counter(S)
dic2 = {"R":0,"G":0,"B":0}
ans = 0
for i in range(N-2):
    RGB = {"R","G","B"} - {S[i]}
    dic2[S[i]]+=1
    dic3 = {"R":0,"G":0,"B":0}
    for j in range(i+1,N-1):
        dic3[S[j]]+=1
        if len(RGB - {S[j]})!=1:
            continue
        else:
            target = list(RGB - {S[j]})[0]
            ans+=dic[target]-dic2[target]-dic3[target]
            if((j - i)+ j <= N -1):
                if(S[(j - i)+ j] == target):
                    ans-=1
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod = 10**9+7

if K==1:print(0)
else:
  factorial=[1 for i in range(N+1)]
  for i in range(1,N+1):
    if i==1:factorial[i]=1
    else:factorial[i] = factorial[i-1]*i

  def comb(n,k):
    return factorial[n]//(factorial[n-k]*factorial[k])

  A1=sorted(A)
  A2=A1[::-1]
  
  ans=0
  for i in range(N-K+1):
    ans += (A2[i]-A1[i])*comb(N-i-1,K-1)
    ans %= mod

  print(ans)


### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod = 10**9+7

if K==1:print(0)
else:
  factorial=[1 for i in range(N+1)]
  for i in range(1,N+1):
    if i==1:factorial[i]=1
    else:factorial[i] = factorial[i-1]*i % mod
  
  def comb(n,k):
    return factorial[n]*pow(factorial[n-k]*factorial[k], -1, mod)

  A1=sorted(A)
  A2=A1[::-1]
  
  ans=0
  for i in range(N-K+1):
    ans += (A2[i]-A1[i])*comb(N-i-1,K-1)
  ans %= mod

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

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

def q_D(A, B):
	target = A
	another = B
	if A > B:
		target = B
		another = A
	yaku = []
	sosu = []
	if target == 1:
		yaku.append(1)
	for i in range(int(target/2)):
		n = i + 1
		if target % n == 0:
			if another % n == 0:
				yaku.append(n)
	for i, x in enumerate(yaku):
		if isPrime(x):
			sosu.append(x)
	print(len(sosu))

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

### FIXED CODE ###

# D - Disjoint Set of Common Divisors
A, B = map(int, input().split())

from fractions import gcd

# nの素数判定
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

# nの約数列挙
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            ass.append(n//i)
    return ass #sortされていない

ans = 0
gcd1 = gcd(A, B)
for i in divisor(gcd1):
    if is_prime(i):
        ans += 1

print(ans+1)
### BUGGY CODE ###

import heapq

COST_MAX = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
fare_adj = [[COST_MAX] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    fare_adj[u][v] = fare_adj[v][u] = a
    time_adj[u][v] = time_adj[v][u] = b
    fare_max = max(fare_max, a)

exchanges = []
for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    exchanges.append((c, d))


WALLET_MAX = fare_max * (N - 1)
mintime = [[TIME_MAX] * (WALLET_MAX + 1) for _ in range(N)]


def search():
    q = [(0, 0, min(S, WALLET_MAX))]
    while q:
        t, loc, silvers = heapq.heappop(q)
        if t > mintime[loc][silvers]:
            continue
        mintime[loc][silvers] = t
        while True:
            for nloc in range(N):
                if nloc == loc:
                    continue
                ntime = t + time_adj[loc][nloc]
                nsilvers = min(silvers - fare_adj[loc][nloc], WALLET_MAX)
                if nsilvers >= 0 and ntime < mintime[nloc][nsilvers]:
                    mintime[nloc][nsilvers] = ntime
                    heapq.heappush(q, (ntime, nloc, nsilvers))
            rate, wait = exchanges[loc]
            t += wait
            if silvers > WALLET_MAX:
                break
            silvers += rate


search()
for t in range(1, N):
    print(min(mintime[t]))


### FIXED CODE ###

import sys
import heapq

input = sys.stdin.readline

NCOSTS = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
adj = [[] for _ in range(N * NCOSTS)]
fare_adj = [[NCOSTS] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0


def node(city, silvers):
    return silvers * N + city


for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    for j in range(a, NCOSTS):
        adj[node(u, j)].append((node(v, j - a), b))
        adj[node(v, j)].append((node(u, j - a), b))

for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    for j in range(NCOSTS - c):
        adj[node(i, j)].append((node(i, j + c), d))


mintime = [TIME_MAX for _ in range(N * NCOSTS)]


def search():
    q = [(0, node(0, min(S, NCOSTS - 1)))]
    while q:
        t, node1 = heapq.heappop(q)
        if t > mintime[node1]:
            continue
        for node2, cost in adj[node1]:
            ntime = t + cost
            if mintime[node2] > ntime:
                mintime[node2] = ntime
                heapq.heappush(q, (ntime, node2))


search()
for i in range(1, N):
    print(min(mintime[node(i, j)] for j in range(NCOSTS)))
### BUGGY CODE ###

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
l = [0] * N
ans = 0
count = 0
check = [False] * N
tmpl = []

while(count <= N - 1):
    check = [False] * N
    for i in range(N):
        if l[i] < N - 1:
            to = A[i][l[i]] - 1
            if (not check[to]) and (not check[i]):
                if A[to][l[to]] - 1 == i:
                    l[i] += 1
                    l[to] += 1
                    check[to] = True
                    check[i] = True
                if l[i] == N - 1:
                    count += 1
                if l[to] == N - 1:
                    count += 1
    ans += 1
    if tmpl == l:
        print(-1)
        exit()
    tmpl = l[:]
    # print(l, ans)

print(ans)


### FIXED CODE ###

import sys
import time
def input():
    return sys.stdin.readline()
 
def main():
    a = time.time()
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    l = [0] * N
    ans = 0
    count = 0
    check = [False] * N
    tmpl = []
    next = False
 
    while(count < N):
        check = [False] * N
        for i in range(N):
            if l[i] < N - 1:
                to = A[i][l[i]] - 1
                if (not check[to]) and (not check[i]):
                    if A[to][l[to]] - 1 == i:
                        l[i] += 1
                        l[to] += 1
                        check[to] = True
                        check[i] = True
                        next = True
                    if l[i] == N - 1:
                        count += 1
                    if l[to] == N - 1:
                        count += 1
        ans += 1
        if not next:
            print(-1)
            exit()
        next = False

        b = time.time()
        if b - a >= 1.7:
            print(N*(N - 1)//2)
            exit()
        # print(l, ans)
 
    print(ans)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
edge = ['#'] * (W + 2)
field = [edge]
q = deque()

for i in range(H):
    line = input()
    field.append(['#'] + list(line) + ['#'])
    for j in range(W):
        if line[j] == '#':
            q.append((i + 1, j + 1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    if lv > res:
        res = lv

    for dy, dx in dyx:
        if field[y + dy][x + dx] == '.':
            field[y + dy][x + dx] = '#'
            q.append((y + dy, x + dx, lv + 1))

print(res)

### FIXED CODE ###

from collections import deque

dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
edge = ['#']*(W+2)
field = [edge]
q = deque()

for i in range(H):
    field.append(['#'] + list(input()) + ['#'])
    for j in range(W):
        if field[i+1][j+1] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    res = max(lv, res)

    for dy, dx in dyx:
        if field[y+dy][x+dx] == '.':
            field[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, lv+1))

print(res)
### BUGGY CODE ###

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

### FIXED CODE ###

a, b, k= map(int, input().split(" "))
if a > k:
    a -= k
else:
    k-=a
    a = 0
    if b > k:
        b-=k
    else:
        b = 0

print(a, b)
### BUGGY CODE ###

#coding:utf-8

R, G, B, N = map(int, input().split())

cnt = 0

for x in range(N+1):
    for y in range(N-x+1):
        '''
        if (N - x*R - y*G ) % B == 0:
            cnt += 1
        '''
        for z in range(N-x-y+1):
            if N == x*R + y*G + z*B:
                cnt += 1


print(cnt)

### FIXED CODE ###

#coding:utf-8

R, G, B, N = map(int, input().split())

cnt = 0

for red in range(int(N/R)+1):
    for green in range(int((N-red*R)/G)+1):
        if (N - (red*R + green*G)) % B == 0:
            cnt += 1

print(cnt)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a.sort()
f.sort(reverse=True)
m=0
for i in range(n):
    m=max(m,a[i]*f[i])
x=m//2
l=0
r=m
def check(x):
    p=0
    for i in range(n):
        if x//f[i]<a[i]:
            p+=a[i]-x//f[i]
    if p>k:
        return False
    else:
        return True
while l<r:
    if check(x):
        r=x
        x=(r+l)//2
    else:
        l=x
        x=(r+l)//2
print(r)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

a = []
f = []
n = 0

def rec(l, r, k):
    if l+1 < r:
        mid = (l + r) // 2
        s = 0
        for i in range(n):
            s += max(a[i] - mid // f[i], 0)
        if s <= k:
            return rec(l, mid, k)
        else:
            return rec(mid, r, k)
    else:
        return r

def main():
    global a, f, n
    n, k = map(int, input().strip().split())
    a = list(map(int, input().strip().split()))
    f = list(map(int, input().strip().split()))
    a = sorted(a)
    f = sorted(f, reverse=True)
    print(rec(-1, 10**12, k))

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

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

n = int(input())
game = [0]

for _ in range(n):
    comp = deque((map(int, input().split())))
    game.append(comp)

count = 0
final = n*(n-1)//2
for day in range(1, 1000000):
    finish = set()
    possible = False
    for me in range(1, n+1):
        if me in finish or game[me] == deque([]):
            continue

        you = game[me][0]
        if you in finish or game[you] == deque([]):
            continue
        else:
            if game[you][0] == me:
                finish.add(game[you].popleft())
                finish.add(game[me].popleft())
                possible = True
                count += 1
            else:
                continue

    if not possible:
        print(-1)
        exit()

    if count == final:
        print(day)
        exit()


### FIXED CODE ###

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

n = int(input())
game = {}

for i in range(1, n+1):
    game[i] = deque((map(int, input().split())))

count = 0
final = n*(n-1)//2
done = []

finish = [0] * (n + 1)
for me in range(1, n + 1):
    if finish[me] == 1 or game[me] == deque([]):
        continue

    you = game[me][0]
    if finish[you] == 1:
        continue
    else:
        if game[you][0] == me:
            done.append(you)
            done.append(me)
            finish[game[you].popleft()] = 1
            finish[game[me].popleft()] = 1
            possible = True
            count += 1
        else:
            continue

for day in range(2, 1000000):
    finish = [0]*(n+1)
    possible = False
    new_done = []
    for me in done:
        if finish[me] == 1 or game[me] == deque([]):
            continue

        you = game[me][0]
        if finish[you] == 1:
            continue
        else:
            if game[you][0] == me:
                finish[game[you].popleft()] = 1
                finish[game[me].popleft()] = 1
                new_done.append(me)
                new_done.append(you)
                possible = True
                count += 1
            else:
                continue
    done = new_done
    if not possible:
        print(-1)
        exit()

    if count == final:
        print(day)
        exit()
### BUGGY CODE ###

import bisect

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

A.sort()
F.sort(reverse=True)

if sum(A) <= K:
    ans = 0
else:
    AF = [A[i] * F[i] for i in range(N)]
    high = max(AF)
    low = 0
    mid = (high + low) // 2
    while low < mid < high:
        Ki = K
        able = True
        for i in range(N):
            if AF[i] > mid:
                Ki -= A[i] - mid // F[i]
                if Ki < 0:
                    able = False
                    break
        if able:
            high = mid
        else:
            low = mid
        mid = (high + low) // 2
    ans = high

print(ans)


### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
F = np.array(list(map(int, input().split())))

A.sort()
F[::-1].sort()

sum_A = A.sum()
if sum_A <= K:
    ans = 0
else:
    high = (A * F).max()
    low = 0
    mid = (high + low) // 2
    while low < mid < high:
        if sum_A - np.minimum(A, mid // F).sum() <= K:
            high = mid
        else:
            low = mid
        mid = (high + low) // 2
    ans = high

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

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

pre = 1
for i in range(k):
    pre *= A[i]

def prod(i, k):
    ret = 1
    for j in range(i-k, i):
        ret *= A[j]
    return ret

for i in range(k+1, n+1):
    now = prod(i, k)
    if now <= pre:
        print('No')
    else:
        print('Yes')
    pre = now


### FIXED CODE ###

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

for i in range(k, n):
    if A[i] > A[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1,N+1):
    ans += int(i*(1+N//i)*(N//i)/2)
print(ans)

### FIXED CODE ###

N = int(input())
c = (N+1)//2
ans = 0
for i in range(1,N-c+1):
    ans += i*(1+N//i)*(N//i)/2
ans += N*c -(c-1)*c/2
print(int(ans))
### BUGGY CODE ###

from fractions import gcd
K = int(input())

result = 0
for k in range(1, K + 1):
  for l in range(1, K + 1):
    for m in range(1, K + 1):
      gcd_res = gcd(gcd(k, l), m)
      result += gcd_res

print(result)


### FIXED CODE ###

def euclid(a, b):
  division = a if (a > b) else b
  divider = b if (a > b) else a
  reminder = 0
  while divider != 0:
    reminder = division % divider
    division = divider
    divider = reminder
  
  return division

K = int(input())

result = 0
for k in range(1, K + 1):
  for l in range(1, K + 1):
    for m in range(1, K + 1):
      gcd = euclid(euclid(k, l), m)
      result += gcd

print(result)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
for i in range(n):
  print(c[i + 1])
### BUGGY CODE ###


def main():
  n, k = map(int, input().split())
  A = tuple(map(int, input().split()))

  prev = None
  s = 1
  for i in range(n):
    s *= A[i]
    if i >= k - 1:
      if i >= k:
        s //= A[i - k]
        if s > prev:
          print('Yes')
        else:
          print('No')

      prev = s



main()


### FIXED CODE ###


def main():
  n, k = map(int, input().split())
  A = tuple(map(int, input().split()))

  for i in range(k, n):
    if A[i] > A[i - k]:
      print('Yes')
    else:
      print('No')



main()
### BUGGY CODE ###

def divbin(s,res):
  if int(s,2)==0:
    v=res
    return v
  # ss=int(s)
  val=int(s,2)
  count=bin(val).count("1")
  val%=count
  # t_str=bin(str(count))
  t_str=bin(val)
  t_str=t_str.replace("0b","")
  res+=1
  return divbin(t_str,res)

from copy import deepcopy
n=int(input())
x=input()

# c=str(bin(n))
# c=c.replace("0b","")
s=x
p=int(x)
cnt=bin(p).count("1")
x=list(x)
# print(cnt)
for i in range(len(x)):
  tmp=cnt
  ts=""
  if x[i]=="1":
    cnt-=1
    if i==0:
      ts="0"+s[i+1:]
    elif 1<=i<len(x)-1:
      ts=s[:i]+"0"+s[i+1:]
    elif i==len(x)-1:
      ts=s[:i]+"0"
  else:
    cnt+=1
    if i==0:
      ts="1"+s[i+1:]
    elif 1<=i<len(x)-1:
      ts=s[:i]+"1"+s[i+1:]
    elif i==len(x)-1:
      ts=s[:i]+"1"
  # ans=0
  # global ans
  ans=0
  ans=divbin(ts,ans)
  print(ans)



### FIXED CODE ###

n=int(input())
x=input()
val=int(x,2)

cnt=x.count("1")
p_cnt=cnt+1
m_cnt=cnt-1
p_amari,m_amari=0,0

p_amari=val%(cnt+1)
if cnt-1!=0:
  m_amari=val%(cnt-1)
else:
  m_amari=0

for i in range(n):
  ans=0
  if x[i]=="0":
    amari=p_amari+pow(2,n-i-1,p_cnt)
    amari%=p_cnt
  elif x[i]=="1":
    if cnt-1==0:
      print(0)
      continue
    amari=m_amari-pow(2,n-i-1,m_cnt)
    amari%=m_cnt
  ans+=1
  while amari!=0:
    amari%=bin(amari).count("1")
    ans+=1
  print(ans)
### BUGGY CODE ###

X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
s = p + q + r
s.sort()
s.reverse()
i = 0
j = 0
ans = 0
a = 0
b = 0
c = 0
while i < (X + Y):
  if s[j] in r:
    c += 1
    r.remove(s[j])
    ans += s[j]
    i += 1
  elif s[j] in p and a < X:
    a += 1
    p.remove(s[j])
    ans += s[j]
    i += 1
  elif s[j] in q and b < Y:
    b += 1
    q.remove(s[j])
    ans += s[j]
    i += 1
  j += 1
print(ans)

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse = True)
q = sorted(list(map(int, input().split())), reverse = True)
r = sorted(list(map(int, input().split())), reverse = True)
S = sorted(p[:X] + q[:Y] + r[:X+Y], reverse = True)
print(sum(S[:X+Y]))
### BUGGY CODE ###

import heapq
def dijkstra_heap(N,s,edge):
    d = [float("inf")] * N #始点sから各頂点への最短距離
    used = [False] * N
    d[s] = 0
    used[s] = True
    edgelist = []
    #edgelist : [sからの暫定(未確定)最短距離,頂点]のリスト
    #edge[s] : sから出る枝の[重み,終点]のリスト
    for v,w in enumerate(edge[s]):
        heapq.heappush(edgelist,(w,v)) #sの隣の点は枝の重さがそのまま暫定最短距離となる
    while len(edgelist):
        #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
        minedge = heapq.heappop(edgelist)
        #minedge : [sからの(確定)最短距離,頂点]
        v = minedge[1]
        if used[v]:
            continue
        d[v] = minedge[0]
        used[v] = True
        for u,w in enumerate(edge[v]):
            if not used[u]:
                heapq.heappush(edgelist,(d[v]+w,u))
    return d


################################
A, B, C, D = map(int, input().split())
N = int(input())

d = [[0]*(N+2) for _ in range(N+2)]

X = [0]*N
Y = [0]*N
R = [0]*N
for i in range(N):
    X[i],Y[i],R[i] = map(int, input().split())
d[0][-1] = ((C-A)**2+(D-B)**2)**0.5
d[-1][0] = ((C-A)**2+(D-B)**2)**0.5
for i in range(1,N+1):
    d_s = max(0,((X[i-1]-A)**2+(Y[i-1]-B)**2)**0.5-R[i-1])
    d_e = max(0,((X[i-1]-C)**2+(Y[i-1]-D)**2)**0.5-R[i-1])
    d[0][i],d[i][0] = d_s,d_s
    d[N+1][i],d[i][N+1] = d_e,d_e
    for j in range(1,N+1):
        d[i][j] = max(((X[i-1]-X[j-1])**2+(Y[i-1]-Y[j-1])**2)**0.5-R[i-1]-R[j-1],0)
s = 0 #始点
d = dijkstra_heap(N+2,s,d)
print(d[-1])

### FIXED CODE ###

import heapq
def dijkstra_heap(N,s,edge):
    d = [float("inf")] * N #始点sから各頂点への最短距離
    used = [False] * N
    d[s] = 0
    used[s] = True
    edgelist = []
    #edgelist : [sからの暫定(未確定)最短距離,頂点]のリスト
    #edge[s] : sから出る枝の[重み,終点]のリスト
    for v,w in enumerate(edge[s]):
        heapq.heappush(edgelist,(w,v)) #sの隣の点は枝の重さがそのまま暫定最短距離となる
    while len(edgelist):
        #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
        minedge = heapq.heappop(edgelist)
        #minedge : [sからの(確定)最短距離,頂点]
        v = minedge[1]
        if used[v]:
            continue
        d[v] = minedge[0]
        used[v] = True
        for u,w in enumerate(edge[v]):
            if not used[u]:
                heapq.heappush(edgelist,(d[v]+w,u))
    return d


################################
A, B, C, D = map(int, input().split())
N = int(input())

d = [[0]*(N+2) for _ in range(N+2)]

X = [0]*N
Y = [0]*N
R = [0]*N
for i in range(N):
    X[i],Y[i],R[i] = map(int, input().split())
d[0][-1] = ((C-A)**2+(D-B)**2)**0.5
d[-1][0] = ((C-A)**2+(D-B)**2)**0.5
for i in range(1,N+1):
    d_s = max(0,((X[i-1]-A)**2+(Y[i-1]-B)**2)**0.5-R[i-1])
    d_e = max(0,((X[i-1]-C)**2+(Y[i-1]-D)**2)**0.5-R[i-1])
    d[0][i],d[i][0] = d_s,d_s
    d[N+1][i],d[i][N+1] = d_e,d_e
    for j in range(1,N+1):
        d[i][j] = max(((X[i-1]-X[j-1])**2+(Y[i-1]-Y[j-1])**2)**0.5-R[i-1]-R[j-1],0)
s = 0 #始点
d = dijkstra_heap(N+2,s,d)
print(d[-1])
### BUGGY CODE ###

N, M = map(int, input().split())
price = list(map(int, input().split()))
price.sort(reverse=True)
for i in range(M):
  price[0] /= 2
  price.sort(reverse=True)
price = sum([int(i) for i in price])
print(price)

### FIXED CODE ###

from heapq import heappop, heappush

N, M = map(int, input().split())
price = list(map(int, input().split()))
he = []
for i in price:
  heappush(he, -i)
for i in range(M):
  max = heappop(he)
  heappush(he, -(-max//2))
print(-sum(he))
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappop, heappush

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, X))
    events.append((T - X, 1, X))

for _ in range(Q):
    events.append((int(input()), 2, 0))

events.sort()

cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]

for t, flag, x in events:
    if flag == 0:
        if cnt[x] == 0:
            heappush(que, x)
        cnt[x] += 1
    elif flag == 1:
        cnt[x] -= 1
    else:
        while cnt[que[0]] == 0:
            heappop(que)
        print(que[0] if que[0] != INF else -1)



### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, X))
    events.append((T - X, 1, X))

for _ in range(Q):
    events.append((int(input()), 2, 0))

events.sort()

cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]

for t, flag, x in events:
    if flag == 0:
        if cnt[x] == 0:
            heappush(que, x)
        cnt[x] += 1
    elif flag == 1:
        cnt[x] -= 1
    else:
        while cnt[que[0]] == 0:
            heappop(que)
        print(que[0] if que[0] != INF else -1)