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

import math
import sys
from functools import reduce


def eratosthenes(n):
    prime = [2]
    limit = int(n**0.5)
    prime_list = [i + 1 for i in range(2, n, 2)]
    while True:
        p = prime_list[0]
        if limit <= p:
            return prime + prime_list
        prime.append(p)
        prime_list = [e for e in prime_list if e % p != 0]

def prime_factorize(n):
    prime_list = eratosthenes(n)
    arr = []

    for p in prime_list:
        if n % p == 0:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            arr.append([p, cnt])
    
    return arr

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


def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

prime_list = eratosthenes(n)
check = [0]*(10**6)
pairwise = True

for x in a:
    for p in prime_list:
        if x % p == 0:
            if check[p]:
                pairwise = False
                break
            check[p] = 1
    if not pairwise:
        break

if pairwise:
    print('pairwise coprime')
    sys.exit()

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


### FIXED CODE ###

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

num = [0]*(10**6+1)

for x in a:
    num[x] += 1

pairwise = True
for i in range(2, 10**6+1):
    cnt = sum(num[i::i])
    if cnt == n:
        print('not coprime')
        exit()
    if cnt > 1:
        pairwise = False

if pairwise:
    print('pairwise coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

k = int(input())
def my_gcd(a, b):
    if a < b: a, b = b, a
    c = a % b
    if c == 0: return b
    for _ in range(100):
        c = a % b
        a = b
        b = c
        if c == 0: return a

ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        t = my_gcd(a, b)
        for c in range(1, k+1): ans += my_gcd(t, c)
print(ans)


### FIXED CODE ###

from math import gcd
k=int(input())
ans=0
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      ans+=gcd(gcd(a,b),c)
print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    A = map(int, input().split())
    l0 = [0] * 61
    l1 = [0] * 61
    for i in A:
        t = format(i, 'b').zfill(61)
        for j, v in enumerate(t):
            if v == '1':
                l1[j] += 1
            else:
                l0[j] += 1
    a = 0
    for i in range(61):
        a += ((2 ** i) * (l0[60-i] * l1[60-i])) % (10 ** 9 + 7)
    return a % (10**9 + 7)

print(main())





### FIXED CODE ###

def main():
    N = int(input())
    A = map(int, input().split())
    l0 = [0] * 61
    l1 = [0] * 61
    for i in A:
        t = format(i, 'b').zfill(61)
        for j, v in enumerate(t):
            if v == '1':
                l1[j] += 1
            else:
                l0[j] += 1
    a = 0
    for i in range(61):
        a += ((2 ** i) * (l0[60-i] * l1[60-i])) % (10 ** 9 + 7)
    return a % (10**9 + 7)

print(main())
### BUGGY CODE ###

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

d = [a[i] - a[i-1] for i in range(1, n)]
d.insert(0, a[0])
d.append(k - a[-1])
sum_d = sum(d)

most_min_path = 10000

for i in range(n):
    if i == 0:
        normal_ck = sum_d - d[i] - d[-1]
        reverse_ck = sum_d - d[i+1]
    elif i == n - 1:
        normal_ck = sum_d - d[i]
        reverse_ck = sum_d - d[i+1] - d[0]
    elif 0 < i < n - 1:
        normal_ck = sum(d) - d[i]
        reverse_ck = sum(d) - d[i+1]

    min_ck = normal_ck if normal_ck < reverse_ck else reverse_ck
    if most_min_path > min_ck:
        most_min_path = min_ck

print(most_min_path)

### FIXED CODE ###

k, n = map(int, input().split())
a = list(map(int, input().split()))
a.append(a[0] + k)

d = [a[i+1] - a[i] for i in range(n)]
l = 0
for i in range(n):
    l = max(l, a[i+1] - a[i])
print(k - l)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Fri Sep 13 22:46:19 2019

"""

N,M=( int(x) for x in input().split())
A=[int(s) for s in input().split()]

for i in range(M):
    Pmax=max(A)
    Pmax_index=A.index(max(A))
    A[Pmax_index]=int(A[Pmax_index]/2)
    
print(sum(A))

### FIXED CODE ###

import heapq

N,M=( int(x) for x in input().split())
A=[int(s)*-1 for s in input().split()]

heapq.heapify(A)

for i in range(M):
    A_max=heapq.heappop(A)*-1
    heapq.heappush(A,(A_max//2)*-1)    
print(sum(A)*-1)
### BUGGY CODE ###

n,m = map(int, input().split())
a = [int(input()) for i in range(m)]
mod = (10**9)+7
dp = [1] + [0]*(n)
for i in range(1,n+1):
    if i in a:
        dp[i] == 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[-1]%mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
A = set()
for i in range(m):
    a = int(input())
    A.add(a)
mod = (10**9)+7
dp = [1] + [0]*(n)
for i in range(1,n+1):
    if i in A:
    #リストに対するinは激遅なのでset
        dp[i] == 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
print(dp[-1])
### BUGGY CODE ###

if __name__ == '__main__':
    N = int(input())
    S = input()
    cnt = 0
    for i in range(N):
        for j in range(i+1, N):
            for k in range(j+1, N):
                if (S[i] != S[j] and S[i] != S[k] and S[j] != S[k]) and j - i != k - j:
                    cnt += 1
    print(cnt)

### FIXED CODE ###

from collections import Counter

def get_k(i, j):
    return 2*j - i

if __name__ == '__main__':
    N = int(input())
    S = input()
    C = Counter(S) 
    eq_cnt = 0
    cnt = C['R'] * C['G'] * C['B']
    for i in range(N):
        for j in range(i+1, N):
            k = get_k(i, j)
            if k >= N: continue
            if (S[i] != S[j] and S[i] != S[k] and S[j] != S[k]):
                eq_cnt += 1
    print(cnt - eq_cnt)
### BUGGY CODE ###

s = input()
n = len(s)
res = 0
for i in range(n):
    sum = int(s[i])
    for j in range(i + 1, n):
        num = int(s[j])
        sum = sum * 10 + num
        if sum % 2019 == 0:
            res += 1

print(res)

### FIXED CODE ###

s = input()
n = len(s)
res = 0
sum = 0
c = {}
c[0] = 1
p = 1
for i in range(n - 1, -1, -1):
    sum = (sum + int(s[i]) * p) % 2019
    if sum in c:
        res += c[sum]
    p = (p * 10) % 2019
    c[sum] = c.get(sum, 0) + 1

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

n, q = [int(x) for x in input().split()]
s = input()
for i in range(q):
    l, r = [int(x) for x in input().split()]
    print(s[l - 1:r].count("AC"))


### FIXED CODE ###

n, q = [int(x) for x in input().split()]
s = input()
c = [s[i:i + 2] == "AC" for i in range(n - 1)]
d = [0] * n
for i in range(1, n):
    d[i] = d[i - 1] + c[i - 1]

for i in range(q):
    l, r = [int(x) for x in input().split()]
    print(d[r - 1] - d[l - 1])
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for i in range(N+1):
    for j in range(N-i+1):
        if (N - i*R - j*G) / B >= 0 and (N - i*R - j*G) % B == 0:
            ans += 1
            
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for i in range(N // R + 1):
    for j in range((N - R*i) // G + 1):
        if (N - i*R - j*G) % B == 0:
            ans += 1
            
print(ans)
### BUGGY CODE ###

n=int(input())
a=""
res=0
for i in range(n):
  a+=input()
if int(a[0])!=0:
  print(-1)
  exit()
for  i in range(n-1):
  a2=int(a[i+1])
  a1=int(a[i])
  if a2-a1>1:
    print("-1")
    exit()
  if a2<=a1:
    res+=a1
res+=int(a[n-1])
print(res)

### FIXED CODE ###

n=int(input())
res=0
a1=int(input())
if a1!=0:
  print(-1)
  exit()
try:a2=int(input())
except:
      print("0")
      exit()
for  i in range(n-2):
  if a2-a1>1:
    print("-1")
    exit()
  if a2<=a1:
    res+=a1
  a1=a2
  a2=int(input()) 
if a2-a1>1:
    print("-1")
    exit()
if a2<=a1:
    res+=a1
res+=a2
print(res)
### BUGGY CODE ###

x=int(input())
if x**0.2==int(x**0.2):
  print(int(x**0.2),0)
  exit()
i=int(-(x**0.2))
while True:
  h=(x+(i**5))**0.2
  if h==int(h):
    print(int(h),i)
    exit()
  i+=1

### FIXED CODE ###

x=int(input())
for i in range(-200,200):
  for j in range(-200,200):
    if (i**5)-(j**5)==x:
      print(i,j)
      exit()
### BUGGY CODE ###

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

def sad(A,b):
    return(sum(abs(v - b - i) for i,v in enumerate(A)))

print(min(sad(A,v) for v in range(-len(A),max(A),1)))


### FIXED CODE ###

from statistics import median_low

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

A = [v-i-1 for i,v in enumerate(A)]
x = median_low(A)

print(sum(abs(v - x) for v in A))
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
for i in range(q):
  c = 0
  l,r = map(int,input().split())
  for k in range(l,r):
    if s[k-1] == 'A' and s[k] == 'C':
      c += 1
  print(c)

### FIXED CODE ###

n,q=map(int,input().split())
s=list(input())
a=[0]*n
for i in range(n-1):
  if s[i]=="A" and s[i+1]=="C":
    a[i+1]=a[i]+1
  else:
    a[i+1]=a[i]
for i in range(q):
  l,r=map(int,input().split())
  print(a[r-1]-a[l-1])
### BUGGY CODE ###

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]
ans = 0
tyukan = []
saigo = []
 
for i in range(M):
    if ab[i][0] == 1:
        tyukan.append(ab[i][1])
 
for i in range(M):
    if ab[i][0] in tyukan:
        if ab[i][1] == N:
            ans =1
            break
 
print('POSSIBLE' if ans == 1 else 'IMPOSSIBLE') 

### FIXED CODE ###

N, M = map(int, input().split())
mid, las = [], []
ans = 0

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        mid.append(b)
    
    elif b == N:
        las.append(a)

if len(set(mid) & set(las)) != 0:
    ans =1

print('POSSIBLE' if ans == 1 else 'IMPOSSIBLE')
### BUGGY CODE ###

def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edgesが与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  import copy
  d=copy.deepcopy(A)
  for k in range(N):
    for i in range(N):
      for j in range(N):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d
 
import sys
from sys import stdin
input = stdin.readline
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
B=Warshall_Floyd(A,N)
if A!=B:
  print(-1)
  sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j:
        if A[i][j]==A[i][k]+A[k][j]:
          need=0
          break
    ans+=need*A[i][j]
print(ans)

### FIXED CODE ###

def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k, i, j in itertools.product(range(N), range(N),range(N)):
    if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
import itertools
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i, j in itertools.product(range(N),range(N)):
  need=1
  for k in range(N):
    if k!=i and k!=j and A[i][j]==A[i][k]+A[k][j]:
      need=0
      break
  if need:ans+=A[i][j]
print(ans//2)
### BUGGY CODE ###

import sys
h,w=map(int,input().split())
cmap=[input() for _ in range(h)]

whitesum=0
for each in cmap:
    whitesum += each.count(".")

def nextpoint(y,x):
    global cmap
    tmp=[]
    returnlist=[]
    cmap[y]=cmap[y][:x] + "#" + cmap[y][x+1:]

    if y == 0:
        tmp.append([y+1,x])
    elif y == h-1:
        tmp.append([y-1,x])
    else:
        tmp.extend([[y-1,x],[y+1,x]])

    if x == 0:
        tmp.append([y,x+1])
    elif x == w-1:
        tmp.append([y,x-1])
    else:
        tmp.extend([[y,x+1],[y,x-1]])

    for l in tmp:
        if cmap[l[0]][l[1]] == ".":
            returnlist.append(l)

    return returnlist

start=[0,0]
seen=[start]
todo=[]
todo.extend(nextpoint(start[0],start[1]))

i=2
finishflag=True

while finishflag:
    nextlist=[]

    for nep in todo:
        if nep == [h-1,w-1]:
            print(whitesum-i)
            sys.exit()
        else:
            nextlist.extend(nextpoint(nep[0],nep[1]))
    todo=[]
    todo.extend(nextlist)

    if todo == []:
        finishflag = False

    i += 1

print("-1")



### FIXED CODE ###

import sys
h,w=map(int,input().split())
cmap=[input() for _ in range(h)]

whitesum=0
for each in cmap:
    whitesum += each.count(".")

def nextpoint(y,x):
    global cmap
    tmp=[]
    returnlist=[]
    cmap[y]=cmap[y][:x] + "#" + cmap[y][x+1:]

    if y == 0:
        tmp.append([y+1,x])
    elif y == h-1:
        tmp.append([y-1,x])
    else:
        tmp.extend([[y-1,x],[y+1,x]])

    if x == 0:
        tmp.append([y,x+1])
    elif x == w-1:
        tmp.append([y,x-1])
    else:
        tmp.extend([[y,x+1],[y,x-1]])

    for l in tmp:
        if cmap[l[0]][l[1]] == ".":
            cmap[l[0]]=cmap[l[0]][:l[1]] + "#" + cmap[l[0]][l[1]+1:]
            returnlist.append(l)

    return returnlist

start=[0,0]
seen=[start]
todo=[]
todo.extend(nextpoint(start[0],start[1]))

i=2
finishflag=True

while finishflag:
    nextlist=[]

    for nep in todo:
        if nep == [h-1,w-1]:
            print(whitesum-i)
            sys.exit()
        else:
            nextlist.extend(nextpoint(nep[0],nep[1]))
    todo=[]
    todo.extend(nextlist)

    if todo == []:
        finishflag = False

    i += 1

print("-1")
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math


n = int(input())
a = [int(i) for i in input().split()]

b = []
for i in range(n):
    if (i+1) % 2 == 1:
        b.append(a[i])
    else:
        b.insert(0,a[i])

if (n+1)%2==0:
    b.reverse()

for i in range(n):
    print(b[i],end=" ")

print("")


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math


n = int(input())
a = [int(i) for i in input().split()]

b = [0 for i in range(n+1)]
half = n//2
for i in range(n):
    if (i+1)%2==0:
        b[half+(i//2)+1] = a[i]
    else:
        b[half-(i//2)] = a[i]

b.remove(0)
if n%2==0:
    b.reverse()

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

class UF():
  def __init__(self, N):
    self.parents = [ i for i in range(N+1) ]

  def union(self, f, t):
    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return
    self.parents[p2] = p1

  def find(self, node):
    # if self.parents[node] == node:
    #   return node
    # else:
    #   return self.find(self.parents[node])
    while self.parents[node] != node:
      node = self.parents[node]
    return node

N,M = map(int, input().split())
p = list(map(int, input().split()))
uf = UF(N)

for _ in range(M):
  x,y = map(int, input().split())
  uf.union(x,y)

res = 0
for i in range(N):
  if uf.parents[i+1] == uf.parents[p[i]]:
    res += 1
  elif uf.find(i+1) == uf.find(p[i]):
    res += 1

print(res)


### FIXED CODE ###

class UF():
  def __init__(self, N):
    self.parents = [-1] * (N+1)

  def union(self, f, t):
    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return

    if self.parents[p1] > self.parents[p2]:
      p1,p2 = p2,p1
    self.parents[p1] += self.parents[p2]
    self.parents[p2] = p1

  def find(self, node):
    if self.parents[node] < 0:
      return node
    else:
      self.parents[node] = self.find(self.parents[node])
      return self.parents[node]

  def same(self, n1, n2):
    return self.find(n1) == self.find(n2)

N,M = map(int, input().split())
p = list(map(int, input().split()))
uf = UF(N)
xy = [ list(map(int, input().split())) for _ in range(M) ]

# for _ in range(M):
#   x,y = map(int, input().split())
#   uf.union(x,y)
for x,y in xy:
  uf.union(x,y)

res = 0
for i in range(N):
  if i+1 == p[i] or uf.same(i+1, p[i]):
    res += 1

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

import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
# list(map(int, input().split()))

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

from itertools import combinations

ans = 10 ** 12
for i in combinations(P, k):
    ans = min(ans, sum(i))
print(ans)


### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
# list(map(int, input().split()))

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

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

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

### FIXED CODE ###

i = input().split()
a = int(i[0])
b = int(i[1])
k = int(i[2])
if a >= k:
  a = a - k
else:
  if (k - a) >= b:
    a = 0
    b = 0
  else:
    b = b - (k - a)
    a = 0
print(a," ",b)
### BUGGY CODE ###

K, S = map(int, input().split())
 
cnt = 0
for i in range(K+1):
    flg = False
    for j in range(K+1):
        if flg == True:
            break
        for k in range(K+1):
            ijk_sum = i + j + k
            if ijk_sum == S:
                flg = True
                lim_tmp = min(K - j, k)
                cnt += lim_tmp + 1
                break
print(cnt)

### FIXED CODE ###

K, S = map(int, input().split())
 
cnt = 0
for i in range(K+1):
    for j in range(K+1):
        k = S - i - j
        if k >= 0 and k <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)

for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

res = [set() for _ in range(N + 1)]
Q = int(input())
qd = [0] * Q
qc = [0] * Q
for i in range(Q):
  v, d, c = map(int, input().split())
  qd[i] = d
  qc[i] = c
  res[v].add(i)
#print(qc)

def clean():
  global res
  for i in range(1, N + 1):
    a = sorted(res[i], reverse = True)
    d = -1
    for j in range(len(a)):
      x = a[j]
      if qd[x] <= d: res[i].discard(x)
      d = max(d, qd[x])
clean()
for t in range(10):
  tres = [set() | s for s in res]
  for x in range(1, N + 1):
    for y in e[x]:
      for z in res[x]:
        if qd[z] > t: tres[y].add(z)
  res = tres
  clean()
#print(res)

for r in res[1: ]:
  if len(r): print(qc[max(r)])
  else: print(0)

### FIXED CODE ###

import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)

for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
mxd = 0
res = [[-1] * 11 for _ in range(N + 1)]
Q = int(input())
qd = [0] * Q
qc = [0] * Q
for i in range(Q):
  v, d, c = map(int, input().split())
  qd[i] = d
  qc[i] = c
  res[v][d] = i
  mxd = max(mxd, d)
#print(qc)

#print(mxd)
for t in range(mxd):
  tres = [x[: ] for x in res]
  for x in range(1, N + 1):
    for y in e[x]:
      for i in range(t + 1, 11):
        res[y][i] = max(res[y][i], tres[x][i])

#print(res)
for r in res[1: ]:
  x = -1
  for i in range(11):
    if r[i] != -1: x = max(x, r[i])
  if x == -1: print(0)
  else: print(qc[x])
### BUGGY CODE ###

import math

def calc_spf(n):
    num = list(range(2,n+1))
    spf = [0]*n
    
    while len(num)>0:
        p = num.pop(0)
        delta = p
        spf[p-1]=p
        p *= delta
        while p<=n:
            if p in num and spf[p-1]==0:
                spf[p-1]=delta
                num.remove(p)
            p += delta
    return spf

def get_prime(n,spf):
    if n==1:
        return {1}
    ans = []
    while n > 1:
        tmp = spf[n-1]
        ans.append(tmp)
        n //= tmp
    return set(ans)

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
b = a[:]
pgcd = True
sgcd = a[n-1]
spf = calc_spf(max(a))
b[n-1] = get_prime(a[n-1],spf)
tmp = b[n-1]
for i in range(0,n-1):
    sgcd = math.gcd(sgcd, a[i])
    b[i] = get_prime(a[i],spf)
    if pgcd and len(tmp&b[i]) >0 and tmp&b[i] !={1}:
        pgcd = False
    tmp = tmp | b[i]
if sgcd!=1:
    print('not coprime')
elif pgcd:
    print('pairwise coprime')
else:
    print('setwise coprime')

### FIXED CODE ###

import math

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
NUM = 1_000_005
aa = [0]*NUM
pgcd = True
sgcd = a[n-1]
aa[a[n-1]]+=1
for i in range(0,n-1):
    sgcd = math.gcd(sgcd, a[i])
    aa[a[i]]+=1

for i in range(2,NUM):
    tmp = sum(aa[i::i])
    if tmp >= 2:
        pgcd = False
        break
        
if sgcd!=1:
    print('not coprime')
elif pgcd:
    print('pairwise coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

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

count = {}
for i in range(N):
    if not S[i] in count:
        count[S[i]] = 1
    else:
        count[S[i]] += 1
max_k_list = [kv[0] for kv in count.items() if kv[1] == max(count.values())]
max_k_list.sort()
for i in range(len(max_k_list)):
    print(max_k_list[i])


### FIXED CODE ###

from collections import Counter

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

C = Counter(S)

C = sorted(C.items(), key=lambda x:x[1], reverse=True)


cnt_max = C[0][1]
ans = []
for i in range(len(C)):
    if cnt_max > C[i][1]:
        break
    else:
        ans.append(C[i][0])

ans.sort()

for w in ans:
    print(w)
### BUGGY CODE ###

import sys
import heapq

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

for i in range(N):
    s, t, x = map(int, sys.stdin.readline().split())
    events.append([s - x, 1, x])  # 通行止め追加
    events.append([t - x, -1, x])  # 通行止め削除

events.sort()
events.append([float('inf'), 'guard', None])

i = 0
closing = set()
hq = []  # 最小値を高速に入手するため
for q in range(Q):
    d = int(input())
    while d >= events[i][0]:
        time, event, x = events[i]
        if event == 1:
            closing.add(x)
            heapq.heappush(hq, x)

        elif event == -1:
            closing.remove(x)

        i += 1

    while hq and (hq[0] not in closing):
        heapq.heappop(hq)

    if hq:
        print(hq[0])
    else:
        print(-1)


### FIXED CODE ###

def main():

    import sys
    import heapq

    N, Q = map(int, sys.stdin.readline().split())
    events = []

    for i in range(N):
        s, t, x = map(int, sys.stdin.readline().split())
        events.append((s - x, 1, x))  # 通行止め追加
        events.append((t - x, -1, x))  # 通行止め削除

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

    events.sort()
    events.append([float('inf'), 'guard', None])

    i = 0
    closing = set()
    hq = []  # 最小値を高速に入手するため
    while d >= events[i][0]:
        time, event, x = events[i]
        if event == 1:
            closing.add(x)
            heapq.heappush(hq, x)

        elif event == -1:
            closing.remove(x)

        else:
            while hq and (hq[0] not in closing):
                heapq.heappop(hq)

            if hq:
                print(hq[0])
            else:
                print(-1)

        i += 1


if __name__ == '__main__':
    main()