{"raw_statement":[{"iden":"statement","content":"Рудольф является выдающимся специалистом по структурам данных, поэтому его пригласили прочесть лекцию для студентов университета. Чтобы сделать материал лекции более доступным для слушателей, Рудольф решил заранее приготовить и расположить на сцене множество наглядных пособий. Теперь ему осталось только проверить, что сцена достаточно хорошо освещена.\n\nСцена имеет ширину W и может быть представлена отрезком [0; W]. Над сценой закреплены N прожекторов.\n\nКаждый прожектор характеризуется координатой X, мощностью A и рассеянием B. При включении прожектора освещённость сцены изменяется следующим образом: \n\nПомогите Рудольфу определить, насколько хорошо будут освещены определённые точки сцены после включения всех прожекторов.\n\nПервая строка содержит целое число W (1 ≤ W ≤ 106) — ширину сцены.\n\nВторая строка содержит целое число N (1 ≤ N ≤ 5·105) — количество прожекторов.\n\nСледующие N строк описывают прожекторы. Каждая из них содержит целые числа Xi, Ai и Bi (0 ≤ Xi ≤ W, 1 ≤ Ai ≤ 106, 1 ≤ Bi ≤ Ai) — соответственно координату, мощность и рассеяние i-го прожектора.\n\nСледующая строка содержит целое число M (1 ≤ M ≤ 5·105) — количество точек, для которых необходимо определить освещённость.\n\nСледующая строка содержит M целых чисел Xj (0 ≤ Xj ≤ W) — координаты точек, для которых необходимо определить освещённость.\n\nВыведите M целых чисел — освещённость каждой из искомых точек.\n\n"},{"iden":"входные данные","content":"Первая строка содержит целое число 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) — координаты точек, для которых необходимо определить освещённость."},{"iden":"выходные данные","content":"Выведите M целых чисел — освещённость каждой из искомых точек."},{"iden":"примеры","content":"Входные данные1016 4 1110 1 2 3 4 5 6 7 8 9 10Выходные данные0 0 0 1 2 3 4 3 2 1 0 Входные данные1023 10 17 5 2100 1 2 3 9 8 7 6 3 4Выходные данные7 8 9 10 5 8 11 10 10 9 "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ W \\in \\mathbb{Z}^+ $ be the width of the stage, represented as the interval $[0, W]$.  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of spotlights.  \nFor each spotlight $ i \\in \\{1, \\dots, N\\} $, define:  \n- $ x_i \\in [0, W] $: position,  \n- $ a_i \\in \\mathbb{Z}^+ $: power,  \n- $ b_i \\in \\mathbb{Z}^+ $: spread, with $ b_i \\leq a_i $.  \n\nLet $ M \\in \\mathbb{Z}^+ $ be the number of query points.  \nFor each query point $ j \\in \\{1, \\dots, M\\} $, let $ x_j \\in [0, W] $ be its coordinate.\n\n**Constraints**  \n1. $ 1 \\leq W \\leq 10^6 $  \n2. $ 1 \\leq N \\leq 5 \\cdot 10^5 $  \n3. $ 0 \\leq x_i \\leq W $, $ 1 \\leq a_i \\leq 10^6 $, $ 1 \\leq b_i \\leq a_i $ for all $ i $  \n4. $ 1 \\leq M \\leq 5 \\cdot 10^5 $  \n5. $ 0 \\leq x_j \\leq W $ for all $ j $\n\n**Objective**  \nFor each query point $ x_j $, compute the total illumination:  \n$$\nI(x_j) = \\sum_{\\substack{i=1 \\\\ |x_j - x_i| \\leq b_i}}^{N} \\left( a_i - |x_j - x_i| \\right)\n$$","simple_statement":"You are given a stage of width W, represented as the interval [0, W]. There are N spotlights, each at position Xi with power Ai and spread Bi. Each spotlight lights up the range [Xi - Bi, Xi + Bi], and the brightness at any point in that range is increased by Ai. You are given M query points, and for each, output the total brightness at that point after all spotlights are turned on.","has_page_source":false}