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

# -*- coding: utf-8 -*-

import sys
from math import sqrt
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()

M = int(sqrt(N))
i = 1
x = N
li1 = []
li2 = []
mul = []
while i < x:
    li1.append(x)
    i += 1
    prev = x
    x = N // i
    li2.append((prev - x) * (i - 1))
    mul.append(prev - x)
li = []
if i == x:
    li += li1 + [x] + li2[::-1]
else:
    li += li1 + li2[::-1]

M = len(li)
mul = [1] * (M-len(li2)) + mul[::-1]
dp = list2d(K-1, M, 0)
for i in range(M):
    dp[0][i] = li[i]

for i in range(1, K-1):
    acc = list(accumulate(dp[i-1]))[::-1]
    for j in range(M):
        dp[i][j] = acc[j] * mul[j] % MOD
print(sum(dp[K-2]) % MOD)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
from math import sqrt
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()

M = int(sqrt(N))
i = 1
x = N
li1 = []
li2 = []
mul = []
while i < x:
    li1.append(x)
    i += 1
    prev = x
    x = N // i
    li2.append((prev - x) * (i - 1))
    mul.append(prev - x)
li = []
if i == x:
    li += li1 + [x] + li2[::-1]
else:
    li += li1 + li2[::-1]

M = len(li)
mul = [1] * (M-len(li2)) + mul[::-1]
dp = list2d(K-1, M, 0)
for i in range(M):
    dp[0][i] = li[i]

for i in range(1, K-1):
    acc = list(accumulate(dp[i-1]))[::-1]
    for j in range(M):
        dp[i][j] = acc[j] * mul[j] % MOD
print(sum(dp[K-2]) % MOD)
### BUGGY CODE ###

from collections import deque
N, M, K = map(int, input().split())
F = dict()
Block = dict()
for i in range(1, N+1):
    F[i] = []
    Block[i] = []

for _ in range(M):
    A, B = map(int, input().split())
    F[A].append(B)
    F[B].append(A)
for _ in range(K):
    C, D = map(int, input().split())
    Block[C].append(D)
    Block[D].append(C)

def dfs(i, F):
    cnt = 0
    visited = [False]*N
    visited[i-1] = True
    deq = deque(F[i])
    while deq:
        Q = deq.pop()
        if type(Q) == int:
            Q = [Q]
        for q in Q:
            if visited[q-1]:
                continue
            visited[q-1] = True
            cnt += 1
            if q in Block[i] or q in F[i]:
                cnt -= 1
            deq += F[q]
            deq = list(set(deq))
    return cnt

for i in range(1, N+1):
    if i != N:
        print(dfs(i, F), end=' ')
    else:
        print(dfs(i, F))

### FIXED CODE ###

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

class UnionFind:
    def __init__(self, n):
        self.ps = [-1] * (n + 1)
 
    def find(self, x):
        if self.ps[x] < 0:
            return x
        else:
            self.ps[x] = self.find(self.ps[x])
            return self.ps[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.ps[x] > self.ps[y]:
            x, y = y, x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def size(self, x):
        x = self.find(x)
        return -self.ps[x]

uf = UnionFind(N)
friends = [0]*(N+1)
chain = [0]*(N+1)


for _ in range(M):
    A, B = map(int, input().split())
    friends[A] += 1
    friends[B] += 1
    uf.union(A, B)

for _ in range(K):
    C, D = map(int, input().split())
    if uf.same(C, D):
        friends[C] += 1
        friends[D] += 1

ans = []

for i in range(1, N+1):
    ans.append(uf.size(i) - friends[i] - 1)

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

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]

XH = sorted(XH)

for i in range(N):
    XH[i][1] = (XH[i][1] + A - 1) // A

adjust = [0 for _ in range(N + 1)]

def findi(v):
    ng = 0
    ok = N
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if XH[mid][0] > v: ok = mid
        else: ng = mid
    return ok

ans = 0
done = 0

for i in range(N):
    done -= adjust[i]
    XH[i][1] -= done
    if XH[i][1] < 0: continue

    ans += XH[i][1]
    index = findi(XH[i][0] + D * 2)
    done += XH[i][1]
    adjust[index] += XH[i][1]

print(ans)

### FIXED CODE ###

import sys
N, D, A = map(int, sys.stdin.readline().split())
XH = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

XH = sorted(XH)

for i in range(N):
    XH[i][1] = (XH[i][1] + A - 1) // A

adjust = [0 for _ in range(N + 1)]

def findi(v):
    ng = 0
    ok = N
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if XH[mid][0] > v: ok = mid
        else: ng = mid
    return ok

ans = 0
done = 0

for i in range(N):
    done -= adjust[i]
    XH[i][1] -= done
    if XH[i][1] < 0: continue

    ans += XH[i][1]
    index = findi(XH[i][0] + D * 2)
    done += XH[i][1]
    adjust[index] += XH[i][1]

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

from collections import defaultdict
from math import factorial

MOD = 10 ** 9 + 7

def nCr(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r))

def nHr(n, r):
    return nCr(n + r - 1, r)

N, M = map(int, input().split())

factors = defaultdict(int)
i = 2
while M > 1:
    while M % i == 0:
        M //= i
        factors[i] += 1
    i += 1

ans = 1
for n in factors.values():
    ans *= nHr(N, n)
    ans %= MOD
print(ans)


### FIXED CODE ###

from collections import defaultdict
from functools import reduce
from operator import mul

MOD = 10 ** 9 + 7

def nCr(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(1, r + 1))

N, M = map(int, input().split())

factors = defaultdict(int)
i = 2
while M > 1 and i * i <= M:
    while M % i == 0:
        M //= i
        factors[i] += 1
    i += 1 if i == 2 else 2
if M > 1:
    factors[M] += 1

ans = 1
for n in factors.values():
    ans *= nCr(N + n - 1, n)
    ans %= MOD
print(ans)
### BUGGY CODE ###

import heapq


n,m = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
bc = []
for i in range(m):
    bc.append([int(_) for _ in input().split()])
bc = sorted(bc, key=lambda x:x[1])
heapq.heapify(a)
for _ in range(m):
    b,c = bc.pop()
    for i in range(b):
        num = heapq.heappop(a)
        if num < c:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, num)
ans = 0
for i in range(len(a)):
    ans += a[i]
print(ans)

### FIXED CODE ###

import bisect


n,m = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
bc = []
for i in range(m):
    bc.append([int(_) for _ in input().split()])
bc = sorted(bc, key=lambda x:x[1])
a = sorted(a)
t = 0
ans = 0
for _ in range(m):
    b,c = bc.pop()
    idx = bisect.bisect_left(a, c)
    if idx > t:
        ans += c * min(idx - t, b)
        t += min(idx - t, b)
    else:
        continue
for i in range(t, n):
    ans += a[i]
print(ans)
### BUGGY CODE ###

def main():
  import bisect
  n,m = map(int,input().split())
  a = sorted(list(map(int,input().split())))
  for _ in range(m):
    x= a.pop(-1)/2
    index = bisect.bisect_left(a, x) 
    a.insert(index, x)
  print(int(sum(i//1 for i in a)))
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  import heapq
  n,m = map(int,input().split())
  a =sorted(list(map(lambda x: int(x)*(-1),input().split())))
  heapq.heapify(a)
  for _ in range(m):
    x=heapq.heappop(a)/2
    heapq.heappush(a,x) 
  print(int(sum((-1)*i//1 for i in a)))
if __name__=='__main__':
  main()
### BUGGY CODE ###

import sys
S = sys.stdin.readline().rstrip()
ans = 0
for i in range(0, len(S)-3):
    for j in range(i+3, len(S)):
        if int(S[i:j+1])%2019 == 0:
            ans += 1
print(ans)

### FIXED CODE ###

S = input() [::-1]
ans = 0
mod = 0
ten = 1
count = [0]* 2019
count[0] = 1
for i in range(len(S)):
    mod = (mod + int(S[i]) * ten) % 2019
    ten = ten*10 % 2019
    count[mod] += 1
for c in count:
    ans += c*(c-1)//2
print(ans)
### BUGGY CODE ###

S = list(input())
size = len(S)
ans = 0

while True:
    i = 0
    fg = False
    while i < size -1:
        if S[i] == 'B' and S[i+1] == 'W':
            ans += 1
            S[i] = 'W'
            S[i+1] = 'B'
            fg = True
        i += 1
    if fg == False:
        break
print(ans)

### FIXED CODE ###

import sys
import math
S = list(input())
size = len(S)

B_size = sum([ 1 for i in S if i == 'B' ])
if B_size == 0:
    print(0)
    sys.exit()

B_size2 = sum([ i for i,j in enumerate(S) if j == 'B' ])
ans= sum(range(0, size)[-B_size:]) - B_size2
print(ans)
### BUGGY CODE ###

def uf_find(x):
  while x != p[x]:
    x = p[x]
  return(x)

def uf_unite(x,y):
  x = uf_find(x)
  y = uf_find(y)
  if x == y:
    pass
  else:
    p[x] = y

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

for i in range(M):
  A, B = [int(i)-1 for i in input().split()]
  uf_unite(A,B)
  #print(p)

for i in range(N):
  p[i] = uf_find(i)
#print(p)

q = [0]*N
for i in range(N):
  q[i] = p.count(i)
  
print(max(q))


### FIXED CODE ###

N, M = map(int, input().split())

par = list(range(N))
rank = [1]*N
size = [1]*N

def find(x):
  if par[x] == x:
    return x
  else:
    return find(par[x])
  
def unite(x,y):
  x = find(x)
  y = find(y)
  
  if x == y:
    return
  if rank[x]<rank[y]:
    par[x]=y
    size[y]+= size[x]
  else:
    par[y] = x
    size[x] += size[y]
    if rank[x]==rank[y]:
      rank[x]+=1
    
for i in range(M):
  a,b = [int(i)-1 for i in input().split()]
  unite(a,b)
  
print(max(size))
### BUGGY CODE ###

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

r=0
for i in range(N-1):
  for j in range(i+1,N):
    if S[i]==S[j]:
      r+=1
print(r)

### FIXED CODE ###

N=int(input())
M={}
ans=0
for i in range(N):
    s=''.join(sorted(list(str(input()))))
    if s in M:
        ans+=M[s]
        M[s]+=1
    else:
        M[s]=1
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0

for i in range(k + 1):
    x = i
    for j in range(k + 1):
        y = j
        for l in range(k + 1):
            z = l
            if x + y + z == s:
                count += 1
print(count)


### FIXED CODE ###

k, s = map(int, input().split())
count = 0

for x in range(k + 1):
    for y in range(k + 1):
        if (s - x - y >= 0 and s - x - y <= k):
            count += 1

print(count)
### BUGGY CODE ###

K=int(input())

x=7%K
modlist=[]
i=1
flag=0
while(x not in modlist):
  if x==0:
    print(i)
    flag=1
    break
  modlist.append(x)
  x=(10*x+7)%K
  i+=1

if flag==0:
  print(-1)

### FIXED CODE ###

K=int(input())

x=7%K
i=1
flag=0
for j in range(K+1):
  if x==0:
    print(i)
    flag=1
    break
  x=(10*x+7)%K
  i+=1


if flag==0:
  print(-1)
### BUGGY CODE ###

K = int(input())

if K % 2 == 0:
  print(-1)
  exit()

k = 7
cnt = 1
while True:
  if k % K == 0:
    break
  k = (k * 10 + 7) % K
  cnt += 1

print(cnt)

### FIXED CODE ###

K = int(input())

if K % 2 == 0:
  print(-1)
  exit()

if K % 7 == 0:
  K //= 7
k = 1
cnt = 1
for i in range(10 ** 8):
  if k % K == 0:
    break
  k = (k * 10 + 1) % K
  cnt += 1
else:
  print(-1)
  exit()

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

n = int(input())
s = input()
ans = n
for i in range(n):
    grp1 = s[:i]
    grp2 = s[i+1:]
    cnt = grp1.count('W') + grp2.count('E')
    if cnt < ans:
        ans = cnt
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

w_num = [0] * (n+1)
e_num = [0] * (n+1)
e = s.count('E')

for i in range(n):
    if s[i] == 'W':
        w_num[i+1] = w_num[i] + 1
    else:
        w_num[i+1] = w_num[i]
        
    if s[i] == 'E':
        e_num[i+1] = e_num[i] + 1
    else:
        e_num[i+1] = e_num[i]


ans = n

for i in range(n):
    cnt = w_num[i] + (e - e_num[i+1])
    if cnt < ans:
        ans = cnt

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

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



for y in range(N):
    a.pop(y)
    a.insert(0, 0)
    price = 0
    for x in range(len(a)-1):
        price += abs(a[x+1] - a[x])
    price += abs(a[-1])
    print(price)
    a = list(A)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
A.insert(0,0)
A.append(0)
price = 0
for x in range(n+1):
    price += abs(A[x+1]-A[x])
for x in range(1, n+1):
    s = price
    s = s + abs(A[x-1]-A[x+1]) - (abs(A[x-1]-A[x])+abs(A[x]-A[x+1]))
    print(s)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

N=int(input())
A=list(map(int,input().split()))
abc=[0,0,0]#1,2,3個の寿司が載っている皿の枚数
for i in A:
    abc[i-1]+=1

#1,2,3個の寿司が載っている皿の枚数がi,j,kから全てを取るのに必要な期待値
dp=[[[0]*(N+1) for _ in range(N+1)] for i in range(N+1)]

          
def rec(i,j,k):
    if dp[i][j][k]!=-0:
        return dp[i][j][k]
    if i==0 and j==0 and k==0:
        return 0
    x,y,z=0,0,0
    if i-1>=0:
        x=rec(i-1,j,k)*i
    if j-1>=0:
        y=rec(i+1,j-1,k)*j
    if k-1>=0:
        z=rec(i,j+1,k-1)*k
    dp[i][j][k]=((x+y+z)+N)/(i+j+k)
    return dp[i][j][k]
            
print(rec(abc[0],abc[1],abc[2]))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
abc=[0,0,0]#1,2,3個の寿司が載っている皿の枚数
for i in A:
    abc[i-1]+=1
    
total=sum(A)

#1,2,3個の寿司が載っている皿の枚数がi,j,kから全てを取るのに必要な期待値
dp=[[[0.0]*(N+1) for _ in range(N+1)] for i in range(N+1)]



for k in range(abc[2]+1):#3枚の皿は初期枚数から増えない
    for j in range(abc[2]+abc[1]+1-k):#2枚の皿の枚数は，3枚の皿が減った枚数に依存
        for i in range(sum(abc)+1-j-k):
            if i==0 and j==0 and k==0:
                continue
            if i-1>=0:
                dp[i][j][k]+=dp[i-1][j][k]*i
            if j-1>=0:
                dp[i][j][k]+=dp[i+1][j-1][k]*j
            if k-1>=0:
                dp[i][j][k]+=dp[i][j+1][k-1]*k
            dp[i][j][k]+=N
            dp[i][j][k]/=(i+j+k)

print(dp[abc[0]][abc[1]][abc[2]])
### BUGGY CODE ###


N = int(input())
A = list(map(int, input().split()))
B = [0]*60
mod = 10 ** 9 + 7

for x in A:
  temp = bin(x)[2:]
  for i in range(len(temp)):
    if temp[-1-i] == "1":
      B[i] += 1

ans = 0

for i in range(60):
  ans += (N-B[i])*B[i]*pow(2, i, mod)
  ans %= mod

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0]*60
mod = 10 ** 9 + 7

for x in A:
  for i in range(60):
    B[i] += (x >> i) & 1

ans = 0
p = 1

for i in range(60):
  if i >= 1:
    p *= 2
    p %= mod
  ans += (N-B[i])*B[i]*p
  ans %= mod

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

import math

N = int(input())

for n in range(1, N + 1):
    count = 0
    ub = int(math.sqrt(n))
    for x in range(1, ub + 1):
        for y in range(x, ub + 1):
            for z in range(y, ub + 1):
                if x * x + y * y + z * z + x * y + y * z + z * x == n:
                    s = len(set([x, y, z]))
                    if s == 1:
                        count += 1
                    elif s == 2:
                        count += 3
                    else:
                        count += 6
                    break
    print(count)


### FIXED CODE ###

import math

N = int(input())

for n in range(1, N + 1):
    count = 0
    ub = int(math.sqrt(n))
    for x in range(1, ub + 1):
        for y in range(x, ub + 1):
            r = 4 * n - 3 * x * x - 2 * x * y - 3 * y * y
            if r < 0:
                break
            z = (math.sqrt(r) - x - y) / 2
            if z - int(z) < 1e-9:
                z = int(z)
            elif z - int(z + 1) < 1e-9:
                z = int(z + 1)
            else:
                break

            if y > z or z > ub:
                break
            if abs(x * x + y * y + z * z + x * y + y * z + z * x - n) < 1e-9:
                #print(x, y, round(z), z)
                s = len(set([x, y, round(z)]))
                if s == 1:
                    count += 1
                elif s == 2:
                    count += 3
                else:
                    count += 6

    print(count)
### BUGGY CODE ###

import sys

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

cl=[]
city=1
count=0
while city not in cl:
    count+=1
    cl.append(city)
    city=a[city-1]
#arrive at city in count, len(cl)=count
if k<count:
    print(cl[k])
    sys.exit()
#print(cl)
    
loop=0
for i in range(len(cl)):
    if cl[i]==city:
        loop=len(cl)-i
        break
#print(loop)
d=(k-count)%loop

for i in range(d):
    city=a[city-1]

print(city)

### FIXED CODE ###

import sys
import numpy

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=numpy.zeros(n,dtype=int)

city=1
count=0
while b[city-1]==0:
    count+=1
    b[city-1]=1
    
    city=a[city-1]

#arrive at city in count, len(cl)=count
if k<count:
    cc=1
    for i in range(k):
        cc=a[cc-1]
    print(cc)
    sys.exit()

c=1
cnt=0
while c!=city:
    cnt+=1
    c=a[c-1]

loop=count-cnt

d=(k-count)%loop

for i in range(d):
    city=a[city-1]

print(city)
### BUGGY CODE ###

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

balls = ""
while True:
    for i in range(A):
        balls += "b"
    for i in range(B):
        balls += "r"
    if len(balls) >= N:
        break

print(balls[:N].count("b"))


### FIXED CODE ###

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

ans = A * (N // (A + B))
if N % (A + B) > A:
    ans += A
else:
    ans += N % (A + B)

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

n,a,b,*h=map(int,open(0).read().split());i,j=0,-(-max(h)*n//a)
while j-i>1:
 k=c=(j+i+1)//2
 for t in h:c+=min(0,(b*k-t)//(a-b))
 if c>=0:j=k
 else:i=k
print(j)

### FIXED CODE ###

n,a,b,*h=map(int,open(0).read().split())
i,j=0,-(-max(h)*n//a)
while True:
  if j-i<2:
    print(j)
    break
  k=c=(j+i+1)//2
  for t in h:
    t-=b*k
    if t>0:
      c+=-t//(a-b)
  if c>=0:
    j=k
  else:
    i=k
### BUGGY CODE ###

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

A = [K]*N

for r in range(Q):
  correct = int(input())
  for i in range(N):
    if i != correct-1:
      A[i] = A[i] - 1

for i in range(N):
  if A[i] > 0:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

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

A = [K]*N
C = [0]*N

for r in range(Q):
  correct = int(input())
  C[correct-1] = C[correct-1] + 1

for i in range(N):
  A[i] = A[i] - Q + C[i]
  
  if A[i] > 0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

N=int(input())
A=[a-i-1 for i,a in enumerate(map(int,input().split()))]
k=abs(sum(A)//N+1)
print(min(sum(abs(a-x)for a in A)for x in range(-k-1,k+1)))

### FIXED CODE ###

N=int(input())//2
A=sorted(a-i-1 for i,a in enumerate(map(int,input().split())))
print(sum(abs(a-A[N])for a in A))
### BUGGY CODE ###

def main():
    from collections import Counter
    s = input()

    n = 2019
    l = [0]
    for i, x in enumerate(s[::-1]):
        y = l[-1] + int(x) * pow(10, i)
        z = y % n
        l.append(z)

    c = Counter(l)
    ans = sum([v * (v - 1) // 2 for v in c.values()])
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    s = input()

    n = 2019
    l = [0]
    t = 1
    for i, x in enumerate(s[::-1]):
        t = t * 10 % n
        y = (l[-1] + int(x) * t) % n
        l.append(y)

    c = Counter(l)
    ans = sum([v * (v - 1) // 2 for v in c.values()])
    print(ans)


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

import fractions

def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    ans = 1
    for i_out in range(len(A)):
        A_ith = [A[i] for i in range(len(A))]
        del A_ith[i_out]
        ans = max(ans, cal_all_gcb(A_ith))
    print(ans)

def cal_all_gcb(A):
    gcd = A[0]
    for j in range(1, len(A)):
        gcd = fractions.gcd(gcd, A[j])
    return gcd

main()

### FIXED CODE ###

import fractions as f

N = int(input())
A = [int(i) for i in input().split()]
L = [A[0]]
for i in range(1, N):
    L.append(f.gcd(L[-1], A[i]))
A.reverse()
R = [A[0]]
for i in range(1, N):
    R.append(f.gcd(R[-1], A[i]))
R.reverse()
ans = 0
for i in range(N):
    if i == 0:
        ans = max(ans, R[1])
    elif i == N - 1:
        ans = max(ans, L[N - 2])
    else:
        ans = max(ans, f.gcd(L[i - 1], R[i + 1]))
print(ans)
### BUGGY CODE ###

def main():
    n,m = map(int,input().split())
    ab = []
    cnt = [0] * n
    road = [[] for i in range(n)]

    for _ in range(m):
        a, b = map(int,input().split())
        ab.append([a-1,b-1])
        cnt[a-1] += 1
        cnt[b-1] += 1
        road[a-1].append(b-1)
        road[b-1].append(a-1)

    dist = [10**7] * n
    dist[0] = 0
    ans = [0] * n
    cnt = 0
    while True:
        for i, aa in enumerate(road):
            for j, t in enumerate(aa):
                if dist[i] > dist[t]+1:
                    dist[i] = dist[t]+1
                    ans[i] = t + 1
                    flg = True


        cnt += 1
        if cnt == 1000:
            break
        if flg :
            flg = False
            continue
        else:
            break

    f = 'Yes'
    for i in range(n):
        if dist[i] == 10**7:
            f = 'No'
            break
        else:
            continue
    print(f)
    for i in range(1,n):
        print(ans[i])


if __name__=='__main__':
    main()


### FIXED CODE ###

import queue
def main():
    n,m = map(int,input().split())
    ab = [[] for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    q =queue.Queue()
    q.put(0)
    ans = [-1] * n
    ans[0] = 0
    while q:
        now = q.get()
        for i, next in enumerate(ab[now]):
            if ans[next] == -1:
                ans[next] = now+1
                q.put(next)
        if q.empty():
            break
    print('Yes')
    for i in range(1,n):
        print(ans[i])



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

# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
event=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	event.append(  ( s-x ,1, x) )	#Start
	event.append(  ( t-x,-1, x) )	#End


for i in range(Q):
	d=int(sys.stdin.readline().strip())
	event.append(  (d ,0, i) )

event.sort(key=lambda x:(x[0]) )

stop=set()

ans=defaultdict(lambda: -1)
is_stop=False
minstop=float("inf")


for s,flag,x in event:
	if flag==1:
		stop.add(x)
		if x<minstop:
			minstop=x
			is_stop=True
	elif flag==-1:
		try:
			stop.remove(x)
		except:
			pass
		if minstop==x:
			is_stop=False
	elif flag==0:
		if stop:
			if not is_stop:
				minstop=min(stop)
				is_stop=True
			ans[x]=minstop
		else:
			ans[x]=-1


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


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right

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

S=[]
event=[]	#x, s, t
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	heappush( event, (x, max(0,s-x) , max(0,t-1-x)) )


D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
D.sort()
ans=[ float("inf") for _ in range(Q) ]

Next=[ i+1 for i in range(Q) ]	#Next


while event:
	x,s,t=heappop(event)
	start=bisect_left(D,s)
	end=bisect_right(D,t)

	i=start
	while i<end:
		ans[i]=min(ans[i],x)
		next=Next[i]
		Next[i]=end
		i=next

for x in ans:
	if x==float("inf"):
		print -1
	else:
		print x