Будимо, на якій живе Леді, освітлюють ліхтарів, пронумерованих підлягає вулиці від до . Один або кілька ліхтарів, що стоять підряд, наявемо сегментом. Таким чином, загальна кількість сегментів дорівнює \frac{N(N+1)}{2}. Сегмент вважається робочим, якщо лампочки в усіх ліхтарях цього сегмента працюють.
З ліхтарями регулярно відбуваються події одного з двох типів:
в якомусь сегменті через стрибок напруги усі лампочки одночасно перегорають;
Леді вибирає деякий сегмент і викликає ремонтників, щоб вони замінили на ньому усі перегорілі лампочки.
Після кожної такої події мерія мість, в якому живе Леді, вимагає від неї надати звіт про кількість робочих сегментів. Для покращення показників роботи ремонтників Леді включає у звіт усі сегменти, які є робочими на момент подання звіту або були робочими коли-небудь до цієї події.
Напишіть програму, яка після кожної події визначить кількість сегментів у звіті Леді.
У першому рядку вхідного файлу знаходяться два натуральних числа і – кількість ліхтарів і кількість подій, що відбулись. Другий рядок вхідного файлу містить символів «0» і «1», які описують початковий стан ліхтарів, де «1» означає ліхтар з робочою лампочкою, а «0» – з перегорілою.
У кожному з наступних рядків міститься опис подій у вигляді трьох чисел L_i, R_i, C_i, які означають, що після цієї події усі лампочки в ліхтарях L_i, L_{i+1}, \dots, R_i
перегорають при C_i = 0,
замінюють на робочі при C_i = 1.
В описах усіх подій 1 \leqslant L_i \leqslant R_i \leqslant N, і C_i приймають значення або .
У першому рядку вихідного файлу виведіть єдине число – кількість діючих сегментів в початковому стані. Потім по одному в рядку виведіть чисел: для кожної події, що відбулась виведіть кількість сегментів, вказаних у звіті після цієї події.
Example 1
Ця задача складається з п'яти підзадач. Для підзадач виконуються додаткові обмеження, вказані в таблиці. Бали за підзадачу будуть нараховані лише за умови проходження усіх тестів підзадачі.
№ підзадачі | Бали | Обмеження | Примітка |
0 | 0 | Тести з умови | |
1 | 9 | 1 \leqslant N \leqslant 50; 1 \leqslant Q \leqslant 150 | |
2 | 11 | 1 \leqslant N \leqslant 500; 1 \leqslant Q \leqslant 250 | |
3 | 15 | 1 \leqslant N \leqslant 5000; 1 \leqslant Q \leqslant 1000 | |
4 | 20 | 1 \leqslant N \leqslant 50000; 1 \leqslant Q \leqslant 1000 | |
5 | 45 | 1 \leqslant N \leqslant 300000; 1 \leqslant Q \leqslant 300000 |