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

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *A, = map(int, input().split())

    dp = [0] * (S + 1)

    ans = 0
    for x in A:
        ans = (ans + dp[S] + (dp[S - x] if S - x >= 0 else 0) + (1 if S - x == 0 else 0)) % MOD
        for s in range(S, 0, -1):
            if s - x >= 0:
                v = dp[s - x] + (1 if s - x == 0 else 0)
                dp[s] = (dp[s] + v) % MOD
        dp[0] += 1

    print(ans)


if __name__ == '__main__':
    main()

#             dp[i + 1][s][0] = (dp[i + 1][s][0] + dp[i][s][0]) % MOD
#             dp[i + 1][s][1] = (dp[i + 1][s][1]
#                                + dp[i][s][1] + (dp[i][s - x][1] if s - x >= 0 else 0)
#                                + dp[i][s][0] + (dp[i][s - x][0] if s - x >= 0 else 0)) % MOD
#             dp[i + 1][s][2] = (dp[i + 1][s][2]
#                                + dp[i][s][2] +
#                                dp[i][s][1] + (dp[i][s - x][1] if s - x >= 0 else 0)
#                                + dp[i][s][0] + (dp[i][s - x][0] if s - x >= 0 else 0)) % MOD

#     for i, x in enumerate(A):
#         dp[i + 1][0][0] = dp[i][0][0]
#         for s in range(S, -1, -1):
#             dp[i + 1][s][1] = (dp[i][s][1] + dp[i][s][0]) % MOD
#             dp[i + 1][s][2] = (dp[i][s][2] + dp[i][s][1] + dp[i][s][0]) % MOD
#
#             if s - x >= 0:
#                 v = dp[i][s - x][1] + dp[i][s - x][0]
#                 dp[i + 1][s][1] = (dp[i + 1][s][1] + v) % MOD
#                 dp[i + 1][s][2] = (dp[i + 1][s][2] + v) % MOD

#         dp[i + 1][0][0] = dp[i][0][0]
#         dp[i + 1][0][1] = (dp[i][0][1] + dp[i][0][0]) % MOD
#         dp[i + 1][0][2] = (dp[i][0][2] + dp[i][0][1] + dp[i][0][0]) % MOD
#         for s in range(S, 0, -1):
#             dp[i + 1][s][1] = dp[i][s][1] % MOD
#             dp[i + 1][s][2] = (dp[i][s][2] + dp[i][s][1]) % MOD
#             if s - x >= 0:
#                 v = dp[i][s - x][1] + dp[i][s - x][0]
#                 dp[i + 1][s][1] = (dp[i + 1][s][1] + v) % MOD
#                 dp[i + 1][s][2] = (dp[i + 1][s][2] + v) % MOD

#     for x in A:
#         for s in range(S, 0, -1):
#             dp[s][1] += dp[s][0]
#             if s - x >= 0:
#                 v = dp[s - x][0] + (1 if s - x == 0 else 0)
#                 dp[s][0] += v
#                 dp[s][1] += v
#             dp[s][0] %= MOD
#             dp[s][1] %= MOD
#         dp[0][0] += 1
#         dp[0][1] += (dp[0][0] + 1)


### FIXED CODE ###

# https://atcoder.jp/contests/abc159/submissions/11139734

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

    dp = [0] * (S + 1)

    ret = 0
    for i, x in enumerate(a):
        dp[0] += 1
        if x > S: continue
        ret = (ret + dp[S - x] * (N - i)) % MOD
        for k in range(S - 1, x - 1, -1):
            dp[k] = (dp[k] + dp[k - x]) % MOD

    print(ret)


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

n,m=map(int,input().split())
x=[0]*n
y=[0]*n
for i in range(n):
  x[i],y[i]=map(int,input().split())
ans=10**19
for i in range(n):
  for j in range(n):
    for k in range(n):
      for l in range(n):
        xl=min(x[i],x[j],x[k],x[l])
        xr=max(x[i],x[j],x[k],x[l])
        yl=min(y[i],y[j],y[k],y[l])
        yh=max(y[i],y[j],y[k],y[l])
        cnt=0
        for c in range(n):
          cnt+=xl<=x[c]<=xr and yl<=y[c]<=yh
        if cnt>=m:ans=min(ans,(xr-xl)*(yh-yl))
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
x=[0]*n
y=[0]*n
for i in range(n):
  x[i],y[i]=map(int,input().split())
ans=10**19
for i in range(n):
  for j in range(i,n):
    for k in range(j,n):
      for l in range(k,n):
        xl=min(x[i],x[j],x[k],x[l])
        xr=max(x[i],x[j],x[k],x[l])
        yl=min(y[i],y[j],y[k],y[l])
        yh=max(y[i],y[j],y[k],y[l])
        cnt=0
        for c in range(n):
          cnt+=xl<=x[c]<=xr and yl<=y[c]<=yh
        if cnt>=m:ans=min(ans,(xr-xl)*(yh-yl))
print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
P = list(map(int,input().split()))
P = np.array(P)
ans = 0
for i in range(N):
  if P[i] == min(P[:i+1]):
    ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
m = N + 1
ans = 0
for i in P:
  if i <= m:
    ans += 1
    m = i
  else:
    continue
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
doubleA = {}
doubleA[1] = A
now = 1
 
for i in range(len(bin(k))-2):
    if (k>>i)&1:
        now = doubleA[i+1][now-1]
    doubleA[i+2] = {}
    for j in range(n):
        doubleA[i+2][j] = doubleA[i+1][doubleA[i+1][j]-1]
print(now)

### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
now = 1
 
for i in range(len(bin(k))-2):
    if (k>>i)&1:
        now = A[now-1]
    A = [A[a-1] for a in A]
print(now)
### BUGGY CODE ###

import math
import collections
 
def main():
    halfdic={}
    n = int(input())
    num_list = list(map(int, input().split()))  
    for i in range(len(num_list)):
        ansdic = {}
        pop = num_list.pop(i)
        if pop in halfdic.keys():
            print(halfdic[pop])
            num_list.insert(i, pop)            
        else:
            dic = collections.Counter(num_list)
            for k, j in dic.items():
                if j < 2:
                  pass
                else:
                  ansdic[k] = int(j * (j-1)/2)
            print(sum(ansdic.values()))
            halfdic[pop] = sum(ansdic.values())
            num_list.insert(i, pop)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import math
    n = int(input())
    inlis = list(map(int, input().split()))
    indic = dict()
    total = 0

    for num in inlis:
        if num in indic:
            indic[num] += 1
        else:
            indic[num] = 1
    
    for k, v in indic.items():
        total += int(v * (v-1) / 2)
    
    for num in inlis:
        print(total - indic[num] + 1)





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

import numpy as np
N, K = map(int, raw_input().split())

ans = 0
mi_prev = 0
for i in reversed(range(1, N+1)):
    for mi in range(mi_prev, K):
        if i*2**mi >= K:
            break

    ans += (1.0/2)**mi
    mi_prev = mi

ans = ans/N
print ans



### FIXED CODE ###

import numpy as np
import math
N, K = map(int, raw_input().split())

ans = 0
for i in range(1, N+1):

    mi = np.log2(1.0*K/i)

    mi = max(mi,0)
    mi = math.ceil(mi)
    ans += (1.0/2)**mi

ans = ans/N
print ans
### BUGGY CODE ###

import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

ml = len(format(A[-1], 'b'))
bA = [list(map(int, format(val, '061b'))) for val in A]
bAT = list(zip(*bA))
#print(bAT)
bAT = [sum(val) for val in bAT[::-1]]
#nbA = np.asarray(bA).sum(axis=0)[::-1]

cnt = 0
for i, val in enu(bAT):
    cnt += (N-val)*val*(2**(i))
    cnt %= MOD

print(cnt)



### FIXED CODE ###

import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
A = np.array(input().split(), np.int)
#print(A)

cnt = 0
for i in range(61):
    B = (A>>i)&1
    z = np.count_nonzero(B)
    cnt += z*(N-z)*(2**(i))
    cnt %= MOD

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

import sys
import math
from collections import deque
input = sys.stdin.readline
N = int(input())
check = [i for i in range(1, N+1)]
t = [[0 for i in range(9)] for _ in range(9)]
ans = 0
for i in range(1, 10):
    for l in range(1, 10):
        for q in check:
            if int(str(q)[0]) == i and int(str(q)[-1]) == l:
                t[i-1][l-1] += 1
for i in range(1, N+1):
    if str(i)[-1] == "0":
        continue
    elif len(str(i)) == 1:
        ans += t[i-1][i-1]
    else:
        ans += t[int(str(i)[-1])-1][int(str(i)[0])-1]
print(ans)



### FIXED CODE ###

N = int(input())
t = [[0 for _ in range(9)] for l in range(9)]
ans = 0
for i in range(1, N+1):
    if len(str(i)) == 1:
        t[i-1][i-1] += 1
    elif str(i)[-1] != "0":
        t[int(str(i)[0])-1][int(str(i)[-1])-1] += 1
for i in range(1, N+1):
    a = str(i)[0]
    b = str(i)[-1]
    if b == "0":
        continue
    elif a == b:
        ans += t[(int(a)-1)][int(a)-1]
    else:
        ans += t[(int(b)-1)][int(a)-1]
print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
if min(l)== 0:
    print(0)
else:    
    s=1
    for x in l:
        s *= x
    
    if s>1000000000000000000:
        print(-1)
    else:
        print(s)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
if min(l)== 0:
    print(0)
else:    
    s=1
    for x in l:
        s *= x
        if s>10**18:
            s=-1
            break
    print(s)
### BUGGY CODE ###

N, K =map(int, input().split())
lst = []
for _ in range(N):
    lst.append(int(input()))
sor = sorted(lst)

mindiff = float('inf')
for i in range(N-K+1):
    selected = sor[i:i+K]
    diff = selected[-1] - selected[0]
    if diff <= mindiff:
        mindiff = diff
print(mindiff)

### FIXED CODE ###

N, K =map(int, input().split())
lst = []
for _ in range(N):
    lst.append(int(input()))
sor = sorted(lst)

mindiff = float('inf')
for i in range(N-K+1):
    diff = sor[i+K-1] - sor[i] 
    if diff <= mindiff:
        mindiff = diff
print(mindiff)
### BUGGY CODE ###

from operator import itemgetter
n,q=map(int,input().split())
c=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  l[i]=[i,l[i][0],l[i][1]]
l2=sorted(l,key=itemgetter(2))

L=[-1 for i in range(max(c))]

class Bit:
  def __init__(self,n):
    self.size=n
    self.tree=[0]*(n + 1)
    self.depth=n.bit_length()

  def sum(self,i):
    s=0
    while i>0:
      s+=self.tree[i]
      i-=i&-i
    return s

  def add(self,i,x):
    while i<=self.size:
      self.tree[i]+=x
      i+=i&-i
 
  def lower_bound(self,x):
    sum_=0
    pos=0
    for i in range(self.depth,-1,-1):
      k=pos+(1<<i)
      if k<=self.size and sum_+self.tree[k]<x:
        sum_+=self.tree[k]
        pos+=1<<i
    return pos+1,sum_

BIT=Bit(n+1)

ans=[]
ct=0
for i in range(q):
  while ct<=l2[i][2]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans.append([l2[i][0],BIT.sum(l2[i][2]+1)-BIT.sum(l2[i][1])])

ans.sort()
for i in range(q):
  print(ans[i][1])

### FIXED CODE ###

n,q=map(int,input().split())
c=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  l[i].append(i)
l2=sorted(l,key=lambda x:x[1])

L=[-1]*(5*10**5+1)

class Bit:
  def __init__(self,n):
    self.size=n
    self.tree=[0]*(n + 1)
    self.depth=n.bit_length()

  def sum(self,i):
    s=0
    while i>0:
      s+=self.tree[i]
      i-=i&-i
    return s

  def add(self,i,x):
    while i<=self.size:
      self.tree[i]+=x
      i+=i&-i

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l2[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l2[i][2]]=BIT.sum(l2[i][1]+1)-BIT.sum(l2[i][0])

for i in range(q):
  print(ans[i])
### BUGGY CODE ###

from heapq import heappop,heappush 
k=int(input())
inf=float("inf")
data=[[] for i in range(k)]
for i in range(1,k):
    if i%10==9:
        data[i]=[[i*10%k,0]]
    else:
        data[i]=[[i*10%k,0],[(i+1)%k,1]]

que=[[1,1]]
ans=[inf]*k
count=1
while que:
    c,u=heappop(que)
    ans[u]=c
    for v,d in data[u]:
        if ans[v]==inf:
            heappush(que,[d+c,v])
    if ans[0]!=inf:
        break
print(ans[0])

### FIXED CODE ###

from heapq import heappop,heappush 
from collections import deque
k=int(input())
inf=float("inf")
data=[[] for i in range(k)]
for i in range(1,k):
    if i%10==9:
        data[i]=[[i*10%k,0]]
    else:
        data[i]=[[i*10%k,0],[(i+1)%k,1]]

que=deque([[1,1]])
ans=[inf]*k
while que:
    c,u=que.popleft()
    ans[u]=c
    for v,d in data[u]:
        if ans[v]==inf:
            if d==0:
                que.appendleft([c,v])
            else:
                que.append([c+1,v])
    if ans[0]!=inf:
        break
print(ans[0])
### BUGGY CODE ###

p = 1000000007
s = input()
n = len(s)
e,a,b,c = 1,0,0,0
for i in range(n):
  if s[i] == "A":
    a+=e
  elif s[i] == "B":
    b+=a
  elif s[i] == "C":
    c+=b
  else:
    e,a,b,c = 3*e,e+3*a,a+3*b,b+3*c
print(c%p) 


### FIXED CODE ###

e,a,b,c=1,0,0,0
p=1000000007
for i in input():
  if i == "A":
    a+=e
  elif i == "B":
    b+=a
  elif i == "C":
    c+=b
  else:
    e,a,b,c = (3*e)%p,(e+3*a)%p,(a+3*b)%p,(b+3*c)%p
print(c%1000000007)
### BUGGY CODE ###

s = input()
t = input()
LENs = len(s)
LENt = len(t)
dp = [[0 for i in range(LENt+1)] for j in range(LENs+1)]
for i in range(LENs+1):
    for j in range(LENt+1):
        if i+1 <= LENs:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if j+1 <= LENt:
            dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if i+1 <= LENs and j+1<=LENt:
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1

ans = ''
x = LENs
y = LENt
while True:
    if len(ans)==dp[-1][-1]:
        break
    if dp[x-1][y] == dp[x][y-1]:
        if dp[x-1][y-1] < dp[x][y]:
            ans += s[x-1]
            x = x-1
            y = y-1
            continue
        else:
            x = x-1
            continue
    elif dp[x-1][y] < dp[x][y-1]:
        y = y-1
    elif dp[x-1][y] < dp[x][y-1]:
        x = x-1

print(ans[::-1])

### FIXED CODE ###

s = input()
t = input()
LENs = len(s)
LENt = len(t)
dp = [[0 for i in range(LENt+1)] for j in range(LENs+1)]
for i in range(LENs+1):
    for j in range(LENt+1):
        if i+1 <= LENs:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if j+1 <= LENt:
            dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if i+1 <= LENs and j+1<=LENt:
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1

ans = ''
x = LENs
y = LENt
while True:
    if len(ans)==dp[-1][-1]:
        break
    if dp[x-1][y] ==dp[x][y]:
        x = x-1
    elif dp[x][y] == dp[x][y-1]:
        y = y-1
    elif dp[x-1][y-1]+1== dp[x][y]:
        ans =s[x-1] + ans
        x = x-1
        y = y-1
        continue
#     elif dp[x-1][y] == dp[x][y-1]:
#         x = x-1

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

import copy

def bfs(x, y):
    global tmp
    global cnt
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == "." and not (nx, ny) in tmp:
            tmp.append((nx, ny))
            maze[nx][ny] = "#"
            cnt += 1
    return tmp

h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
ans = 0
cnt = 0
tmp = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            tmp.append((i, j))
            cnt += 1

while cnt < h * w:
    tmp_ = copy.copy(tmp)
    tmp = []
    while tmp_:
        p = tmp_.pop()
        bfs(p[0], p[1])
    ans += 1
print(ans)

### FIXED CODE ###

import copy

def bfs(x, y):
    global tmp
    global cnt
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == ".":
            tmp.append((nx, ny))
            maze[nx][ny] = "#"
            cnt += 1
    return tmp

h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
ans = 0
cnt = 0
tmp = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            tmp.append((i, j))
            cnt += 1

while cnt < h * w:
    tmp_ = copy.copy(tmp)
    tmp = []
    while tmp_:
        p = tmp_.pop()
        bfs(p[0], p[1])
    ans += 1
print(ans)
### BUGGY CODE ###

import itertools

a,b,m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
P = [list(map(int,input().split())) for i in range(m)]
x = []
y = []
#普通に足算する
p = itertools.product(A, B)
for v in p:
    x.append(sum(v))
#min出す
xx = min(x)    
#割引券使う
for i in range(m):
  y.append(A[P[i][0]-1] + B[P[i][1]-1] - P[i][2])
#min出す
yy = min(y)
print(min(xx,yy))



### FIXED CODE ###

import itertools

a,b,m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
P = [list(map(int,input().split())) for i in range(m)]
y = []
#普通に足算する
aa = min(A)
bb = min(B)
xx =aa+bb

#割引券使う
for i in range(m):
  y.append(A[P[i][0]-1] + B[P[i][1]-1] - P[i][2])
#min出す
yy = min(y)

print(min(xx,yy))
### BUGGY CODE ###

N = int(input())
X = input()

dp = [-1] * 200001
dp[0] = 0
dp[1] = 1
dp[2] = 1
dp[3] = 2
dp[4] = 1
dp[5] = 2
dp[6] = 1
dp[7] = 2
dp[8] = 1
dp[9] = 2
dp[10] = 1


def popcount(n: int):
    bin_n = bin(n)
    return str(bin_n).count('1')


for i in range(N):
    count = 0
    if X[i] == '1':
        tmp = int(X)
        tmp -= 10 ** (N - i - 1)
    else:
        tmp = int(X)
        tmp += 10 ** (N - i - 1)
    tmp = int(str(tmp), 2)

    while True:
        if tmp == 0:
            print(count)
            break
        else:
            count += 1
            tmp = tmp % popcount(tmp)
            origin = tmp
            if dp[tmp] != -1:
                if tmp != origin:
                    dp[origin] = count + dp[tmp]
                print(count + dp[tmp])
                break
            else:
                count += 1
                tmp = tmp % popcount(tmp)


### FIXED CODE ###

N = int(input())
S = input()
X = int(S, 2)
pcx = S.count('1')
# ビット反転で1が0になる場合
pc1 = X % (pcx - 1) if pcx > 1 else 0
# ビット反転で0が1になる場合
pc2 = X % (pcx + 1)


def f(j):
    cnt = 0
    while j:
        j %= bin(j).count('1')
        cnt += 1
    return cnt


for i, y in enumerate(S):
    k = N - i - 1
    if y == "0":  # modを分配するときは、分配してからもう１回modを作用させれば良い
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
    dp[i] = min(dp[j] + abs(h[j] - h[i]) for j in range(max(i - k, 0), i))
print(dp[-1])

### FIXED CODE ###

def main():
    n, k = [int(e) for e in input().split()]
    h = [int(e) for e in input().split()]
    dp = [0] * n
    for i in range(1, n):
        dp[i] = min(dp[j] + abs(h[j] - h[i]) for j in range(max(i - k, 0), i))
    print(dp[n-1])
main()
### BUGGY CODE ###

import sys
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
setA = set()
water = [0]*n
cur = min(a[0],a[-1])
water[0]=2*min(a[0],a[-1])
dams=cur
i = n-1
while(1):
    if i==0:
        if dams+cur== a[0]:
            break
        else:
            water[0]-=cur
            dams=water[0]//2
            cur = dams
            i=n-1
    else:
        need = a[i]-cur
        water[i]= need*2
        cur=need
        i-=1
print(*water)

### FIXED CODE ###

import sys
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
switch =1
s = 0
ans = [0]*n
for v in a:
    s+= 2*v*switch
    switch*=-1
x=s//2
ans[-1]=x//2
for i in range(n-1,0,-1):
    need = (a[i]-ans[i])*2
    ans[i]=need
    ans[i-1]=need//2
ans[0]= x
print(*ans)
### BUGGY CODE ###

import heapq


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, 1, x])
  event_list.append([t-x, -1, x])

event_list.sort()
event_list.append([10**10, 1, 10**10])
i = 0
x_set = set()
x_list = []
for q in range(Q):
  d = int(input())
  while True:
    time, event, x = event_list[i]
    if time <= d:
      if event == 1:
        x_set.add(x)
        heapq.heappush(x_list, x)
      else:
        x_set.discard(x)
      i += 1
    else:
      break
  if x_set:
    while x_list and x_list[0] not in x_set:
      _ = heapq.heappop(x_list)
    print(x_list[0])
  else:
    print(-1)

### FIXED CODE ###

import sys
from heapq import heappop, heappush

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, 1, x])
  event_list.append([t-x, -1, x])

for i in range(Q):
  event_list.append([int(input()), 2, 0])

ans = []
event_list.sort()
x_set = set()
x_list = []
for time, event, x in event_list:
  if event == 1:
    x_set.add(x)
    heappush(x_list, x)
  elif event == -1:
    x_set.remove(x)
  else:
    while x_list and x_list[0] not in x_set:
      heappop(x_list)
    if x_list:
      ans.append(x_list[0])
    else:
      ans.append(-1)

print(*ans, sep='\n')
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def add(x, a):
    while x <= N:
        bit[x] += a
        x += x & -x

def sum(x):
    ret = 0
    while x != 0:
        ret += bit[x]
        x -= x & -x
    return ret

N, Q = map(int, input().split())
bit = [0] * (N+1)
c = list(map(int, input().split()))
rl = [None] * Q
for i in range(Q):
    l, r = map(int, input().split())
    rl[i] = (r, l, i)
rl.sort()
ans = [None] * Q
last_idx = [-1] * (N+1)
j = 0
for r, l, i in rl:
    while j < r:
        if last_idx[c[j]] == -1:
            last_idx[c[j]] = j
        else:
            add(last_idx[c[j]]+1, -1)
            last_idx[c[j]] = j
        add(j+1, 1)
        j += 1
    ans[i] = sum(r) - sum(l-1)
print(*ans, sep='\n')
            

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    bit = [0] * (N+1)

    def add(x, a):
        while x <= N:
            bit[x] += a
            x += x & -x

    def sum(x):
        ret = 0
        while x != 0:
            ret += bit[x]
            x -= x & -x
        return ret

    c = list(map(int, input().split()))
    lr = [None] * Q
    for i in range(Q):
        l, r = map(int, input().split())
        lr[i] = (i, l, r)
    lr.sort(key=lambda x: x[2])
    ans = [None] * Q
    last_idx = [-1] * (N+1)
    j = 0
    for i, l, r in lr:
        while j < r:
            if last_idx[c[j]] == -1:
                last_idx[c[j]] = j
            else:
                add(last_idx[c[j]]+1, -1)
                last_idx[c[j]] = j
            add(j+1, 1)
            j += 1
        ans[i] = sum(r) - sum(l-1)
    for a in ans:
        print(a)
            
if __name__ == "__main__":
    main()