31270번 - Vrsar 서브태스크다국어

문제

Vrsar is a small coastal town consisting of $n$ hills. Surprisingly, all the hills, when viewed from the sea, are arranged one behind the other so that the $i$-th hill is $x_i$ meters away from the sea. At the top of each hill, there is an ice rink. All ice rinks open simultaneously every day, but they do not close at the same time: the $i$-th ice rink is open for $t_i$ minutes.

Iva and Mia have come to Vrsar and will be here for $m$ days. Iva and Mia love ice skating and want to skate every day they spend in this town. At the beginning of the $i$-th day, they are $a_i$ meters away from the sea, and their ice-skating adventure starts at the same time as the ice rinks open. To reach an ice rink, they must walk to it, moving at a speed of one meter per minute. They can walk both to the left and to the right. If they are at a position where there is a hill, they can climb the hill and reach the ice rink on top of it, or they can bypass it without climbing.

They are in very good shape, so they can climb the hill without spending extra time. Once they reach the top, they can skate as much as they want or until the ice rink closes. Going downhill is not as easy as going up. Recently, it rained, and the ground is slippery, so it takes si minutes for them to descend the $i$-th hill. After descending from a hill, they can continue walking towards the next ice rink.

The illustration shows the first example.

Iva and Mia are at the starting point at position 1ドル$. They walk for 2ドル$ minutes to the ice rink on the hill at position 3ドル$ and ice skate there for 5ドル$ minutes. Then they descend from the hill (in 0ドル$ minutes), continue walking for 3ドル$ minutes to the ice rink on the hill at position 6ドル,ドル and ice skate there for 1ドル$ minute. In total, they have ice skated for 5ドル + 1 = 6$ minutes.

Iva and Mia are interested in determining the maximum number of minutes they can ice skate each day. In one day, they can visit any number of ice rinks. Since they want to spend more time skating and less time calculating, they have turned to you for help. Help them solve this problem!

Note: If Iva and Mia at the beginning of the day are at the same position as a hill, they are at the bottom of the hill, and so they have to climb it if they want to ice skate on the ice rink on top of it.

입력

The first line contains integers $n$ and $m$ (1ドル ≤ n, m ≤ 10^5$), the number of hills and the number of days.

The i-th of the following $n$ lines contains integers $x_i,ドル $t_i$ and $s_i$ (0ドル ≤ x_i , t_i , s_i ≤ 10^9$), the distance of the $i$-th hill from the shore, closing time of the ice rink and the time required for the descent from the hill.

The third line contains $m$ integers $a_i$ (0ドル ≤ a_i ≤ 10^9$), Iva’s and Mia’s starting distance from the shore at the beginning of the $i$-th day.

출력

In one line, print $m$ integers, the $i$-th of which is the maximum time Iva and Mia can ice skate on $i$-th day.

제한

서브태스크

힌트

Clarification of the first example: Take a look at the illustration in the statement.