Перед вами есть числовая прямая, на которой выделено $$$n$$$ точек, пронумерованных слева направо от $$$1$$$ до $$$n$$$. Известно, что на эти точки могут выпадать осадки. А именно, в момент времени $$$t_j$$$(в начале секунды номер $$$t_j$$$) на точку с номером $$$x_j$$$ выпадает $$$c_j$$$ единиц дождя. Каждая точка характеризуется скоростью высыхания дождя на ней. Известно, что на точке номер $$$i$$$ осадки высыхают со скоростью $$$v_i$$$ единиц в секунду. Если в точке меньше $$$v_i$$$ единиц, то после высыхания на ней останется $$$0$$$ единиц дождя. Считайте, что осадки выпадают мгновенно в начале указанной секунды на указанное место, а высыхание происходит в конце каждой секунды в каждой точке. Вам дано $$$m$$$ запросов. В запросе $$$j$$$ на точку $$$x_j$$$ в момент времени $$$t_j$$$ выпадает $$$c_j$$$ осадков. Обозначим $$$f_{ij}$$$ – количество осадков в момент времени $$$j$$$ на участке номер $$$i$$$. Для каждого участка $$$i$$$ посчитайте $$$\sum_{j = 1}^{10^{100}} f_{ij}$$$. Выведите $$$n$$$ полученных чисел. Для более ясного понимания, вам нужно посчитать суммарное количество осадков в каждой точке по всем возможным моментам времени(к моменту времени $$$10^{100}$$$ все осадки точно высохнут). Считайте, что измерение количества осадков проводится сразу непосредственно после выпадения осадков, до того как осадки начали высыхать в эту секунду. Например, если в какую-то точку выпало $$$10$$$ единиц осадков, а скорость высыхания в этой точке равна $$$3$$$, и в этой точке потом больше не было осадков, то вам нужно прибавить $$$10 + 7 + 4 + 1 = 22$$$.
В первой строке вам задано число $$$1 \le n \le 10^5$$$ – количество точек и число $$$1 \le m \le 10^5$$$ – количество запросов. В следующей строке вам даны скорости высыхания дождя $$$1 \le v_i \le 10^9$$$. В следующих $$$m$$$ строках вам заданы по три числа $$$1 \le t_j \le 10^9, 1 \le x_j \le n, 1 \le c_j \le 10^4$$$. Обратите внимание, что запросы могут быть не отсортированы по времени, и в один и тот же момент времени возможно выпадение осадков для разных запросов, в том числе и на одну точку.
Выведите $$$n$$$ чисел – ответ на задачу.
5 10 2 1 2 1 3 1 1 10 2 2 10 3 3 10 4 4 10 5 5 10 6 5 10 7 5 10 8 5 10 9 5 10 10 5 10
30 55 30 55 480
