Рус Uzb Eng

C21B. Дюны
Ограничение по времени: 2 cекунды
Ограничение по памяти: 64 мегабайт

Географ Григорий Георгиевич исследует образование песчаных дюн. Он выбрал очень длинную дюну и разбил его на огромное число участков, которые пронумеровал от 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 запросов выведите одно целое число — высоту соответствующего участка.

Пример ввода Пример вывода
2 6 1 6 7 3 7 2
1
2
3
6
7
8
7
-7
9
-9
2
0
Область:
Источник задачи:

Отправить решение на проверку

Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.