D. Дюны

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

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