Lampalar

İndi isə lampalarla oynama növbəsi Ayxanla Raulundur. Raul bir cərgədə $1$-dən $n$-ə tam ədədlərlə nömrələnmiş $n$ lampa düzüb. Başlanğıcda bu lampalardan bəziləri yanılı bəziləri isə sönülü vəziyyətdədir. Ardıcıl gələn lampalar seqmenti o halda gözəl sayılır ki, həmin seqmentdəki bütün lampalar yanılı olsun. Məlum olduğu kimi bütün mümkün lampa seqmentləri $n\cdot (n+1)/2$ saydadır. Başlanğıcda bəziləri gözəl ola bilər.

Raul Ayxandan ilk olaraq başlanğıc vəziyyətdə lampalar ardıcıllığındakı gözəl seqmentlərin sayını soruşur. Daha sonra Ayxanı bezdirmək üçün $q$ dəfə ya hansısa aralıqdakı bütün lampaları sönülü ya da yanılı vəziyyətə gətirib Ayxandan indi və ya indiyə kimi nə vaxtsa gözəl olmuş seqmentlərin sayını soruşur. Ayxan Raulun bitmək bilməyən suallarına cavab verməkdən yorulub, bu işdə ona kömək edin.

Giriş verilənləri

Birinci sətirdə iki tam ədəd, $n$ və $q(1\le n,q\le 3\cdot 10^5)$ verilir. Növbəti sətirdə $n$ sayda $0$ və $1$ simvollarından ibarət $s$ sətri verilir. $s_i=0$ $i$-ci lampanın başlanğıcda sönülü, $s_i=1$ isə yanılı olduğunu bildirir.

Növbəti $q$ sətrin hər birində üç tam ədəd $l_i,r_i(1\le l_i\le r_i\le n,1\le i\le q)$ və $c_i(0\le c_i\le 1,1\le i\le q)$ verilir.

$c_i=0$ olarsa, Raul $[l_i,r_i]$ aralığında yanılı olan bütün lampaları söndürür, $c_i=1$ olarsa o, bu aralıqdakı bütün sönülü olan lampaları yandırır.

Çıxış verilənləri

İlk sətirdə başlanğıcda gözəl olan seqmentlərin sayını, növbəti sətirlərdə hər sorğunu icra etdikdən sonra həmin anda və ya daha əvvəl nə vaxtsa gözəl olmuş seqmentlərin sayını çap edin.

Nümunələr

Qiymətləndirmə

Bu məsələ aşağıdakı kimi $5$ alt tapşırıqdan ibarətdir. Alt tapşırıq üçün ballar yalnız bu alt tapşırığa aid bütün testlər uğurla keçdikdə verilir.

1. ($17$ bal): $n\le 50,q\le 150$;

2. ($19$ bal): $n\le 500,q\le 250$;

3. ($12$ bal): $n\le 5000,q\le 1000$;

4. ($20$ bal): $n\le 50000,q\le 1000$;

5. ($32$ bal): Əlavə məhdudiyyət yoxdur;