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