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

ОПГ «братухи 42» начало распространяться.

В России живет $$$n$$$ человек. Каждый из них пронумерован от $$$1$$$ до $$$n$$$, а также про каждого известно, он 42 братуха или нет.

Происходит $$$q$$$ актов распространения. Акт распространения заключается в следующем: $$$i$$$ человек-распространитель вербует в ОПГ «братухи 42» людей с номерами с $$$l$$$ по $$$r$$$. При этом, если $$$i$$$ человек не 42 братуха, то у него не хватает харизмы кого-либо завербовать.

Главарю ОПГ «братухи 42» стало интересно, сколько человек в результате актов распространения оказалось 42 братухой.

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

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

Во второй строке через пробел задается $$$n$$$ чисел, если $$$i$$$ из них равно $$$1$$$, то значит $$$i$$$ человек 42 братуха, иначе — нет.

В следующих $$$q$$$ строках в хронологическом порядке задается через пробел три числа $$$i$$$, $$$l$$$, $$$r$$$ $$$(1 \le i \le n, 1 \le l \le r \le n, i \notin [l, r])$$$.

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

В единственной строке выведите число — количество человек, которое в результате стали 42-братухами.

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

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

Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи
$$$0$$$ | $$$0$$$ | Тесты из условия | —
$$$1$$$ | $$$42$$$ | $$$n \cdot q \le 10^7$$$ | —
$$$2$$$ | $$$58$$$ | — | $$$0$$$, $$$1$$$

Пример

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

    7 20 0 0 1 0 0 14 1 31 7 7

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

    5