众所周知,甜地花坛最好的装饰是香草松饼。这种植物的幼苗需要阳光才能生长。 Slastyona 有 m 个幼苗,第 j 个幼苗至少需要 kj 分钟的阳光才能长大。
Sweetland大部分时间都是晴天,但有时会出现一些焦糖云,其中第i个焦糖云会在时刻(分)li出现并在时刻ri消失。当然,云会产生阴影,当至少有一朵云遮住太阳时,幼苗就无法生长。
Slastyona 希望她的松饼尽快长大。她正好有C糖果,这是甜蜜之地的主要货币。
支付 ci 糖果即可驱散任何乌云。不过,为了遵守斯威特兰气象局的规定,一片云不能驱散超过两片云。
Slastyona 尚未决定将哪一棵树苗种植在公主的花园里,所以她需要你的帮助。对于每棵幼苗,如果斯拉斯蒂奥娜不违法并且不花费比她拥有的更多的糖果,则确定它最早可以长大的时刻。请注意,每个幼苗都是独立考虑的。
幼苗在时刻 0 开始生长。
输入
第一行包含两个整数 n 和 C (0 ≤ n ≤ 3·105, 0 ≤ C ≤ 109) – 焦糖云的数量和 Slastyona 拥有的糖果数量。
接下来的 n 行每行包含三个整数:li, ri, ci (0 ≤ li < ri ≤ 109, 0 ≤ ci ≤ 109),描述一个焦糖云。
下一行包含单个整数 m (1 ≤ m ≤ 3·105) – 幼苗的数量。每棵幼苗都用一个整数 kj (1 ≤ kj ≤ 109) 来描述——所需的晴天分钟数。
输出
为每一棵幼苗打印一个整数——Slastyona 可以让它长大的最短分钟。
示例
输入 #1
3 5 1 7 1 1 6 2 1 7 1 3 7 2 5
输出 #1
12 7 10
输入 #2
3 15 1 4 17 2 8 6 4 8 9 2 5 1
输出 #2
8 1
输入 #3
2 10 3 7 9 10 90 10 2 10 100
输出 #3
10 104
注意
考虑第一个例子。对于每个 k,最好消除云 1 和 3。然后剩余的云将在时间段 [1..6] 上产生阴影。因此,间隔 [0..1] 和 [6..inf) 都是晴天。
在第二个示例中,k = 1 时,无需驱散任何东西,而 k = 5 时,最佳策略是驱散云 2 和 3。这会添加一个额外的阳光片段 [4..8],与 [0..1] 一起允许松饼在第 8 分钟长大。
如果是第三个例子,则两株幼苗完全不同。对于第一个,需要驱散云 1 并获得晴朗的部分 [0..10]。然而,同样的策略对于第二棵树苗给出了答案 180。相反,我们可以驱散云 2,使段 [0..3] 和 [7..inf) 晴朗,这样最多可以将时间缩短到 104。