Lamps

Now it's Ayhan's and Raul's turn to play with light bulbs. Raul has arranged $n$ light bulbs in a row, numbered from $1$ to $n$. Initially, some of these bulbs are lit, and some are turned off. A segment of consecutive light bulbs is considered beautiful if all the bulbs in this segment are turned on. As we know, the number of all possible segments of the bulb equals $n\cdot (n+1)/2$. Some of them may be beautiful initially.

Raul first asks Ayhan how many beautiful segments are in the sequence of light bulbs in the original state. Then, to annoy Ayhan, he either turns off or turns on all the bulbs in a specific range $q$ times, and each time he asks Ayhan how many segments became beautiful up to the current moment. Ayhan is tired of answering Raul's endless questions. Help him with this task.

Input

The first line contains two integers $n$ and $q(1\le n,q\le 3\cdot 10^5)$. The next line contains a string $s$ consisting of $n$ characters $0$ and $1$. $s_i=0$ means that the $i$-th bulb is initially turned off, and $s_i=1$ means that it is turned on.

Each of the next $q$ lines contains three integers $l_i,r_i(1\le l_i\le r_i\le n,1\le i\le q)$ and $c_i(0\le c_i\le 1,1\le i\le q)$.

If $c_i=0$, Raul turns off all the bulbs that are turned on in the interval $[l_i,r_i]$. If $c_i=1$, then he turns on all the bulbs that are turned off in this interval.

Output

In the first line, print the number of segments that were initially beautiful, and in the following lines, print the number of segments that became beautiful up to the current moment after performing the corresponding query.

Examples

Scoring

This problem consists of $5$ subtasks. Points for each subtask are awarded only if all tests related to this subtask are passed successfully.

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

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

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

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

5. ($32$ points): no additional restrictions;