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@@RISE_MATH_BLOCK_0@@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@@RISE_MATH_BLOCK_1@@i\) 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.

Subtask 1 (8 points): n, \(m \le 10\)

Subtask 2 (17 points): \(m = 1\), a\(1 = 0\)

Subtask 3 (19 points): n, \(m \le 1\,000\)

Subtask 4 (26 points): No additional constraints.

The first line contains integers \(n\) and \(m\) (\(1 \le n\), \(m \le 10^{5}\)), the number of hills and the number of days.
The \(i-th\) of the following \(n\) lines contains integers \(x@@RISE_MATH_BLOCK_0@@i\) and \(s@@RISE_MATH_BLOCK_1@@i\), t\(i\), s\(i \le 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@@RISE_MATH_BLOCK_2@@i \le 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.

생성자가 기록되지 않았습니다.

출처 COCI 2023/2024 Contest 3