Streetlights

The Underwater Canal street is lit by $n$ streetlights, numbered 1 to $n$ along the street. A segment is one or more streetlights that stand consecutively. Thus the total number of segments is $\frac{n(n+1)}{2}$. A segment is healthy if the bulbs in all of its streetlights are working.

Events of one of two types happen to the streetlights regularly:

• in some segment, a voltage surge burns out all the bulbs at once;
• Arkhenergo picks some segment and sends repair crews to replace every burnt-out bulb in it with a working one.

After each event, the city hall demands that Arkhenergo report the number of healthy segments. To make their performance look better, the repair crews include in the report every segment that is healthy now or was ever healthy before.

Write a program that determines, after each event, the number of segments that are healthy at that moment or were healthy at any time before that event.

The first line of the input contains two numbers $n$ and $q$, the number of streetlights and the number of events that happened. The next line of the input consists of $n$ characters 0 and 1 describing the initial state of the streetlights, where 1 denotes a streetlight with a working bulb and 0 denotes one with a burnt-out bulb.

Each of the following $q$ lines contains a description of an event as three numbers $l_i, r_i$, and $c_i$, which mean that after this event all bulbs in the streetlights numbered $l_i, l_i+1, \ldots, r_i$:

• burn out if $c_i = 0$,
• become working if $c_i = 1$.

In the descriptions of all events $1 \le l_i \le r_i \le n$, and $c_i$ takes the value $0$ or $1$.

In the first line of the output, print a single number: the number of healthy segments in the initial state. Then print $q$ numbers, one per line: for each event that happened, print the number of segments listed in the report after that event.

• $1 \le n \le 300\,000$
• $1 \le q \le 300\,000$