Лампи

Тепер черга Айхана і Рауля грати з лампочками. Рауль розташував у ряд $n$ лампочок, пронумерованих цілими числами від $1$ до $n$. Спочатку деякі з цих ламп горять, а деякі вимкнені. Сегмент послідовних лампочок вважається красивим, якщо всі лампочки в цьому сегменті увімкнені. Як ми знаємо, кількість всіх можливих сегментів лампи дорівнює $n\cdot (n+1)/2$. Деякі можуть бути красивими від початку.

Спочатку Рауль питає Айхана, скільки красивих сегментів у послідовності лампочок у вихідному стані. Потім, щоб дратувати Айхана, він $q$ разів або вимикає, або увімкає всі лампи в певному діапазоні, і кожного разу питає Айхана, скільки сегментів становилися красивими до поточного моменту. Айхан втомився відповідати на безкінечні питання Рауля. Допоможіть йому з цим завданням.

Вхідні дані

У першому рядку задаються два цілих числа $n$ і $q(1\le n,q\le 3\cdot 10^5)$. У наступному рядку задається рядок $s$, що складається з $n$ символів $0$ і $1$. $s_i=0$ означає, що $i$-та лампа спочатку вимкнена, а $s_i=1$ означає, що вона увімкнена.

Кожного з наступних $q$ рядків містить три цілих числа $l_i,r_i(1\le l_i\le r_i\le n,1\le i\le q)$ і $c_i(0\le c_i\le 1,1\le i\le q)$.

Якщо $c_i=0$, Рауль вимикає всі лампи, що увімкнені в інтервалі $[l_i,r_i]$. Якщо $c_i=1$, то він увімкнює всі лампи, що вимкнені в цьому інтервалі.

Вихідні дані

У першому рядку виведіть кількість сегментів, які спочатку були красивими, а в наступних рядках — кількість сегментів, які становилися красивими до поточного моменту після виконання відповідного запиту.

Приклади

Оцінювання

Це завдання складається з $5$ підзадач. Очки за кожну підзадачу нараховуються лише в разі успішного проходження всіх тестів, пов'язаних з цією підзадачею.

1. ($17$ балів): $n\le 50,q\le 150$;

2. ($19$ балів): $n\le 500,q\le 250$;

3. ($12$ балів): $n\le 5000,q\le 1000$;

4. ($20$ балів): $n\le 50000,q\le 1000$;

5. ($32$ балів): немає додаткових обмежень;