CF833E.Caramel Clouds

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 k__j 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) l__i and disappear at time moment r__i. 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 c__i 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.

众所周知，甜乡（Sweetland）花坛的最佳装饰品是香草松饼。这种植物的幼苗需要阳光才能生长。斯拉丝通娜（Slastyona）有 $m$ 株幼苗，其中第 $j$ 株幼苗至少需要 $k_j$ 分钟的日照时间才能长成。

甜乡大部分时间都是晴天，但偶尔会有焦糖云出现：第 $i$ 朵云将在时刻（分钟）$l_i$ 出现，并在时刻 $r_i$ 消失。显然，这些云会投下阴影；只要有一朵云遮蔽了太阳，幼苗就无法生长。

斯拉丝通娜希望尽可能快地让她的松饼长成。她恰好拥有 $C$ 颗糖果——这是甜乡的主要货币。

驱散任意一朵云需花费 $c_i$ 颗糖果。然而，为遵守甜乡气象局的规定，最多只能驱散两朵云。

斯拉丝通娜尚未决定将 $m$ 株幼苗中的哪些种在公主的花园里，因此她需要你的帮助：对每一株幼苗，求出它最早能在何时长成——前提是斯拉丝通娜不违反上述规定，且花费的糖果总数不超过 $C$。注意：每株幼苗的计算相互独立。

所有幼苗均从时刻 $0$ 开始生长。

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: l__i, r__i, c__i (0 ≤ l__i < r__i ≤ 109, 0 ≤ c__i ≤ 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 k__j (1 ≤ k__j ≤ 109) – the required number of sunny minutes.

第一行包含两个整数 $n$ 和 $C$（$0 \le n \le 3\cdot10^5$，$0 \le C \le 10^9$）——分别表示焦糖云的数量以及 Slastyona 拥有的糖果数量。

接下来的 $n$ 行每行包含三个整数：$l_i$、$r_i$、$c_i$（$0 \le l_i < r_i \le 10^9$，$0 \le c_i \le 10^9$），描述一朵焦糖云。

下一行包含一个整数 $m$（$1 \le m \le 3\cdot10^5$）——表示幼苗的数量。每株幼苗由一个整数 $k_j$（$1 \le k_j \le 10^9$）描述——即该幼苗所需的晴朗分钟数。

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

对于每株幼苗，输出一个整数——Slastyona 将其培育成熟的最短分钟数。

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.

考虑第一个例子。对于每个 $k$，最优策略都是驱散第 1 和第 3 号云。此时剩余的云会在时间区间 $[1..6]$ 内投下阴影。因此，区间 $[0..1]$ 和 $[6..\infty)$ 是晴朗的。

在第二个例子中，当 $k = 1$ 时，无需驱散任何云；而当 $k = 5$ 时，最优策略是驱散第 2 和第 3 号云。这额外增加了晴朗区间 $[4..8]$，结合原有的 $[0..1]$，使得松饼可在第 8 分钟成熟。

在第三个例子中，两株幼苗的情况截然不同。对于第一株幼苗，必须驱散第 1 号云，从而获得晴朗区间 $[0..10]$。然而，对第二株幼苗采用相同策略得到的答案为 180。相反，若驱散第 2 号云，则可使区间 $[0..3]$ 和 $[7..\infty)$ 变为晴朗，从而将所需时间缩短至 104。