题目描述

莱迪居住的街道由 $N$ 盏路灯照亮，这些路灯沿街编号为 $1$ 到 $N$。一盏或多盏连续路灯构成一个路灯段。因此，总共有 $\frac{N\cdot (N+1)}{2}$ 个路灯段。如果一个路灯段内所有路灯的灯泡都在工作，那么这个路灯段称为工作段。

路灯会定期发生以下两种事件之一：

• 某个路灯段内，因为电压突然升高，所有灯泡同时烧坏；
• 莱迪选择某个路灯段并叫来维修工，让他们替换其中所有已经烧坏的灯泡。

每次事件之后，莱迪所在城市的市长都会要求她提供一份报告，说明工作段的数量。为了提高维修工的工作指标，莱迪会把所有当前正在工作的路灯段，以及在这次事件之前曾经工作过的路灯段，全部写入报告。

请编写程序，在每次事件后确定莱迪报告中的路灯段数量。

输入格式

第一行包含两个自然数 $N$ 和 $Q$，分别表示路灯数量和发生的事件数量。

第二行包含 $N$ 个字符 0 和 1，表示每盏路灯的初始状态，其中 1 表示灯泡正常工作，0 表示灯泡烧坏。

接下来 $Q$ 行，每行包含三个整数 $L_i,R_i,C_i$，描述一次事件。事件发生后，第 $L_i,L_i+1,\ldots,R_i$ 盏路灯中的所有灯泡：

• 当 $C_i=0$ 时烧坏；
• 当 $C_i=1$ 时被替换为正常工作。

所有事件均满足 $1\le L_i\le R_i\le N$，且 $C_i$ 的值为 $0$ 或 $1$。

输出格式

第一行输出初始状态下工作段的数量。

接下来输出 $Q$ 行：对于每次事件，输出这次事件后莱迪报告中的路灯段数量。

样例

样例 1

7 4
1100101
4 6 1
3 6 0
3 4 1
5 7 1

5
13
13
19
28

计分方式