시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 33 | 24 | 22 | 70.968% |
Географ Григорий Георгиевич исследует образование песчаных дюн. Он выбрал очень длинную дюну и разбил его на огромное число участков, которые пронумеровал от 1 до $10^9$.
Теория Григория Георгиевича гласит, что изначально высота песка относительно некоторой условной отметки на всех участках была равна нулю. После этого произошло $n$ сильных порывов ветра, которые могли изменить ландшафт.
Порыв ветра номер $i$ имел силу $x_i$ и действовал на участки с $l_i$-го по $r_i$-й. В результате этого порыва высота участка номер $l_i$ увеличилась на $x_i$, высота участка номер $l_i+1$ уменьшилась на $x_i$, следующего --- снова увеличилась, и так далее до участка номер $r_i$, включительно.
Зная всю информацию о всех $n$ порывах ветра, Григорий Георгиевич хочет узнать установившуюся в итоге высоту некоторых интересующих его $m$ участков. Помогите ему.
В первой строке входного файла содержатся два натуральных числа $n$ и $m$ ($1 \le n, m \le 1000$) --- количество порывов ветра и количество участков, итоговая высота которых интересует Григория Георгиевича.
В каждой из следующих $n$ строк содержится описание очередного порыва ветра --- три целых числа $l_i, r_i, x_i$ ($1 \le l_i \le r_i \le 10^9$; $1 \le x_i \le 1000$).
В каждой из следующих $m$ строк содержится целое число $q_i$ ($1 \le q_i \le 10^9$) --- номер участка, для которого требуется узнать его итоговую высоту. Номера участков приведены в возрастающем порядке.
Для каждого из $m$ запросов выведите одно целое число --- высоту соответствующего участка.
2 6 1 6 7 3 7 2 1 2 3 6 7 8
7 -7 9 -9 2 0