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

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
H, W, K = map(int,readline().split())
x1, y1, x2, y2 = map(int,readline().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
C = read().split()

dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        dist[xx][yy] = dist[x][y] + 1
        d.append([xx, yy])
      else:
        break

print(dist[x2][y2])

### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
H, W, K = map(int,readline().split())
x1, y1, x2, y2 = map(int,readline().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
C = read().split()

dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

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

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

a_ol = []
a_counts = []
for i in a_uni:
    a_co = a.count(i)
    if a_co > 1:
        a_ol.append(i)
        a_counts.append(a_co)

def_count = sum([i * (i - 1) // 2 for i in a_counts])
for k in range(n):
    count = 0
    if a[k] in a_ol:
        a_counts[a_ol.index(a[k])] -= 1
        count = sum([i * (i - 1) // 2 for i in a_counts])
        a_counts[a_ol.index(a[k])] += 1
    else:
        count = def_count
    print(count)



### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))


a_ol = Counter(a)
def_count = 0
for item in a_ol.items():
    a_co = item[1]
    def_count += a_co * (a_co - 1)

def_count //= 2

for k in a:
    print(def_count - a_ol[k] + 1)
### BUGGY CODE ###

LIST=""
LIST=list(LIST)
c=0

def func(S):
    global LIST
    global c

    if(len(S)==0):
        c=1
    if(c==1):
        for i in range(len(LIST)-1,-1,-1):
            print(LIST[i])
        exit()

    So=S[::]
    for i in range(len(S)):
        S=So[::]
        if(S[i]==(i+1)):
            LIST.append(S.pop(i))
            func(S)
    if(len(LIST)>0):
        LIST.pop(-1)

N=int(input())
S=list(map(int,input().split()))
func(S)
print("-1")

### FIXED CODE ###

N=int(input())
S=list(map(int,input().split()))
LIST=list("")

for i in range(N):
    if((S[i] - i)>1):
        print("-1")
        exit()  

while(len(S)>0):
    c=10**10
    for i in range (len(S)):
        if(S[i]==i+1):
            c=i
    if(c==(10**10)):
        print("-1")
        exit()  
    LIST.append(S.pop(c))

for i in range(len(LIST)-1,-1,-1):
    print(LIST[i])
### BUGGY CODE ###

N, K = [int(_) for _ in input().split()]

P = [[int(_) for _ in input().split()] for n in range(N)]

X = []
Y = []
for n in range(N):
    x, y = P[n]
    X.append(x)
    Y.append(y)
X.sort()
Y.sort()

ans = 10 ** 20
for xi in range(N):
    for xj in range(xi+1, N):
        for yi in range(N):
            for yj in range(yi+1, N):
                x1, y1 = X[xi], Y[yi]
                x2, y2 = X[xj], Y[yj]
                c = 0
                for v in range(N):
                    x, y = P[v]
                    if x1 <= x <= x2 and y1 <= y <= y2:
                        c += 1
                if c >= K:
                    ans = min(ans, (x2-x1) * (y2-y1))
print(ans)


### FIXED CODE ###

N, K = [int(_) for _ in input().split()]

P = [[int(_) for _ in input().split()] for n in range(N)]

X = []
Y = []
for n in range(N):
    x, y = P[n]
    X.append(x)
    Y.append(y)
X.sort()
Y.sort()

ans = 10 ** 20
for xi in range(N):
    for xj in range(xi+1, N):
        for yi in range(N):
            for yj in range(yi+1, N):
                x1, y1 = X[xi], Y[yi]
                x2, y2 = X[xj], Y[yj]
                c = 0
                for v in range(N):
                    x, y = P[v]
                    if x1 <= x <= x2 and y1 <= y <= y2:
                        c += 1
                if c >= K:
                    ans = min(ans, (x2-x1) * (y2-y1))
print(ans)
### BUGGY CODE ###

n = int(input())
b = 1
a = list(map(int,input().split()))
if 0 in a:
    print(0)
else:
    for i in range(n):
        b *= int(a[i])
    if b > 10**18:
       print(-1)
    else:print(b)   

### FIXED CODE ###

n = int(input())
b = 1
a = list(map(int,input().split()))
if 0 in a:
    print(0)
else:
    for i in range(n):
        b *= a[i]
        if b > 10**18:
            print(-1)
            break
    if b <=10**18:
        print(b)
### BUGGY CODE ###

def work_through(): 
  i, j = 1, 1
  cnt = 0

  arr = []
  arr.append([i, j])

  n = int(input())

  while True:
    tmp = []
    length = len(arr)
    for i in range(0, length):
      x, y = arr.pop()
      if x * y == n:
        return cnt
      tmp.append([x + 1, y])
      tmp.append([x, y + 1])
    arr = tmp
    cnt += 1

print(work_through())

### FIXED CODE ###

import math

INF = 1e12
n = int(input())
cnt = INF
m = math.sqrt(n)

for i in range(1, math.ceil(m) + 1):
  if n % i == 0:
    j = n // i
    cnt = min(cnt, i + j - 2)
  else:
    continue

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

N,K = [int(i) for i in input().split()]
while abs(N-K) < N:
    N = abs(N-K)
print(N)

### FIXED CODE ###

N,K = map(int,input().split())
if N>=K:
    N = N%K
    while abs(N-K) < N:
        N = abs(N-K)
    print(N)
else:
    if K >= 2*N:
        print(N)
    else:
        N = K%N
        print(N)
### BUGGY CODE ###

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
l = [[0] * W for _ in range(H)]
r = [[0] * W for _ in range(H)]
u = [[0] * W for _ in range(H)]
d = [[0] * W for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '#':
            if j != 0:
                r[i][j] = r[i][j - 1] + 1
            else:
                r[i][j] = 1

for i in range(H):
    for j in reversed(range(W)):
        if S[i][j] != '#':
            if j != W - 1:
                l[i][j] = l[i][j + 1] + 1
            else:
                l[i][j] = 1

for i in range(W):
    for j in range(H):
        if S[j][i] != '#':
            if j != 0:
                d[j][i] = d[j - 1][i] + 1
            else:
                d[j][i] = 1

for i in range(W):
    for j in reversed(range(H)):
        if S[j][i] != '#':
            if j != H - 1:
                u[j][i] = u[j + 1][i] + 1
            else:
                u[j][i] = 1

for i in range(H):
    for j in range(W):
        tmp = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3
        ans = max(ans, tmp)

print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
l = [[0] * W for _ in range(H)]
r = [[0] * W for _ in range(H)]
u = [[0] * W for _ in range(H)]
d = [[0] * W for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '#':
            if j != 0:
                r[i][j] = r[i][j - 1] + 1
            else:
                r[i][j] = 1

for i in range(H):
    for j in reversed(range(W)):
        if S[i][j] != '#':
            if j != W - 1:
                l[i][j] = l[i][j + 1] + 1
            else:
                l[i][j] = 1

for i in range(W):
    for j in range(H):
        if S[j][i] != '#':
            if j != 0:
                d[j][i] = d[j - 1][i] + 1
            else:
                d[j][i] = 1

for i in range(W):
    for j in reversed(range(H)):
        if S[j][i] != '#':
            if j != H - 1:
                u[j][i] = u[j + 1][i] + 1
            else:
                u[j][i] = 1

for i in range(H):
    for j in range(W):
        tmp = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3
        ans = max(ans, tmp)

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

def func(cnt, cn):
    tmp = [0] * 13
    for i in range(13):
        nn = (cn + i) % 13
        tmp[nn] = cnt[i]
    return tmp


MOD = 10**9+7

s = list(input())
s.reverse()

cnt = [0]*13
cnt[0] = 1
t = 1
for ci in range(len(s)):
    t %= 13 
    if s[ci] != '?':
        cn = int(s[ci]) * t % 13
        cnt = func(cnt, cn)
    else:
        tmp = [0]*13
        add = [0]*13
        for cj in range(10):
            cn = cj * t % 13
            add = func(cnt, cn)
            for _ in range(13):
                tmp[_] += add[_]
                tmp[_] %= MOD
        cnt = tmp
    t *= 10
print(cnt[5])

### FIXED CODE ###

def func(cnt, cn):
    tmp = [0] * 13
    for i in range(13):
        nn = (cn + i) % 13
        tmp[nn] = cnt[i]
    return tmp


MOD = 10**9+7

s = list(input())
s.reverse()

cnt = [0]*13
cnt[0] = 1
t = 1
for ci in range(len(s)):
    t %= 13 
    if s[ci] != '?':
        cn = int(s[ci]) * t % 13
        cnt = func(cnt, cn)
    else:
        tmp = [0]*13
        add = [0]*13
        for cj in range(10):
            cn = cj * t % 13
            add = func(cnt, cn)
            for _ in range(13):
                tmp[_] += add[_]
                tmp[_] %= MOD
        cnt = tmp
    t *= 10
print(cnt[5])
### BUGGY CODE ###

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

for i in range(n):
    b.append(a[i])
    b = list(reversed(b))
print(*b)

### FIXED CODE ###

from collections import deque
n = int(input())
a = list(map(int,input().split()))
b = deque()
for i in range(n):
    if i % 2 == 0:
        b.appendleft(a[i])
    else:
        b.append(a[i])
if n % 2 == 0:
    print(*reversed(b))
else:
    print(*b)
### BUGGY CODE ###

n = int(input())

uvws = [list(map(int, input().split())) for _ in range(n - 1)]

Li = [0] * 2 + [2] * (n-1)

while 2 in Li:
    for uvw in uvws:
        u, v, w = uvw
        if Li[u] != 2 and Li[v] == 2:
            if w % 2 == 0:
                Li[v] = Li[u]
            else:
                Li[v] = 1 - Li[u]
        elif Li[v] != 2 and Li[u] == 2:
            if w % 2 == 0:
                Li[u] = Li[v]
            else:
                Li[u] = 1 - Li[v]

for i in range(n):
    print(Li[i+1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def tree_path():
    # 辺と長さが与えられる
    # 頂点1からの各点の距離を計算する
    # 距離が偶数か奇数かで色分け
    sys.setrecursionlimit(100000)
    n = int(input())
    path = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        # 無向グラフ
        path[u].append((v, w))
        path[v].append((u, w))
    # d[0]は使わない
    d = [-1] * (n + 1)

    def walk(i, c):
        if d[i] == -1:
            d[i] = c
            for x, w in path[i]:
                walk(x, c + w)

    walk(1, 0)
    for i in d[1:]:
        print(i % 2)

        
tree_path()
### BUGGY CODE ###

import numpy as np
import copy
N=int(input())
l=list(map(int, input().split())) 

cp = copy.copy(l)
 
if l[0]!=0:

  for k in range(1,N):
    if sum(l[:k])*sum(l[:k+1])>0:
      l[k]=-np.sign(sum(l[:k]))-sum(l[:k])

  if sum(l)==0:
    print(1+sum([abs(l[n]-cp[n]) for n in range(N)]))
  else:
    print(sum([abs(l[n]-cp[n]) for n in range(N)]))

  
else:#頭0のとき；和0なので変える =>1,-1にした時両方やって良いほうに
  #1にする場合
  sei_l=copy.copy(l)
  sei_l[0]=1
  for k in range(1,N):

    if sum(sei_l[:k])*sum(sei_l[:k+1])>0:

      sei_l[k]=-np.sign(sum(sei_l[:k]))-sum(sei_l[:k])

  if sum(sei_l)==0:
    c1=1+sum([abs(sei_l[n]-cp[n]) for n in range(N)])
  else:
    c1=sum([abs(sei_l[n]-cp[n]) for n in range(N)])  

  #-1にする場合
  fu_l=copy.copy(l)
  fu_l[0]=-1
  for k in range(1,N):

    if sum(fu_l[:k])*sum(fu_l[:k+1])>0:

      fu_l[k]=-np.sign(sum(fu_l[:k]))-sum(fu_l[:k])

  if sum(fu_l)==0:
    c2=1+sum([abs(fu_l[n]-cp[n]) for n in range(N)])
  else:
    c2=sum([abs(fu_l[n]-cp[n]) for n in range(N)])  
  
  print(max(c1,c2))


### FIXED CODE ###

from copy import copy
n = int(input())
a = [int(x) for x in input().split()]
ans1=[(-1)**i for i in range(n)]

b=copy(a)
res_b=0
sb=0
c=copy(a)
res_c=0
sc=0
for i in range(n):
  sb+=a[i]
  if ans1[i]*sb>0:
    pass
  else:
    b[i]=ans1[i]-(sb-b[i])
    sb=sb-a[i]+b[i]
    res_b+=abs(b[i]-a[i])

  sc+=a[i]
  if -1*ans1[i]*sc>0:
    pass
  else:
    c[i]=-1*ans1[i]-(sc-c[i])
    sc=sc-a[i]+c[i]
    res_c+=abs(c[i]-a[i])
  
print(min(res_b,res_c))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
from collections import deque
n, *lst = map(int, read().split())
a = deque(lst[:n])
b = lst[n:]
for k in range(n):
    tmp = set(ai ^ bi for ai, bi in zip(a, b))
    l_tmp = len(tmp)
    if l_tmp == 1:
        print(k, tmp.pop())
    a.rotate(-1)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())

A = list(map(int, readline().split()))
B = list(map(int, readline().split()))


def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


C = convert(A)
D = convert(B)


def Z_algorithm(S):
    # 共通接頭辞の長さを返す
    N = len(S)
    arr = [0] * N
    arr[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        arr[i] = j
        if not j:
            i += 1
            continue
        k = 1

        while i + k < N and k + arr[k] < j:
            k += 1
        i += k
        j -= k

    return arr


Z = Z_algorithm(D + [-1] + C + C)[N + 1:N + N + 1]

K = [i for i, x in enumerate(Z) if x == N]
X = [A[k] ^ B[0] for k in K]

print('\n'.join('{} {}'.format(k, x) for k, x in zip(K, X)))
### BUGGY CODE ###

a,v = map(int,input().split())
b,w = map(int,input().split())
t = int(input())

if((b-a) > 0):
  for i in range(t):
    a += v
    b += w
  if(a >= b):
    print("YES")
  else:
    print("NO")
    
elif((b-a) < 0):
  for i in range(t):
    a -= v
    b -= w
  if(a <= b):
    print("YES")
  else:
    print("NO")
    

### FIXED CODE ###

a,v = map(int,input().split())
b,w = map(int,input().split())
t = int(input())

if((b-a) > 0):
  a = a+v*t
  b = b+w*t
  if(a >= b):
    print("YES")
  else:
    print("NO")
    
elif((b-a) < 0):
  a = a-v*t
  b = b-w*t
  if(a <= b):
    print("YES")
  else:
    print("NO")
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
LA = len(A)
ans = A[0]
for i in range(LA-1):
    ans = ans*A[i+1]
if ans > 10**18:
    print('-1')
else:
    print(ans)



### FIXED CODE ###

import sys

N = int(input())
A = list(map(int, input().split()))
LA = len(A)
ans = A[0]
for j in range(LA):
    if A[j] == 0:
        print('0')
        sys.exit()

for i in range(LA-1):
    ans = ans*A[i+1]
    if ans > 10**18:
        print('-1')
        sys.exit()
        
print(ans)
### BUGGY CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


def main():
    N, K = map(int, readline().split())
    S = set()
    for k in range(K):
        L, R = map(int, readline().split())
        S |= set(range(L, R + 1))

    dp = [0] * (N + 1)
    dp[1] = 1
    S = list(S)

    for i in range(1, N + 1):
        for s in S:
            if i - s > 0:
                dp[i] += dp[i - s]
                dp[i] %= M
            else:
                continue
    print(dp[N])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


def segfunc(x, y):
    return x + y


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()

    A = [0] * (N + 1)
    A[1] = 1
    seg = SegTree(A, segfunc=segfunc, ide_ele=0)
    for i in range(2, N + 1):
        for l, r in LR:
            if i - l > 0:
                total = (seg.tree[i + seg.num] + seg.query(max(1, i - r), min(N, i - l + 1)) % M)
                seg.update(i, total)
            else:
                break
    print(seg.tree[seg.num + N] % M)


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

import sys

n=int(input())
l=[]
for i in range(n):
    l.append(input())
alp=[chr(_) for _ in range(97,97+26)]
res=[]
ans=0

for j in l:
    ll=list(j)
    ll.sort()
    aa="".join(ll)
    tmp2=0
    for z in res:
        if aa==z:
            tmp2+=1
    ans+=tmp2
    res.append(aa)

print(int(ans))

### FIXED CODE ###

import sys

n=int(input())
l=["".join(sorted(sys.stdin.readline().strip())) for i in range(n)]


res={}
ans=0
 
for j in range(n):
    ll=list(l[j])
    ll.sort()
    aa="".join(ll)
    if aa in res:
        ans+=res[aa]
        res[aa]+=1
    else:
        res[aa]=1

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

from collections import deque

h,w = map(int,input().split())
matrix = [[1]*(w+2)] + [list("a" + input() + "a") for _ in range(h)] + [[1]*(w+2)]

matrix_list1 = deque()
cnt = -1

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix[i][j] = 1
            matrix_list1.append([i,j])
        else:
            matrix[i][j] = 0

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if not matrix[x+1][y]:
            matrix[x+1][y] = 1
            matrix_list1.append([x+1,y])
        if not matrix[x-1][y]:
            matrix[x-1][y] = 1
            matrix_list1.append([x-1,y])
        if not matrix[x][y+1]:
            matrix[x][y+1] = 1
            matrix_list1.append([x,y+1])
        if not matrix[x][y-1]:
            matrix[x][y-1] = 1
            matrix_list1.append([x,y-1])
    cnt += 1
    
print(cnt)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
matrix = [["a" for _ in range(w+2)]] + [list("a" + input() + "a") for _ in range(h)] + [["a" for _ in range(w+2)]]

matrix_list1 = deque()
cnt = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list1.append([x,y-1])
    else:
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)
### BUGGY CODE ###

from itertools import combinations

N, K = [int(n) for n in input().split()]
h = [int(input()) for _ in range(N)]
ans = 10**9+1
for c in combinations(h, K):
    mc = max(c)-min(c)
    if ans > mc:
      ans = mc
print(ans)


### FIXED CODE ###

N, K = [int(n) for n in input().split()]
h = sorted([int(input()) for _ in range(N)])
ans = 10**9
for i in range(N-K+1):
    ans = min(ans, h[i+K-1]-h[i])
print(ans)
### BUGGY CODE ###

import bisect


class SegTree:

    def __init__(self, n):
        # supposed that n = 2**m
        self.n = n
        self.val = [-1] * (2 * n - 1)

    def _update(self, a, b, v, k, l, r):
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.val[k] = v
        else:
            self._update(a, b, v, 2 * k + 1, l, (l + r) // 2)
            self._update(a, b, v, 2 * k + 2, (l + r) // 2, r)

    def update(self, a, b, v):
        # 区間[a, b)上の値をvに更新
        self._update(a, b, v, 0, 0, self.n)

    def query(self, x):
        # ノードxの値を返す
        k = self.n + x - 1
        ret = self.val[k]
        while k > 0:
            k = (k - 1) // 2
            ret = max(ret, self.val[k])
        return ret


def main():
    N, Q = list(map(int, input().split(' ')))
    work_list = [list(map(int, input().split(' '))) for _ in range(N)]
    # 工事は出発地から遠い順に並べておく
    work_list.sort(key=lambda work: work[2], reverse=True)
    D = [int(input()) for _ in range(Q)]
    # 一番最初に引っかかる工事のインデックスを求める
    QQ = 1
    while QQ < Q:
        QQ <<= 1
    tree = SegTree(QQ)
    for w, work in enumerate(work_list):
        s, t, x = work
        # s - x <= d < t - x だと工事に引っかかる
        left = bisect.bisect_left(D, s - x)
        right = bisect.bisect_left(D, t - x)
        tree.update(left, right, w)
    for q in range(Q):
        w = tree.query(q)
        if w == -1:
            print(-1)
        else:
            print(work_list[w][2])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect
 
 
class SegTree:
 
    def __init__(self, n):
        # supposed that n = 2**m
        self.n = n
        self.val = [-1] * (2 * n - 1)
 
    def _update(self, a, b, v, k, l, r):
        # 区間[a, b)上の値をvに更新
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.val[k] = v
        else:
            self._update(a, b, v, 2 * k + 1, l, (l + r) // 2)
            self._update(a, b, v, 2 * k + 2, (l + r) // 2, r)
 
    def query(self, x):
        # ノードxの値を返す
        k = self.n + x - 1
        ret = self.val[k]
        while k > 0:
            k = (k - 1) // 2
            ret = max(ret, self.val[k])
        return ret
 
 
def main():
    N, Q = list(map(int, input().split(' ')))
    work_list = [list(map(int, input().split(' '))) for n in range(N)] 
    # 工事は出発地から遠い順に並べておく
    work_list.sort(key=lambda work: work[2], reverse=True)
    D = [int(input()) for q in range(Q)]
    # 一番最初に引っかかる工事のインデックスを求める
    QQ = 1
    while QQ < Q:
        QQ <<= 1
    tree = SegTree(QQ)
    for w, work in enumerate(work_list):
        s, t, x = work
        # s - x <= d < t - x だと工事に引っかかる
        left = bisect.bisect_left(D, s - x)
        right = bisect.bisect_left(D, t - x)
        tree._update(left, right, w, 0, 0, QQ)
    for q in range(Q):
        w = tree.query(q)
        if w == -1:
            print(-1)
        else:
            print(work_list[w][2])
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from itertools import combinations
N = int(input())
L = list(map(int, input().split()))
ans = 0
for i,j,k in list(combinations(L,3)):
  if max(i,j,k)*2 < i+j+k:
    ans += 1
print(ans)

### FIXED CODE ###

from itertools import combinations
import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i,j in list(combinations(L,2)):
  if j < 2*i:
    ans += max(0, bisect.bisect_left(L, i+j) - bisect.bisect_right(L, j-i)-2)
  else:
    ans += max(0, bisect.bisect_left(L, i+j) - bisect.bisect_right(L, j-i)-1)
print(ans//3)