Улицу Подводный канал освещают \(n\) фонарей, пронумерованных вдоль улицы от 1 до \(n\). Один или несколько подряд стоящих фонарей назовём сегментом. Таким образом, общее количество сегментов \(\frac{n(n+1)}{2}\). Сегмент считается исправным, если лампочки во всех фонарях этого сегмента исправны.
С фонарями регулярно происходят события одного из двух типов:
в каком-то сегменте из-за скачков напряжения все лампочки одновременно перегорают;
Архиэнерго выбирает некоторый сегмент и посылает ремонтников, чтобы заменить на нем все перегоревшие лампочки на исправные.
После каждого события мэрия города требует от Архиэнерго предоставить отчёт о количестве исправных сегментов. Для улучшения показателей работы ремонтники включают в отчёт все сегменты, которые исправны сейчас или были исправны когда-либо ранее.
Требуется написать программу, определяющую количество сегментов после каждого события, которые исправны в этот момент или были исправны когда-либо до этого события.
Входные данные
В первой строке входных данных содержатся два числа \(n\) и \(q\) — количество фонарей и количество произошедших событий. Следующая строка входных данных состоит из \(n\) символов 0 и 1, описывающих начальное состояние фонарей, где 1 обозначает фонарь с исправной лампочкой, а 0 — с перегоревшей.
В каждой из последующих \(q\) строк содержатся описания событий в виде трёх чисел \(l_i, r_i\) и \(c_i\), которые означают, что после этого события все лампочки в фонарях с номерами \(l_i, l_i+1, \ldots, r_i\):
- перегорают при \(c_i = 0\),
- становятся исправными при \(c_i = 1\).
В описаниях всех событий \(1 \le l_i \le r_i \le n\), а \(c_i\) принимает значение \(0\) или \(1\).
Выходные данные
В первой строке выходных данных выведите единственное число "— количество исправных сегментов в начальном состоянии. Затем по одному в строке выведите \(q\) чисел: для каждого из произошедших событий выведите количество сегментов, указываемых в отчёте после этого события.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 4
1100101
4 6 1
3 6 0
3 4 1
5 7 1
|
5
13
13
19
28
|