D. Дюны

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

Пример:

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

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



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