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

from sys import exit

X, Y, Z, K = map(int, input().split())

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

score = []

for i in range(X):
    for j in range(Y):
        score.append(A[i] + B[j])

score.sort(reverse=True)

ans = []

for i in range(min(K, len(score))):
    for j in range(Z):
        ans.append(score[i] + C[j])

ans.sort(reverse=True)

for i in range(K):
    print(ans[i])


### FIXED CODE ###

from sys import exit

X, Y, Z, K = map(int, input().split())

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

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

ABC = []

for a in range(X):
    for b in range(Y):
        if (a + 1) * (b + 1) > K:
            break
        for c in range(Z):
            if (a + 1) * (b + 1) * (c + 1) > K:
                break
            ABC.append(A[a] + B[b] + C[c])

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

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


dp=[0]+[float("inf")]*(N-1)


for i in range(N-1):
    for j in range(K):
        if j+i+1>N-1:
            break
        dp[j+i+1]=min(abs(h[j+i+1]-h[i])+dp[i],dp[j+i+1])
    

print(dp[-1])

### FIXED CODE ###

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

S=int(input())

ma=pow(10,9)

for i in range(int(pow(S,1/2))+1,0,-1):
    #print(i)
    if S%i==0 and S//i<=ma:
        print(0,0,i,0,0,S//i)
        break


### FIXED CODE ###

S=int(input())

X_2=pow(10,9)
X_3=(X_2-S)%X_2
Y_3=(S+X_3)//X_2

print(0,0,X_2,1,X_3,Y_3)
### BUGGY CODE ###

from sys import stdin
from collections import deque


def get_adj_list(num_nodes, data, undirected=True):
    # adj_list ex) {1:[2,3,4], 2:[1,4,5], 3:[1,4], 4:[1,2,3,5], 5:[2,4]}
    graph = {}
    for i in range(num_nodes):
        graph[i+1] = []
    for val in data:
        x, y = val
        graph[x] = graph[x] + [y]
        if undirected:
            graph[y] = graph[y] + [x]
    return graph


def breadth_first_search(adj_list, start_node):
    dist = {}
    queue = deque([(start_node, 0)])
    while len(queue) > 0:
        v, d = queue.popleft()
        if v in dist: continue
        dist[v] = d
        for u in adj_list[v]:
            if u not in dist:
                queue.append((u, d+1))
    return dist

# bfs
def get_result(data):
    N, X, Y = data
    _data = [[i, i+1] for i in range(1, N)]
    _data += [[X, Y]]
    adj_list = get_adj_list(N, _data)
    dist_cnt = [0 for i in range(N)]
    for i in range(N):
        dist = breadth_first_search(adj_list, i+1)
        for j in range(i, N):
            dist_cnt[dist[j+1]] += 1
    for i in range(1, N):
        print(dist_cnt[i])

# 解説のコード
# def get_result(data):
#     N, X, Y = data
#     dist_cnt = [0 for i in range(N)]
#     for i in range(1, N+1):
#         for j in range(i+1, N+1):
#             min_dist = min([j-i, abs(X-i) + 1 + abs(Y-j), abs(Y-i) + 1 + abs(X-j)])
#             dist_cnt[min_dist] += 1
#     for i in range(1, N):
#         print(dist_cnt[i])


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip('\n').split(' ')))
    get_result(data)

### FIXED CODE ###

from sys import stdin


def get_result(data):
    N, X, Y = data
    dist_cnt = [0 for i in range(N)]
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            min_dist = min([j-i, abs(X-i) + 1 + abs(Y-j), abs(Y-i) + 1 + abs(X-j)])
            dist_cnt[min_dist] += 1
    for i in range(1, N):
        print(dist_cnt[i])


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip('\n').split(' ')))
    get_result(data)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,k = list(map(int, input().split()))
step_array = list(map(int, input().split()))
score_array = [0]
for i in range(0, n+1):
	for j in range(1, k+1):
		if i+j > n-1:
			break
		cost = abs(step_array[i] - step_array[i+j]) + score_array[i]
		if len(score_array) <= i+j:
			score_array.append(cost)
		elif(score_array[i+j]>cost):
			score_array[i+j] = cost
print(score_array[n-1])

### FIXED CODE ###

n,k = list(map(int, input().strip().split()))
step_array = list(map(int, input().strip().split()))
score_array = [0]
for i in range(0, n+1):
	for j in range(1, k+1):
		if i+j > n-1:
			break
		cost = abs(step_array[i] - step_array[i+j]) + score_array[i]
		if len(score_array) <= i+j:
			score_array.append(cost)
		elif(score_array[i+j]>cost):
			score_array[i+j] = cost
print(score_array[n-1])
### BUGGY CODE ###

def inpl():
    return list(map(int, input().split()))


N, D, A = inpl()
XH = [inpl() for i in range(N)]
XH.sort()
# print(XH)

bomb = [(h + A - 1) // A for x, h in XH]

ans = 0
queue = []
s_i = 0
sum_q = 0
for i in range(N):
    for b, last in queue[s_i:]:
        if XH[i][0] > last:
            sum_q -= queue[s_i][0]
            s_i += 1
        else:
            break

    bomb[i] -= sum_q
    if bomb[i] <= 0:
        pass
    else:
        ans += bomb[i]
        sum_q += bomb[i]
        queue.append([bomb[i], XH[i][0] + 2 * D])

print(ans)


### FIXED CODE ###

from collections import deque


def inpl():
    return list(map(int, input().split()))


N, D, A = inpl()
XH = [inpl() for i in range(N)]
XH.sort()
# print(XH)

bomb = [(h + A - 1) // A for x, h in XH]

ans = 0
dq = deque()
s_i = 0
sum_q = 0
for i in range(N):
    while dq and dq[0][1] < XH[i][0]:
        b, _ = dq.popleft()
        sum_q -= b

    bomb[i] -= sum_q
    if bomb[i] <= 0:
        pass
    else:
        ans += bomb[i]
        sum_q += bomb[i]
        dq.append([bomb[i], XH[i][0] + 2 * D])

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

n = int(input())
g = []
for i in range(n):
    line = list(map(int, input().split()))
    k = line[1]
    c = [100001] * n
    for j in range(k):
        v = line[2 + 2 * j]
        c[v] = line[3 + 2 * j]
    g.append(c)

distance = [100001] * n
distance[0] = 0
visited = [False] * n
current = 0

while not all(visited):
    min_i = 0
    min_d = 100001
    for i in range(n):
        if not visited[i]:
            if distance[current] + g[current][i] < distance[i]:
                distance[i] = distance[current] + g[current][i]
            if distance[i] < min_d:
                min_i = i
                min_d = distance[i]
    visited[current] = True
    current = min_i

for i in range(n):
    print(i, distance[i])

### FIXED CODE ###

inf = float('inf')
n = int(input())
g = []
for i in range(n):
    line = list(map(int, input().split()))
    k = line[1]
    c = [inf] * n
    for j in range(k):
        v = line[2 + 2 * j]
        c[v] = line[3 + 2 * j]
    g.append(c)

distance = [inf] * n
distance[0] = 0
visited = [False] * n
current = 0

while not all(visited):
    visited[current] = True
    min_i = 0
    min_d = inf
    for i in range(n):
        if not visited[i]:
            if distance[current] + g[current][i] < distance[i]:
                distance[i] = distance[current] + g[current][i]
            if distance[i] < min_d:
                min_i = i
                min_d = distance[i]
    current = min_i

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

a = int(input())
result = 0
for i in range(a - 1):
  result = result + i + 1


print(result)

### FIXED CODE ###

a = int(input())
print(int(a * (a - 1) // 2))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(300000)
from collections import Counter

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
A = LMI()

div = set(A)
cnt = Counter(A)
ans = 0

def divisors(n):
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            yield i
            if i != n // i:
                yield n//i
for a in A:
    if cnt[a] >= 2:
        continue
    flg = True
    for d in divisors(a):
        if d == a:
            continue
        if d in div:
            flg = False
            break
    if flg:
        ans += 1
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(300000)
from collections import Counter

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
A = LMI()

div = set(A)
cnt = Counter(A)
M = max(A)
ng = [False] * (M + 1)
for a in A:
    n = a * 2
    while n <= M:
        ng[n] = True
        n += a
ans = 0
for a in A:
    if cnt[a] >= 2:
        continue
    if ng[a]:
        continue
    ans += 1

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

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

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = 1
c = [0] * n
c[0] = 1
m = 0
while c[b-1] < 2 and k > 0:
	b = a[b-1]
	c[b-1] += 1
	k -= 1
while c[b-1] < 3 and k > 0:
	b = a[b-1]
	c[b-1] += 1
	m += 1
if k == 0:
	print(b)
else:
	o = k % m
	for i in range(o):
		b = a[b-1]
	print(b)
### BUGGY CODE ###

s = input()
q = int(input())

l_q = []
for i in range(q):
  l_q.append( list(input().split())  ) 

#クエリ処理
c = 0
for i in l_q:

  if i[0] == "1":
    c = (c+1)%2

  else:
    if (c+int(i[1]))%2 ==1:
      s = i[2] + s
    else:
      s = s + i[2]  
  
if c == 1:
  s = ''.join(list(reversed(s)))
print(s)

### FIXED CODE ###

from collections import deque

s = deque( list(input()) )
q = int(input())

l_q = []
for i in range(q):
  l_q.append( list(input().split())  ) 

#クエリ処理
c = 0
for i in l_q:

  if i[0] == "1":
    c = (c+1)%2

  else:
    if (c+int(i[1]))%2 ==1:
      s.appendleft(i[2])
    else:
      s.append(i[2])

s=list(s)

if c == 1:
  s.reverse()

s = ''.join(s)
print(s)
### BUGGY CODE ###

N, A, B = map(int, input().split())
ans = 0
while True:
  if N >= A:
    ans += A
    N -= A + B
  else:
    ans += max(N, 0)
    break
print(ans)
  

### FIXED CODE ###

N, A, B = map(int, input().split())
ans = (N // (A+B)) * A + min(A, N%(A+B))
print(ans)
### BUGGY CODE ###

N, K = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
minuss = []
pluss = []
for i in l:
    if i < 0:
        minuss = [-i] + minuss
    else:
        pluss = pluss + [i]
minuss = [0] + minuss
pluss = [0] + pluss

# minuss から k本、plussからK-k本取る(短い方を折り返すので2倍)
ans = 1e9
for k in range(N):
    if k >= len(minuss) or K - k >= len(pluss):
        continue
    ans = min(ans, min(minuss[k] * 2 + pluss[K-k], minuss[k] + pluss[K-k] * 2))
print(ans)

### FIXED CODE ###

N, K = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
minuss = [0] + [-i for i in l if i < 0][::-1]
pluss = [0] + [i for i in l if i >= 0]
# minuss から k本、plussからK-k本取る(短い方を折り返すので2倍)
ans = 1e16  # ?
if pluss == [0]:  # 4 2 [-4, -3 , -2, -1]
    pluss = minuss
    minuss = [0]
for k in range(K):
    if k >= len(minuss) or K - k >= len(pluss):
        continue
    ans = min(ans, min(minuss[k] * 2 + pluss[K-k], minuss[k] + pluss[K-k] * 2))
print(ans)
### BUGGY CODE ###

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

s = [0]
for i in range(n):
    s.append(s[i] + ai[i])

cnt = 0
for i in range(n):
    for j in range(i, n):
        if s[j + 1] - s[i] == 0:
            cnt += 1

print(cnt)


### FIXED CODE ###

import collections
import math


def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

s = [0]
for i in range(n):
    s.append(s[i] + ai[i])

c = collections.Counter(s)
print(sum([comb(v, 2) if v > 1 else 0 for v in c.values()]))
### BUGGY CODE ###

s = input()
n = len(s)
ans = 0
for i in range(4, n):
    for j in range(n-i+1):
        if int(s[j:j+i])%2019 == 0:
            ans += 1
print(ans)


### FIXED CODE ###

s = input()
n = len(s)
dp = [1] + [0]*2019
now = 0
i = 1

for c in reversed(s):
    now = (now+i*int(c))%2019
    dp[now] += 1
    i *= 10
    i %= 2019

ans = sum([i*(i-1)/2 for i in dp])
print(int(ans))
### BUGGY CODE ###

import math
from functools import reduce

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

x=0
k=int(input())

for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      x+=gcd(i,j,l)

print(x)

### FIXED CODE ###

from math import gcd

k = int(input())

r = range(1, k + 1)
ans = sum([gcd(gcd(a, b), c) for a in r for b in r for c in r])
print(ans)
### BUGGY CODE ###

import sys

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))

#実家DPと気合い遷移式

def main():
    N = I()
    a = LI()
    t = [0, 0, 0]
    for ai in a:
        t[ai-1] += 1
    A, B, C = t
    E = B+C

    dp = [[0 if (not i|j) else N/(i+j) for j in range(E+1)] for i in range(N+1)]

    for k in range(C+1):
        for j in range(E+1-k):
            for i in range(N+1-k-j):
                z = i+j+k
                if (not z):
                    continue
                d = dp[i][j]
                if (i<N):
                    dp[i+1][j] += (i+1)*d/(z+1)
                if (i>0)&(j<E):
                    dp[i-1][j+1] += (j+1)*d/z
                if (j>0)&(k<C):
                    dp[i][j-1] = (k+1)*d/z + N/z

    print(dp[A][B])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    N = I()
    a = LI()
    t = [0, 0, 0]
    for ai in a:
        t[ai-1] += 1
    A, B, C = t
    E = B+C

    dp = [[0 if (i+j==0) else N/(i+j) for j in range(E+1)] for i in range(N+1)]

    for k in range(C+1):
        for i in range(N+1):
            dp[i][E] = 0 if (i+E+k==0) else N/(i+E+k)
        for j in range(E+1):
            for i in range(N+1):
                z = i+j+k
                if (not z):
                    continue
                d = dp[i][j]
                if (i<N):
                    dp[i+1][j] += (i+1)*d/(z+1)
                if (i>0) and (j<E):
                    dp[i-1][j+1] += (j+1)*d/z
                if (j>0) and (k<C):
                    dp[i][j-1] = (k+1)*d/z + N/z

    print(dp[A][B])

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

n = int(input())
p = list(map(int,input().split()))
p_cutted = []
ans = 0
for i in range(n):
    p_cutted.append(p[i])
    if min(p_cutted) == p[i]:
        ans += 1
print(ans)


### FIXED CODE ###

from collections import deque
n = int(input())
p = list(map(int,input().split()))
p_cutted = []
p_cutted = deque(p_cutted)
min_p_cutted = p[0]
ans = 0
for i in range(n):
    p_cutted.append(p[i])
    if min_p_cutted >= p[i]:
        min_p_cutted = p[i]
        ans += 1
print(ans)
### BUGGY CODE ###

_x = input()
x = []
for i in _x:
    x.append(i)
count = 0
i = 0
while i < len(x):
    # print("i:{} x:{}".format(i, x))
    if i < len(x) - 1 and x[i] == "S" and x[i + 1] == "T":
        del x[i]
        del x[i]
        if i > 0:
            i -= 1
        continue
    else:
        count += 1
        i += 1
print(len(x))


### FIXED CODE ###

_x = input()
x = []
for i in _x:
    x.append(i)
count = 0

# 今まで確認してきたものはスタックに入れる
# スタックの頂上がSで次の入力がTならスタックをポップ
stack = []
i = 0
while i < len(x):
    if len(stack) > 0 and stack[-1] == "S" and x[i] == "T":
        del stack[-1]
    else:
        stack.append(x[i])
    i += 1
print(len(stack))
# print(stack)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


n = int(input())
up = 10**18
l = list(map(int, input().split()))

ans = 1
for i in l:
    ans *= i
    if i == 0:
        ans = 0
        break
    
if ans > up:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline


n = int(input())
up = 10**18
l = list(map(int, input().split()))

if 0 in l:
    print(0)
else:
    ans = 1
    for i in l:
        ans *= i
        if ans > up:
            print(-1)
            break
    else:
        print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
links = [list(map(int, input().split())) for _ in range(M)]

dp = [-1 for _ in range(N+1)]
def search(i):
    if dp[i] != -1:
        return dp[i]
    
    paths = 0
    for _, t in filter(lambda x: x[0] == i, links):
        paths = max(paths, search(t)+1)
    
    dp[i] = paths
    return paths

for i in range(1, N+1):
    search(i)

print(max(dp))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
links = [[] for _ in range(N+1)]
for _ in range(M):
    s, t = map(int, input().split())
    links[s].append(t)

dp = [-1 for _ in range(N+1)]
def search(i):
    if dp[i] != -1:
        return dp[i]
    
    paths = 0
    for t in links[i]:
        paths = max(paths, search(t)+1)
    
    dp[i] = paths
    return paths

for i in range(1, N+1):
    search(i)

print(max(dp))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i in range(N):
  if A[i] == 0:
    continue
  else:
    if i == N - 1 or (i < N - 1 and A[i] != A[i+1]):
      ans += 1
    for j in range(i+1, N):
      if A[j] % A[i] == 0:
        A[j] = 0
print(ans)

### FIXED CODE ###

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

F = [0 for i in range(A[-1]+1)]
for i in A:
  F[i] = 1

c_set = set()
for i in A:
  if F[i] == 0:
    continue
  c_set.add(i)
  for j in range(i, A[-1]+1, i):
    F[j] = 0

ans = len(c_set)
d = 0
d_set = set()
for i in range(N):
  if i == 0 and N > 1:
    if A[i] == A[i+1]:
      d_set.add(A[i])
  elif i < N - 1 and A[i-1] != A[i] and A[i] == A[i+1]:
    d_set.add(A[i])

print( len(c_set - d_set) )
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split(' ')]
b = [int(x) for x in input().split(' ')]

if sum(a) < sum(b):
    print('-1')
    exit()

count = 0
sabun = [(i, a[i]-b[i]) for i, _ in enumerate(a) if a[i]<b[i]]
husoku = sum([x[1] for x in sabun])

while husoku < 0:
    husoku += max(a) - b[a.index(max(a))]
    a[a.index(max(a))] = b[a.index(max(a))]
    count += 1

print(len(sabun) + count)

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split(' ')]
b = [int(x) for x in input().split(' ')]
 
if sum(a) < sum(b):
    print('-1')
    exit()
 
count = 0
sabun = [a[i]-b[i] for i, _ in enumerate(a)]
husoku = sum([x for x in sabun if x<0])
sabun.sort(reverse=True)

for i in sabun:
    if husoku >= 0:
        break
    husoku += i
    count += 1
 
print(len([x for x in sabun if x<0]) + count)
### BUGGY CODE ###

import itertools

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

prices = list(map(int, input().split()))

ans = 999999999999999

for i in itertools.combinations(prices, k):
    ans = min(ans, sum(i))

print(ans)

### FIXED CODE ###

import itertools

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

prices = list(map(int, input().split()))

prices = sorted(prices)

print(sum(prices[:k]))
### BUGGY CODE ###

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

t = []
cur = s[0]
cnt = 0
for ss in s:
    if cur == ss:
        cnt += 1
    else:
        sgn = 1 if cur == '1' else -1
        # 逆立ちでないなら-1
        t.append(cnt * sgn)

        cur = ss
        cnt = 1
sgn = 1 if cur == '1' else -1
# 逆立ちでないなら-1
t.append(cnt * sgn)

M = len(t)
ans = 0
for i in range(M):
    cnt = 0
    b = 0
    for j in range(i, M):
        if t[j] < 0:
            cnt += 1
            if cnt > K:
                break
            b += -t[j]
        else:
            b += t[j]
    ans = max(ans, b)
print(ans)


### FIXED CODE ###

from bisect import bisect_right

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

t = []
abs_t = []

cur = s[0]
cnt = 0
for ss in s:
    if cur == ss:
        cnt += 1
    else:
        sgn = 1 if cur == '1' else -1
        # 逆立ちでないなら-1
        t.append(cnt * sgn)
        abs_t.append(cnt)

        cur = ss
        cnt = 1
sgn = 1 if cur == '1' else -1
# 逆立ちでないなら-1
t.append(cnt * sgn)
abs_t.append(cnt)

M = len(t)

sgn_cnt = [0]
for tt in t:
    sgn_cnt.append(sgn_cnt[-1] + (1 if tt < 0 else 0))
# 反転が必要な箇所数の累積和

c_abst = [0]
for att in abs_t:
    c_abst.append(c_abst[-1] + att)

# print(t, abs_t, c_abst, sgn_cnt)

ans = 0
for i in range(M):
    ok = bisect_right(sgn_cnt, (K + sgn_cnt[i]))
    ok -= 1
    # print(ok, i, K + sgn_cnt[i])
    # print(c_abst)
    ans = max(ans, c_abst[min(ok, M)] - c_abst[i])
print(ans)
### BUGGY CODE ###

n = int(input())
s = str(input())
r, g, b = 0, 0, 0
for i in range(n):
    if s[i] == 'R':
        r += 1
    if s[i] == 'G':
        g += 1
    if s[i] == 'B':
        b += 1
ans = r*g*b


def rgb(k, i):
    se = set([s[i], s[i+k], s[i+2*k]])
    if len(se) == 3:
        return True
    return False


for k in range(1, n//2+1):
    for i in range(n):
        if i+2*k >= n:
            break
        if rgb(k, i):
            ans -= 1
print(ans)


### FIXED CODE ###

n = int(input())
s = str(input())
r = s.count('R')
g = s.count('G')
b = s.count('B')
ans = r*g*b

for k in range(1, n//2+1):
    for i in range(n):
        if i+2*k >= n:
            break
        if s[i] != s[i+k] and s[i] != s[i+2*k] and s[i+k] != s[i+2*k]:
            ans -= 1
print(ans)
### BUGGY CODE ###

import sys
import bisect
from heapq import heappush, heappop
sys.setrecursionlimit(10 ** 7)

# TLE

N, Q = map(int, input().split())
STX = [[int(x) for x in input().split()] for _ in range(N)]
EVENT = []
for s, t, x in STX:
    EVENT.append((s-x, 1, x))
    EVENT.append((t-x, 0, x))

for i in range(Q):
    d = int(input())
    EVENT.append((d, 2, i))

ans = [-1] * Q

EVENT.sort()

# print(EVENT)

STOP = set()
h = []
for t, op, x in EVENT:
    if not op:
        STOP.remove(x)
    elif op == 1:
        STOP.add(x)
        heappush(h, x)
    else:
        while h and h[0] not in STOP:
            heappop(h)
        ans[x] = h[0] if h else -1


'''
    if op == 2:
        while h and h[0] not in STOP:
            heappop(h)
        ans[x] = h[0] if h else -1
    elif op == 1:
        STOP.add(x)
        heappush(h, x)
    elif op == 0:
        STOP.remove(x)
'''


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


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

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

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

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

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

print('\n'.join(map(str,answer)))