Рудольф является выдающимся специалистом по структурам данных, поэтому его пригласили прочесть лекцию для студентов университета. Чтобы сделать материал лекции более доступным для слушателей, Рудольф решил заранее приготовить и расположить на сцене множество наглядных пособий. Теперь ему осталось только проверить, что сцена достаточно хорошо освещена.
Сцена имеет ширину W и может быть представлена отрезком [0; W]. Над сценой закреплены N прожекторов.
Каждый прожектор характеризуется координатой X, мощностью A и рассеянием B. При включении прожектора освещённость сцены изменяется следующим образом:
Помогите Рудольфу определить, насколько хорошо будут освещены определённые точки сцены после включения всех прожекторов.
Первая строка содержит целое число W (1 ≤ W ≤ 106) — ширину сцены.
Вторая строка содержит целое число N (1 ≤ N ≤ 5·105) — количество прожекторов.
Следующие N строк описывают прожекторы. Каждая из них содержит целые числа Xi, Ai и Bi (0 ≤ Xi ≤ W, 1 ≤ Ai ≤ 106, 1 ≤ Bi ≤ Ai) — соответственно координату, мощность и рассеяние i-го прожектора.
Следующая строка содержит целое число M (1 ≤ M ≤ 5·105) — количество точек, для которых необходимо определить освещённость.
Следующая строка содержит M целых чисел Xj (0 ≤ Xj ≤ W) — координаты точек, для которых необходимо определить освещённость.
Выведите M целых чисел — освещённость каждой из искомых точек.
10
1
6 4 1
11
0 1 2 3 4 5 6 7 8 9 10
0 0 0 1 2 3 4 3 2 1 0
10
2
3 10 1
7 5 2
10
0 1 2 3 9 8 7 6 3 4
7 8 9 10 5 8 11 10 10 9
