D. Дюны

Имя входного файла: dunes.in
Имя выходного файла: dunes.out
Ограничение по времени: 2 s
Ограничение по памяти: 256 megabytes

Географ Григорий Георгиевич исследует образование песчаных дюн. Он выбрал очень длинную дюну и разбил его на огромное число участков, которые пронумеровал от 1 до 109.

Теория Григория Георгиевича гласит, что изначально высота песка относительно некоторой условной отметки на всех участках была равна нулю. После этого произошло n сильных порывов ветра, которые могли изменить ландшафт.

Порыв ветра номер i имел силу xi и действовал на участки с li-го по ri-й. В результате этого порыва высота участка номер li увеличилась на xi, высота участка номер li+1 уменьшилась на xi, следующего – снова увеличилась на xi, и так далее до участка номер ri, включительно.

Зная всю информацию о всех n порывах ветра, Григорий Георгиевич хочет узнать установившуюся в итоге высоту некоторых интересующих его m участков. Помогите ему.

Формат входного файла

В первой строке входного файла содержатся два натуральных числа n и m (1 ≤ n, m ≤ 1000) – количество порывов ветра и количество участков, итоговая высота которых интересует Григория Георгиевича.

В каждой из следующих n строк содержится описание очередного порыва ветра – три целых числа li, ri, xi (1 ≤ li ≤ ri ≤ 109; 1 ≤ xi ≤ 1000).

В каждой из следующих m строк содержится целое число qi (1 ≤ qi ≤ 109) – номер участка, для которого требуется узнать его итоговую высоту. Номера участков приведены в возрастающем порядке.

Формат выходного файла

Для каждого из m запросов выведите одно целое число – высоту соответствующего участка.

Пример:

dunes.indunes.out
2 6 1 6 7 3 7 2 1 2 3 6 7 8 7 -7 9 -9 2 0


Источник: Командное школьное первенство Республики Карелия. Ноябрь 2014.

Обсудить       Отправить решение



Версия для печати