E. Карамельные облака
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как известно, лучшее украшение клумбы в королевстве Sweetland — ванильные кексики. Процесс их выращивания весьма сложен и требует немалых ресурсов. У Сластены есть m саженцев, и для превращения j-го саженца кексика в произведение искусства необходимо держать его под солнцем не менее kj минут.

Большую часть времени в Sweetland стоит прекрасная погода, которая лишь иногда омрачается появлением карамельных облаков, i-е из которых возникает в момент времени (минуту) li и исчезает в момент времени ri. Разумеется, солнечный свет не способен пробиться сквозь карамельный покров.

Сластена не отличается терпением, и ей хочется вырастить свое пирожное как можно быстрее. В ее распоряжении ровно C конфет — основной валюты Sweetland.

Любое облако можно полностью рассеять, заплатив за это ci конфет. Однако в соответствии с указом министерства метеорологии Sweetland, рассеивание более чем двух карамельных облаков искусственным путем строжайше запрещено и карается огромным штрафом.

В коллекции Сластены находится m саженцев. Она еще не определилась, какие из них достойны занять почетное место в королевском саду, и ей требуется ваша помощь. Для каждого саженца определите самую раннюю минуту, к которому его можно вырастить, не нарушая указ министерства метеорологии и не выходя за рамки бюджета. Обратите внимание, что Сластена находится на этапе формирования набора кексиков, поэтому каждый новый саженец рассматривается независимо от остальных.

Выращиваться кексики начинают в момент времени 0.

Входные данные

В первой строке следуют два числа n и C (0 ≤ n ≤ 3·105, 0 ≤ C ≤ 109) — число карамельных облаков и количество конфет, которыми обладает Сластена.

В следующих n строках тремя числами li, ri, ci (0 ≤ li < ri ≤ 109, 0 ≤ ci ≤ 109) задается очередное карамельное облако.

Далее следует m (1 ≤ m ≤ 3·105) — число саженцев. Каждый саженец описывается одним параметром kj (1 ≤ kj ≤ 109) — необходимым числом солнечных минут.

Выходные данные

Для каждого саженца выведите одно число — минимально возможную минуту, к которой Сластена сумеет вырастить данный ванильный кексик.

Примеры
Входные данные
3 5
1 7 1
1 6 2
1 7 1
3
7
2
5
Выходные данные
12
7
10
Входные данные
3 15
1 4 17
2 8 6
4 8 9
2
5
1
Выходные данные
8
1
Входные данные
2 10
3 7 9
10 90 10
2
10
100
Выходные данные
10
104
Примечание

Рассмотрим первый пример чуть подробнее. Здесь для любого k оптимально развеять облака 1 и 3. Тогда солнце не будет светить в промежутке [1..6]. Соответственно, солнечными будут являться промежутки [0..1] и [6..inf).

Во втором примере при k = 1 ничего развеивать не требуется, а при k = 5 наилучшей стратегией будет развеять облака 2 и 3. Это добавит дополнительный солнечный промежуток [4..8], который вместе с [0..1] позволяет вырастить кексик по достижении восьмой минуты.

В третьем примере два саженца кардинально различаются. Для минимизации времени выращивания первого необходимо разогнать облако 1 и получить достаточный промежуток времени [0..10], в то время как аналогичный подход даст для второго ответ 180. Однако если убрать облако 2, солнечными будут отрезки [0..3] и [7..inf), что позволит нам сократить время до 104.