브르사르

브르사르는 $n$ 개의 언덕으로 이루어진 작은 해안 마을입니다. 바다에서 보면 언덕들이 앞뒤로 일렬로 늘어서 있고, $i$ 번째 언덕은 바다에서 $x_i$ 미터 떨어져 있습니다. 각 언덕 꼭대기에는 아이스링크가 있습니다. 모든 링크는 매일 같은 시각에 열리지만, $i$ 번째 링크는 $t_i$ 분 뒤에 닫힙니다.

이바와 미아는 $m$ 일 동안 브르사르에 머물며 매일 스케이트를 타려고 합니다. $i$ 번째 날의 시작 시점에 두 사람은 바다에서 $a_i$ 미터 떨어져 있으며, 링크가 열리는 순간 모험이 시작됩니다. 두 사람은 어느 방향으로든 분당 1미터의 속도로 걸을 수 있습니다. 언덕에 도착하면 언덕을 올라 꼭대기의 링크에 갈 수 있고, 오르지 않고 언덕을 지나쳐 갈 수도 있습니다. 오르는 데는 추가 시간이 들지 않습니다. 꼭대기에 도착하면 링크가 닫힐 때까지 원하는 만큼 스케이트를 탈 수 있습니다.

내려오는 데는 시간이 많이 걸립니다. 비가 온 뒤라 땅이 미끄러워서, $i$ 번째 언덕을 내려오는 데 $s_i$ 분이 걸립니다. 내려온 뒤에는 다음 링크를 향해 계속 걷습니다.

하루를 시작할 때 두 사람의 위치가 언덕과 같다면, 두 사람은 언덕 아래에 있는 것이므로 그 꼭대기 링크에서 스케이트를 타려면 언덕을 올라야 합니다.

그림은 첫 번째 예시를 보여 줍니다.

첫 줄에 언덕의 수 $n$과 날짜의 수 $m$이 주어집니다 ($1 \le n, m \le 10^5$).

이어지는 $n$개의 줄에는 정수 $x_i$, $t_i$, $s_i$가 주어집니다 ($0 \le x_i, t_i, s_i \le 10^9$). 각각 언덕이 바다에서 떨어진 거리, 그 언덕 링크의 폐장 시각, 그 언덕을 내려오는 데 걸리는 시간입니다.

마지막 줄에는 정수 $m$개 $a_i$ ($0 \le a_i \le 10^9$)가 주어집니다. 각 날의 시작 시점에 바다에서 떨어져 있는 거리입니다.

한 줄에 정수 $m$개를 출력합니다. $i$ 번째 정수는 $i$ 번째 날에 이바와 미아가 스케이트를 탈 수 있는 최대 시간(분)입니다.

그림은 첫 번째 예시를 설명합니다. 두 사람은 첫 번째 링크까지 걸어가 스케이트를 타고, 언덕을 내려온 뒤 다음 링크까지 걸어갑니다.