Ліхтарі#173

Ліхтарі

1.5 seconds
512 megabytes
Easy

Будимо, на якій живе Леді, освітлюють ліхтарів, пронумерованих підлягає вулиці від до . Один або кілька ліхтарів, що стоять підряд, наявемо сегментом. Таким чином, загальна кількість сегментів дорівнює \frac{N(N+1)}{2}. Сегмент вважається робочим, якщо лампочки в усіх ліхтарях цього сегмента працюють.

З ліхтарями регулярно відбуваються події одного з двох типів:

Після кожної такої події мерія мість, в якому живе Леді, вимагає від неї надати звіт про кількість робочих сегментів. Для покращення показників роботи ремонтників Леді включає у звіт усі сегменти, які є робочими на момент подання звіту або були робочими коли-небудь до цієї події.

Напишіть програму, яка після кожної події визначить кількість сегментів у звіті Леді.

Input

У першому рядку вхідного файлу знаходяться два натуральних числа і – кількість ліхтарів і кількість подій, що відбулись. Другий рядок вхідного файлу містить символів «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 приймають значення або .

Output

У першому рядку вихідного файлу виведіть єдине число – кількість діючих сегментів в початковому стані. Потім по одному в рядку виведіть чисел: для кожної події, що відбулась виведіть кількість сегментів, вказаних у звіті після цієї події.

Examples

Example 1

Loading
Loading

Scoring

Ця задача складається з п'яти підзадач. Для підзадач виконуються додаткові обмеження, вказані в таблиці. Бали за підзадачу будуть нараховані лише за умови проходження усіх тестів підзадачі.

№ підзадачі

Бали

Обмеження

Примітка

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