Песчаная буря
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Новый архитектор Арракиса проектирует новый городоской квартал Арракина, состоящий из $$$n$$$ расположенных в ряд зданий. Здание номер $$$i$$$ имеет ровно $$$h_i$$$ этажей.

Теперь архитектору интересно, смогут ли горожане по достоинству оценить его проект. Проблема в том, что в городе часто случаются песчаные бури, а стены города защищают от них только нижние этажи, поэтому верхние этажи некоторых зданий может быть не видно с земли.

Формально, вам поступают запросы вида $$$(l, r, f)$$$ — «уровень песчаной бури вокруг зданий с $$$l$$$-го по $$$r$$$-й включительно становится равен $$$f$$$». Это означает, что у всех зданий с $$$l$$$-го по $$$r$$$-й становится видно только первые $$$f$$$ этажей, тогда как все этажи выше спрятаны за песком и не видны. После каждого такого запроса вы должны сообщить архитектору, сколько всего этажей всех его зданий видно с земли.

Еще раз отметим, что песчаная буря непрерывна вверх, то есть если этаж номер $$$x$$$ здания номер $$$y$$$ спрятан за песком, то этажи $$$x + 1, x + 2, \ldots, h_y$$$ также спрятаны, и видны только этажи с первого по $$$(x - 1)$$$-й.

Изначально, перед поступлением первого запроса, песчаная буря еще не началась, то есть все здания видны целиком.

Входные данные

В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$q$$$ — количество зданий и количество запросов на изменение уровня песчаной бури ($$$1 \le n, q \le 10^5$$$).

Во второй строке ввода через пробел перечислены $$$n$$$ целых чисел $$$h_i$$$ — высоты зданий ($$$1 \le h_i \le 10^9$$$).

В следующих $$$q$$$ строках даны описания запросов. В $$$i$$$-й из них через пробел даны числа $$$l_i$$$, $$$r_i$$$ и $$$f_i$$$ — границы отрезка, на котором меняется уровень песчаной бури, и сам новый уровень ($$$1 \le l_i \le r_i \le n$$$; $$$0 \le f_i \le 10^9$$$).

Выходные данные

Выведите $$$q$$$ строк, каждая из которых содержит единственное целое число — ответ на соответствующий запрос.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллыДоп. ограничения Необходимые подзадачи Информация о проверке
0примеры из условияполная
110все $$$h_i$$$ равны, запросы не пересекаютсяполная
213$$$h_{i + 1} \ge h_i$$$, запросы не пересекаются1первая ошибка
315$$$n, q \le 200$$$0первая ошибка
417$$$r_i - l_i \le 10$$$ для всех $$$i$$$0первая ошибка
520$$$n, q \le 2000$$$0, 3первая ошибка
625нет0 – 5первая ошибка

Примеры

Входные данные
1 3
100
1 1 50
1 1 120
1 1 0
Выходные данные
50
100
0
Входные данные
4 5
1 5 7 3
1 3 1
2 4 2
2 3 5
1 4 3
3 4 100
Выходные данные
6
7
13
10
14