Problem Description

Vrsar is a coastal town composed of $n$ small hills. Remarkably, from the coastline, these $n$ hills are arranged in a line, with the distance from the $i$-th hill to the coast being $x_i$ meters. At the top of each hill, there is a skating rink. All skating rinks open simultaneously each day, but they close at different times. The $i$-th skating rink is open for $t_i$ minutes.

Iva and Mia have arrived in Vrsar and will stay here for $m$ days. They love skating and hope to spend each day in Vrsar skating. At the beginning of the $i$-th day, they are $a_i$ meters away from the coast. As soon as the skating rinks open, they start their skating journey. They walk to the skating rinks at a speed of 1 meter per minute.

They are in excellent physical condition, so they do not need extra time to climb the hills. Once they reach the top of a hill, they can skate for any length of time until the rink closes. However, descending the hill is not as easy as climbing it, due to rain making the paths very slippery; they need to spend $s_i$ time to descend the $i$-th hill. After coming down from a hill, they can go to another hill.

Iva and Mia want to know how long they can skate each day. They can visit any number of skating rinks each day. Since they want to spend as much time as possible skating and as little time as possible calculating, they are asking for your help. Help them solve this problem.

Note: If Iva and Mia start in the morning at a position that is at the foot of a hill, they are already at the base of that hill.

Input Format

The first line contains two integers $n, m$ ($1 \le n, m \le 10^5$), representing the number of hills and the number of days, respectively.

The next $n$ lines, each containing three integers $x_i, t_i, s_i$ ($0 \le x_i, t_i, s_i \le 10^9$), represent the distance of the $i$-th hill from the coast, the closing time of the skating rink, and the time required to descend the hill, respectively.

The third line contains $m$ integers $a_i$ ($1 \le a_i \le 10^9$), representing the distance of Iva and Mia from the coast at the start of the $i$-th day.

Output Format

Output one line with $m$ integers, where the $i$-th integer represents the maximum time Iva and Mia can skate on the $i$-th day.

Sample Input and Output

Sample Input #1

3 1
3 7 0
6 11 3
10 13 5
1

Sample Output #1

6

Sample Input #2

3 2
5 10 3
3 6 1
1 5 0
0 3

Sample Output #2

5 8

Sample Input #3

1 3
3 3 3
0 1 2

Sample Output #3

0 1 2

Notes/Hints

Sample Explanation 1

Iva and Mia start at position 1, walk for 2 minutes to reach the hill at position 3, and skate for 5 minutes. Then they spend 0 minutes descending and continue for 3 minutes to reach the hill at position 6, where they skate for 1 minute.

They skate for a total of 6 minutes.

Subtasks

见题面 Input 部分

见题面 Output 部分