Caramel Clouds
Contest: Codeforces Round 426 (Div. 1)
Difficulty rating: 3400
Tags: data structures, dp, sortings

It is well-known that the best decoration for a flower bed in Sweetland are vanilla muffins. Seedlings of this plant need sun to grow up. Slastyona has m seedlings, and the j-th seedling needs at least kj minutes of sunlight to grow up.

Most of the time it's sunny in Sweetland, but sometimes some caramel clouds come, the i-th of which will appear at time moment (minute) li and disappear at time moment ri. Of course, the clouds make shadows, and the seedlings can't grow when there is at least one cloud veiling the sun.

Slastyona wants to grow up her muffins as fast as possible. She has exactly C candies, which is the main currency in Sweetland.

One can dispel any cloud by paying ci candies. However, in order to comply with Sweetland's Department of Meteorology regulations, one can't dispel more than two clouds.

Slastyona hasn't decided yet which of the m seedlings will be planted at the princess' garden, so she needs your help. For each seedling determine the earliest moment it can grow up if Slastyona won't break the law and won't spend more candies than she has. Note that each of the seedlings is considered independently.

The seedlings start to grow at time moment 0.

Input format:
The first line contains two integers n and C (0 ≤ n ≤ 3·105, 0 ≤ C ≤ 109) – the number of caramel clouds and the number of candies Slastyona has.

The next n lines contain three integers each: li, ri, ci (0 ≤ li < ri ≤ 109, 0 ≤ ci ≤ 109), describing one caramel cloud.

The next line contains single integer m (1 ≤ m ≤ 3·105) – the number of seedlings. Each of the seedlings is described with one integer kj (1 ≤ kj ≤ 109) – the required number of sunny minutes.

Output format:
For each seedling print one integer – the minimum minute Slastyona can grow it up.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
Consider the first example. For each k it is optimal to dispel clouds 1 and 3. Then the remaining cloud will give shadow on time segment [1..6]. So, intervals [0..1] and [6..inf) are sunny.

In the second example for k = 1 it is not necessary to dispel anything, and for k = 5 the best strategy is to dispel clouds 2 and 3. This adds an additional sunny segment [4..8], which together with [0..1] allows to grow up the muffin at the eight minute.

If the third example the two seedlings are completely different. For the first one it is necessary to dispel cloud 1 and obtain a sunny segment [0..10]. However, the same strategy gives answer 180 for the second seedling. Instead, we can dispel cloud 2, to make segments [0..3] and [7..inf) sunny, and this allows up to shorten the time to 104.

Example input:
3 5
1 7 1
1 6 2
1 7 1
3
7
2
5

Example output:
12
7
10

Example input:
3 15
1 4 17
2 8 6
4 8 9
2
5
1

Example output:
8
1

Editorial:
Prequisites: scanline.
The key idea is that only minutes which are covered by no more than two clouds can contribute to the answer.
Let us demonstrate how to solve the problem for a fixed k using scanline. Let's create 2·n events: for the start and the end of each cloud. We will then go through all the events in ascending order of their coordinates, maintaining the following values:
• the set of active clouds open;
• the count of sunny (from the beginning!) minutes free;
• the array single(i), which denotes the number of minutes covered solely by cloud i;
• the variable top – the largest number of sunny minutes we can obtain on a given prefix by deleting no more than two clouds;
• the sparse table cross, whose element (a, b) holds the number of minutes of sunny minutes covered solely by a and b;
• and finally, the array opt(i) – the optimal number of sunny minutes we can obtain if we dispel i-th cloud as one of the selected ones.
We will also construct a treap (or BIT/segment tree if we want to), where each leaf has the index in form of the pair cost(i), i, keeping best index relative to single(i) in the subtree in each node.
So, let us assume we are now considering some event with the coordinate x, which is going to add some segment with length len.
• If open is empty, it's enough to just increase free by len.
• If open contains exactly two elements (let's denote them as a and b), we need to increase cross[a, b] by len and try to update opt(a) via using b and opt(b) via using a if it's possible (i.e. if the sum of costs does not exceed the budget).
• The case when open only one element is the most interesting. We have to try to increase both single(a) and opt(a) by len consequently. What clouds may optima have also updated for? Obviously, for every cloud which cost allows us to dispel it together the cloud a. But it's only necessary to update opt only for cloud with maximal single(x) (don't forget to delete a from the tree) on range [0..C - cost(a)]. Why? We leave this as an excercise for the reader.
After that, we will either need to remove the start of the cloud from open if we are dealing with a closing event, or to put it into open otherwise.
Along with aforementioned operations we can also update the variable top. It's not that hard to observe that if free + top ≥ k, the answer would be some point of the last segment: we can find it as x - (free + top) - k.
It's also worth noting that if we are to order all the queries in the non-descending order, the answers would be ordered the same way. We can then process them in one go.
Time complexity: $${ \mathcal { O } } ( n \log(n) + m \log(m) )$$.