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

n = int(input())
l = list(int(x) for x in input().split())
l.sort()
ans = set()
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if l[i]+l[j]>l[k]:
                if l[i] > l[k]-l[j]:
                    ans.add((l[i], l[j], l[k]))
            else:
                break
print(len(ans))

### FIXED CODE ###

import bisect

n = int(input())
l = list(int(x) for x in input().split())
l.sort()
ans = 0
for i in range(n):
    for j in range(i+1, n):
        key = bisect.bisect_left(l, l[j]-l[i]+1)
        ans += max([0, i-key])
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

for length_s in range(N//2, 0, -1):
    for start_s in range(0, N-length_s):
        check_s = S[start_s:start_s+length_s]
        if length_s > N - start_s - length_s:
            break
        if check_s in S[start_s+length_s:]:
            print(length_s)
            exit()
print(0)


### FIXED CODE ###

N = int(input())
S = input()

ans = 0
len_s = 1
for i in range(N):
    tmp_s = S[i:i+len_s]
    while tmp_s in S[i+len_s:]:
        len_s += 1
        tmp_s = S[i:i+len_s]
        ans += 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env/ python3
#S = input()
N = int(input())
#A, B, C = input().split()
#N, M = map(int, input().split())

#N = int(input())
#A = [int(x) for x in input().split()]

#H, W = map(int, input().split())
S = []
count = 0
for i in range(N):
    tmp = input()
    if tmp not in S:
        count += 1
        S.append(tmp)
print(count)

### FIXED CODE ###

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

#N = int(input())
#A = [int(x) for x in input().split()]

#H, W = map(int, input().split())
S = [input() for _ in range(N)]
print(len(set(S)))
### BUGGY CODE ###

def main():
    n,t=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*n]
    ab.sort(key=lambda x:x[0])
    dp=[0]*(t+1)
    for a,b in ab:
        for i in range(t-1,-1,-1):
            if a+i>=t:
                dp[t]=max(dp[t],dp[i]+b)
            else:
                dp[i+a]=max(dp[i+a],dp[i]+b)
    print(max(dp))
main()


### FIXED CODE ###

def main():
    n,t=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*n]
    ab.sort(key=lambda x:x[0])
    dp=[0]*(t+1)
    for a,b in ab:
        for i in range(t-1,-1,-1):
            if a+i>=t:
                dp[t]=max(dp[t],dp[i]+b)
            else:
                dp[i+a]=max(dp[i+a],dp[i]+b)
    print(max(dp))
main()
### BUGGY CODE ###

N = int(raw_input())
S = str(raw_input())
opt_cnt = N
for i in range(N):
    first = S[:i]
    second = S[i+1:]
    cnt = first.count('W') + second.count('E')
    if opt_cnt > cnt:
        opt_cnt = cnt
print(opt_cnt)


### FIXED CODE ###

def opt(N, S):
    if N == 1:
        return 0
    else:
        split = int(N/2)
        return min(opt(split,S[:split])+S[split:].count('E'),S[:split].count('W')+opt(N - split,S[split:]))

Num = int(raw_input())
Str = str(raw_input())
print(opt(Num, Str))
### BUGGY CODE ###

H,W = map(int,input().split())
A = [input() for _ in range(H)]
C = [-1,1]
ans = [[-2]*(W+2)] + [[-2] + [-1]*W + [-2] for _ in range(H)] + [[-2]*(W+2)]
count = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            ans[i+1][j+1] = 0
            count += 1
num = 0
while count < H*W:
    num += 1
    for i in range(H):
        for j in range(W):
            if ans[i+1][j+1] == num - 1:
                for x in C:
                    if ans[i+1+x][j+1] == -1:
                        ans[i+1+x][j+1] = num
                        count += 1
                for y in C:
                    if ans[i+1][j+1+y] == -1:
                        ans[i+1][j+1+y] =num
                        count += 1

print(num)

### FIXED CODE ###

H,W = map(int,input().split())
A = [input() for _ in range(H)]
ans = [[10000]*(W+2) for _ in range(H+2)]
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            ans[i+1][j+1] = 0

for i in range(H):
    for j in range(W):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j]+1)
for i in range(H):
    for j in range(W-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j+2]+1)
for j in range(W):
    for i in range(H):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i][j+1]+1)
for j in range(W):
    for i in range(H-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+2][j+1]+1)

num = 0
for i in range(H):
    for j in range(W):
        num = max(num,ans[i+1][j+1])

print(num)
### BUGGY CODE ###

import sys
from heapq import heappop, heappush

n, m, ss, *uvabcd = map(int, sys.stdin.buffer.read().split())
uuu = uvabcd[0:4 * m:4]
vvv = uvabcd[1:4 * m:4]
aaa = uvabcd[2:4 * m:4]
bbb = uvabcd[3:4 * m:4]
ccc = uvabcd[4 * m + 0::2]
ddd = uvabcd[4 * m + 1::2]
links = [set() for _ in range(n)]

for u, v, a, b in zip(uuu, vvv, aaa, bbb):
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))

req = sum(sorted(aaa, reverse=True)[:n])
INF = 10 ** 18
ans = [INF] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        if (ns, u) in visited:
            continue
        heappush(q, (t + b, ns, u))

    ts = s
    tt = t
    c = ccc[v]
    d = ddd[v]
    while ts <= req:
        ts += c
        tt += d
        if (ts, v) in visited:
            break
        heappush(q, (tt, ts, v))

print('\n'.join(map(str, ans[1:])))


### FIXED CODE ###

import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

print('\n'.join(map(str, ans[1:])))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(m)]

pre = [[] for _ in range(n)]

for i in range(m):
    pre[p[i][0] - 1].append(p[i][1])

for i in range(m):
    pref = "{:0>6}".format(p[i][0])

    years = pre[p[i][0] - 1]
    years.sort()

    y = years.index(p[i][1]) + 1
    year = "{:0>6}".format(y)
    print(pref + year)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
p = [list(map(int, input().split()+[i])) for i in range(m)]

p.sort()
cnt = 0
pre = -1

for city in p:
    if city[0] == pre:
        cnt = cnt + 1
    else:
        pre = city[0]
        cnt = 1

    city.append("{:0>6}{:0>6}".format(city[0], cnt))

p.sort(key = lambda x: x[2])

for city in p:
    print(city[3])
### BUGGY CODE ###

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

ans = 0
p = list(itertools.combinations(A,2))
for i in range(len(p)):
    ans += p[i][0]*p[i][1]

print(ans % (10**9+7))

### FIXED CODE ###

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

#累積和のリストを作成
S = [0]*(N+1)
ans = 0
for i in range(N):
    S[i+1] = A[i] + S[i]%mod

#累積和って感じですね
for i in range(N):
    sum = S[N] - S[i + 1]
    if sum < 0:
        sum += mod
    ans += A[i] * sum

print(ans % mod)
### BUGGY CODE ###

import bisect
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
N,M = map(int,readline().split())
A = np.array(readline().split(),np.int64)
#print(A)
C = np.cumsum(A)
#print(C)
ans = np.sum(C % M == 0)
for i in range(N-1):
  C -= A[i]
  C = C[1:]
  #print(C)
  ans += np.sum(C % M == 0)
print(ans)

### FIXED CODE ###

from collections import defaultdict
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
N,M = map(int,readline().split())
A = np.array(readline().split(),np.int64)
A = np.insert(A,0,0)
C = np.cumsum(A)
C %= M
ans = 0
d = defaultdict(int)
for i in range(N+1):
  ans += d[C[i]]
  d[C[i]] += 1
print(ans)
### BUGGY CODE ###

N=int(input())
S=input()

sw=0
for L in range(N-1,0,-1):
  tmp=[]
  for i in range(N-L+1):
    tmp.append([S[i:i+L],i])
  tmp.sort()
  #print(tmp)
  
  old_tmp=tmp[0]
  for i in range(1,N-L+1):
    if tmp[i][0]==old_tmp[0]:
      if tmp[i][1]>=L+old_tmp[1]:
        sw=1
        break
    else:
      old_tmp=tmp[i]
  if sw==1:
    break
print(L if sw==1 else 0)

### FIXED CODE ###

N = int(input())
S = input()

T = [[0 for _ in range(N)] for _ in range(N)]

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

answer = 0
for i in range(N):
  for j in range(N):
    if T[i][j] and j - i >= T[i][j]:
      answer = max(answer, T[i][j])
print(answer)
### BUGGY CODE ###

import numpy as np
from collections import deque

H, W = map(int, input().split())
maze = np.array([input() for _ in range(H)])


def bfs(sty, stx):
    visited = np.array([[-1 for _ in range(W)] for _ in range(H)])
    q = deque()
    q.append((sty, stx, 0))


    def is_ok(y, x):
        if not 0 <= y <= H - 1:
            return False
        if not 0 <= x <= W - 1:
            return False
        if visited[y][x] != -1:
            return False
        if maze[y][x] == '#':
            return False
        return True


    while q:
        y, x, lv = q.popleft()
        visited[y][x] = lv
        for i in (-1, 1):
            if is_ok(y+i, x):
                q.append((y+i, x, lv+1))
            if is_ok(y, x+i):
                q.append((y, x+i, lv+1))

    return np.max(visited)

res = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            steps = bfs(i, j)
            if steps > res:
                res = steps

print(res)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
maze = [input() for _ in range(H)]


def bfs(sty, stx):
    visited = [[-1]*W for _ in range(H)]
    q = deque()
    visited[sty][stx] = 0
    q.append((sty, stx, 0))


    def is_ok(y, x):
        if not 0 <= y <= H - 1:
            return False
        if not 0 <= x <= W - 1:
            return False
        if visited[y][x] != -1:
            return False
        if maze[y][x] == '#':
            return False
        return True


    while q:
        y, x, lv = q.popleft()
        for i in (-1, 1):
            if is_ok(y+i, x):
                visited[y+i][x] = lv+1
                q.append((y+i, x, lv+1))
            if is_ok(y, x+i):
                visited[y][x+i] = lv + 1
                q.append((y, x+i, lv+1))

    return max(max(r) for r in visited)

res = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            res = max(res, bfs(i, j))

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

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

for i in range(N - 1):
    for j in range(i + 1, N):
        if A[i] == A[j]:
            print("NO")
            exit()

print("YES")

### FIXED CODE ###

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

A.sort()
# print(A)
# print(N//2)
for i in range(N // 2):
    # print(i)
    # print(A[i])
    # print(A[i+1])
    
    if A[i] == A[i+1]:
        print("NO")
        exit()
    elif A[-1-i] == A[-2-i]:
        print("NO")
        exit()

print("YES")
### BUGGY CODE ###

from fractions import gcd as bltin_gcd
import itertools

def coprime2(a, b):
    return bltin_gcd(a, b) == 1

A, B = map(int, input().split())
koyakusuu_list = []
for a in range(1, A+1):
    if a == 1:
        koyakusuu_list.append(1)
    elif B % a == 0 and A % a == 0:
        flag = 0
        for kouyakusuu in koyakusuu_list:
            if coprime2(a, kouyakusuu):
                continue
            else:
                flag += 1
        if flag == 0:
            koyakusuu_list.append(a)

print(len(set(koyakusuu_list)))

### FIXED CODE ###

import fractions

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

f = fractions.gcd(A, B)

kouyakusuu = []

if f % 2 == 0:
    kouyakusuu.append(2)
    while f % 2 == 0:
        f = f / 2

i = 3
while i*i <= f:
    if f % i == 0:
        kouyakusuu.append(i)
        while f % i == 0:
            f = f / i
    i += 2
if f != 1:
    kouyakusuu.append(f)
print(len(kouyakusuu)+1)
### BUGGY CODE ###

n,w = map(int,input().split())
weight = []
value = []
for i in range(n):
    tmp1,tmp2 = map(int,input().split())
    weight.append(tmp1)
    value.append(tmp2)

#dp[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値
dp = [[0 for i in range(w+1)] for j in range(n+1)]
dp[1][weight[0]] = value[0]

for i in range(1,n):
    for j in range(w+1):
        if j - weight[i] >= 0:
            dp[i+1][j] = max(dp[i][j-weight[i]]+value[i],dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
            
print(dp[n][w])

### FIXED CODE ###

n,w = map(int,input().split())
weight = [0 for i in range(n)]
value = [0 for i in range(n)]
for i in range(n):
    weight[i],value[i] = map(int,input().split())
    

#dp[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値
dp = [[None for i in range(w+1)] for j in range(n+1)]
dp[1][weight[0]] = value[0]

for i in range(1,n):
    for j in range(w+1):
        if j - weight[i] >= 0:
            if dp[i][j-weight[i]] != None and dp[i][j] != None:
                dp[i+1][j] = max(dp[i][j-weight[i]]+value[i],dp[i][j])
            elif dp[i][j-weight[i]] == None and dp[i][j] != None:
                dp[i+1][j] = dp[i][j]
            elif dp[i][j-weight[i]] != None and dp[i][j] == None:
                dp[i+1][j] = dp[i][j-weight[i]]+value[i]
            else:
                dp[i+1][weight[i]] = value[i]
        else:
            dp[i+1][j] = dp[i][j]
            
print(max(i for i in dp[n] if i is not None))
### BUGGY CODE ###

import bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = xs[:l], r - l, xs[r:]
if len(low) > len(high):
    low, high = list(map(neg, high)), list(map(neg, low))
else:
    high = high[::-1]
acc = list(accumulate(high[::-1]))[::-1]

factor = 2 ** n0
lsums = sum((Counter(map(sum, combinations(low, 1 + i))) for i in range(len(low))), Counter())

ans = 0
for lsum, cnt in lsums.items():
    tmp = 0
    q = deque()
    q.append((0, lsum))
    while len(q) > 0:
        i, v = q.popleft()
        if i + 1 < len(high) and v + acc[i + 1] >= 0:
            q.append((i + 1, v))
        if i >= len(high):
            continue
        v += high[i]
        if v == 0:
            tmp += 1
            continue
        if v < 0:
            q.append((i + 1, v))
    ans += tmp * cnt

ans *= factor
ans += 2 ** n0 - 1

print(ans)

### FIXED CODE ###

import bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = list(map(neg, xs[:l][::-1])), r - l, xs[r:]

def sums(arr):
    cntr = Counter([0])
    for v in arr:
        tmps = tuple(cntr.items())
        for u, cnt in tmps:
            cntr[u + v] += cnt
    del cntr[0]
    return cntr

lsums = sums(low)
hsums = sums(high)

ans = sum(hsums[a] * b for a, b in lsums.items())

ans *= 2 ** n0
ans += 2 ** n0 - 1

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

import numpy as np
n=int(input())
s=input()

r=[]
g=[]
b=[]

for i in range(0,n):
    if s[i]=='R':
        r.append(i)

    elif s[i]=='G':
        g.append(i)

    elif s[i]=='B':
        b.append(i)

s=0
rl=len(r)
gl=len(g)
bl=len(b)
#ml=max(rl,gl,bl)
#if  ml==rl:
#    d1=r
#    d2=g
#    d3=b
#elif ml==gl:
#    d1=g
#    d2=r
#    d3=b
#else:
#    d1=b
#    d2=g
#    d3=r

for i1 in r:
    for i2 in g:
        if (min(i1,i2)-np.abs(i1-i2)) in b:
            s+=1
        if (max(i1,i2)+np.abs(i1-i2)) in b:
            s+=1
        if (i1+i2)/2.0 in b:
            s+=1

s2=rl*gl*bl-s
print(s2)

### FIXED CODE ###

import numpy as np
n=int(input())
s=input()

r=[]
g=[]
b=[]

for i in range(0,n):
    if s[i]=='R':
        r.append(i)

    elif s[i]=='G':
        g.append(i)

    elif s[i]=='B':
        b.append(i)

s3=0
rl=len(r)
gl=len(g)
bl=len(b)

for i in range(0,n-2):
    n2=int((n+i)/2)+1
    for j in range(i,n2):
        k=2*j-i
        if k<=n-1:
            
            if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
                s3+=1
s2=rl*gl*bl-s3
print(s2)
### BUGGY CODE ###

N,M=map(int,input().split())
root=[[] for _ in range(N+1)]
ans=[0]*(N+1)

print('Yes')
f=0

for _ in range(M):
    a,b=map(int,input().split())
    root[a].append(b)
    root[b].append(a)

#print(root)

lis=[1]
done=set([1])
i=0
while len(done)!=N:
    lis_=[]
    
    for li in lis:
        lis_+=root[li]
        for r in root[li]:
            if not r in done:
                ans[r]=li
            
    lis=lis_
    done=done|set(lis)
    
    #print(lis)
print('\n'.join(map(str,ans[2:])))
    

### FIXED CODE ###

print('Yes')

from collections import deque  

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
#print(graph)

ans = [-1] * (n+1)
ans[0] = 0
ans[1] = 0

d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if ans[i] != -1:
            continue
        ans[i] = v
        d.append(i)

print(*ans[2:], sep="\n")
### BUGGY CODE ###

import sys

N = int(sys.stdin.readline())
A = [int(i) for i in sys.stdin.readline().split(' ')]

A.sort(reverse=True)
max_value = A.pop(0)
diff = [max_value]
ans = 0
for i in A:
    ans = ans + diff.pop(0)
    diff = diff + [i, i]

print(ans)

### FIXED CODE ###

import sys
from collections import deque

N = int(sys.stdin.readline())
A = [int(i) for i in sys.stdin.readline().split(' ')]

A.sort(reverse=True)
max_value = A.pop(0)
diff = deque([max_value])
ans = 0
for i in A:
    ans = ans + diff.popleft()
    diff.append(i)
    diff.append(i)

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

N = int(input())
x = list(map(int, input().split()))
y = [sum(x)] * N
  
for i in range(N):
  for j in range(N):
    if j % 2 == 1:
      index = (i + j) % N
      y[i] -= 2 * x[index]
    
str_y = map(str, y)
output = " ".join(str_y)
print(output)

### FIXED CODE ###

N = int(input())
x = list(map(int, input().split()))
y = [0] * N

odd = sum([n for i, n in enumerate(x) if i % 2 == 1])
even = sum([n for i, n in enumerate(x) if i % 2 == 0])
y[0] = even - odd

for i in range(N-1):
  y[i+1] = 2 * x[i] - y[i]


str_y = map(str, y)
output = " ".join(str_y)
print(output)
### BUGGY CODE ###

import collections
N = int(input())
count = {}

for _ in range(N):
    tmp = collections.OrderedDict(sorted(collections.Counter([s for s in input()]).items()))
    key = "".join(list(tmp.keys())) + "".join(map(str, list(tmp.values())))
    if key not in count.keys():
        count[key] = 1
    else:
        count[key] += 1
        
ans = 0
for v in [v for v in count.values() if v > 1]:
    ans += v * (v - 1) // 2

print(ans)

### FIXED CODE ###

import collections
N = int(input())
count = []

for _ in range(N):
    s = "".join(sorted(input()))
    count.append(s)

ans = 0
for v in collections.Counter(count).values():
    ans += v * (v - 1) // 2

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

S = str(input())
l = [0]* len(S)
for i in range(len(S)):
    T = S[i:]
    t = int(T)
    l[i] = t%2019
l.sort()
m = [0] * len(S)
k = 1
for i in range (len(S) - 1):
    if l[i] != l[i + 1]:
        m[i] = int(k*(k-1)/2)
        k = 1
    else:
        m[i] = 0
        k += 1
if k != 1:
    m[len(S) - 1] = int(k*(k-1)/2)
a = 0
for i in range(len(S)):
    if l[i] == 0:
        a += 1
    else:
        break
print(sum(m) + a)

### FIXED CODE ###

S = str(input())
l = [0]* len(S)
q = 1
l[0] = int(S[len(S) - 1])
for i in range(1,len(S)):
    t = int(S[len(S) - i - 1])
    q = q * 10 % 2019
    l[i] = (t*q + l[i - 1]%2019)%2019
l.sort()
m = [0] * len(S)
k = 1
for i in range (len(S) - 1):
    if l[i] != l[i + 1]:
        m[i] = int(k*(k-1)/2)
        k = 1
    else:
        m[i] = 0
        k += 1
if k != 1:
    m[len(S) - 1] = int(k*(k-1)/2)
a = 0
for i in range(len(S)):
    if l[i] == 0:
        a += 1
    else:
        break
print(sum(m) + a)
### BUGGY CODE ###

import math

n = int(input())
a = math.sqrt(n)

if n % a == 0.0:
    b = int(math.log10(a)) + 1
    print(b)
else:
    a = int(a)
    while n % a != 0:
        a = a + 1
    b = int(math.log10(a)) + 1
    print(b)

### FIXED CODE ###

import math


n = int(input())
a = math.sqrt(n)

if n % a == 0.0:
    b = int(math.log10(a)) + 1
    print(b)
else:
    a = int(a)
    for i in range(a, 0, -1):
    	if n % i == 0:
    		a = n / i
    		break
    b = int(math.log10(a)) + 1
    print(b)
### BUGGY CODE ###

N = int(input())
ans = 0

def prime(x):
    if x<2:
        return 0
    elif x %2 == 0:
        if x ==2:
            return 1
        else :
            return 0
    else:
        i = 3
        while i**2<= x:
            if x % i== 0:
                return 0
        return 1

for i in range(N):
    x = int(input())
    if prime(x) ==1:
        ans +=1
print(ans)

### FIXED CODE ###

import math

N = int(input())
ans = 0

def solve(x):
    if x==2:
        return 1
    elif x%2==0:
        return 0
    else:
        for i in range(3, math.ceil(math.sqrt(x)) + 1, 2):
            if x%i ==0:
                return 0
        return 1
for i in range(N):
    if solve(int(input())) ==1:
        ans +=1
print(ans)
### BUGGY CODE ###

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

event_list=[]
for i in range(N):
  S,T,X=map(int,input().split())
  event_list.append((S-X-0.5,1,X))
  event_list.append((T-X-0.5,-1,X))
  
dlist=[]
for i in range(Q):
  D=int(input())
  event_list.append((D,0,X))  
  dlist.append(D)
event_list.sort()
#print(event_list)

answer_dic={}
stop_set=set()
for t,f,x in event_list:
  if f==1:
    stop_set.add(x)
  elif f==-1:
    stop_set.remove(x)
  else:
    if len(stop_set)>0:
      answer_dic[t]=min(stop_set)
#print(answer_dic)

for d in dlist:
  if d in answer_dic:
    print(answer_dic[d])
  else:
    print(-1)

### FIXED CODE ###

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

event_list=[]
for i in range(N):
  S,T,X=map(int,input().split())
  event_list.append((S-X-0.5,1,X))
  event_list.append((T-X-0.5,-1,X))
  
dlist=[]
for i in range(Q):
  D=int(input())
  event_list.append((D,0,X))  
  dlist.append(D)
event_list.sort()
#print(event_list)

answer_dic={}
stop_set=set()
min_set=float("inf")
for t,f,x in event_list:
  if f==1:
    stop_set.add(x)
    if x<min_set:
      min_set=x
  elif f==-1:
    stop_set.remove(x)
    if x==min_set:
      if len(stop_set)>0:
        min_set=min(stop_set)
      else:
        min_set=float("inf")
  else:
    if len(stop_set)>0:
      answer_dic[t]=min_set
    else:
      answer_dic[t]=-1
#print(answer_dic)

for d in dlist:
  print(answer_dic[d])