Додека го чекале Дедо Мраз да се врати, 3 од неговите џуџиња го украсувале неговиот двор со светилки. Џуџето Мартин најпрво поставило N светилки во една линија и ја поставило i-тата светилка во состојба Ai, 1 <= i <= N, каде 1 означува вклучена светилка, а 0 означува исклучена светилка. Мартин бил задоволен со моменталната состојба на сите светилки, но останатите две џуџиња Тијана и Алтин не биле. Алтин сакал да има што повеќе вклучени светилки, додека Тијана сакала да има помалку вклучени светилки. Тие почнале да одат наоколу и да ја поставуваат состојбата на некои последователни светилки. Мартин испаничил дека веќе нема да е задоволен од состојбата на светилките, но сфатил дека само сака во некои делови да има доволно светлина, односно го интересира колку вклучени светилки има во некој дел. Се бара од вас да ги набљудувате џуџињата Алтин и Тијана и да одговарате на прашањата на Мартин.

Влез

Во првиот ред се наоѓаат броевите N (1 ≤ N ≤ 100000) и Q (1 ≤ Q ≤ 100000).
Во вториот ред се наоѓаат N броеви, 1 или 0, кои ја означуваат почетната состојба на светилките.
Во следните Q редови се дадени информации за движењата на џуџињата.
Ред со формат “+ A B” означува дека Алтин ги вклучил сите светла во [A, B], каде 1 ≤ A ≤ B ≤ N.
Ред со формат “- A B” означува дека Тијана ги исклучила сите светла во [A, B], каде 1 ≤ A ≤ B ≤ N.
Ред со формат “? A B” означува дека Мартин ви поставува прашање за тоа колку вклучени светла има во интервалот [A, B], каде 1 ≤ A ≤ B ≤ N.

Излез

За секое прашање на Мартин испечатете го во посебен ред соодветниот одговор.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
7 6
0 0 0 1 1 1 1
? 2 6
- 5 6
? 3 7
+ 2 5
- 3 6
? 1 4

излез
3
2
1