题目描述

译自 ROI 2015 Day2 T3. Фонари

水下运河街由 $n$ 盏路灯照明，路灯沿街从 $1$ 到 $n$ 编号。称一个或多个连续的路灯为一个段。因此，段的总数为 $\frac{n(n+1)}{2}$。如果一个段内所有路灯的灯泡都正常工作，则该段被认为是正常的。

路灯经常发生以下两种事件之一：

• 由于电压波动，某个段内的所有灯泡同时烧坏；
• 能源公司选择某个段，派遣维修人员更换该段内所有烧坏的灯泡，使其恢复正常。

每次事件后，市政府要求能源公司提交报告，说明正常段的数量。为了改善工作绩效报告，维修人员在报告中包含当前正常或曾经正常过的所有段。

你的任务是编写一个程序，计算每次事件后，报告中包含的段的数量，即当前正常或在该事件之前曾经正常过的段的数量。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $q$，分别表示路灯数量和发生的事件数量。

第二行包含 $n$ 个字符 0 或 1，描述路灯的初始状态，其中 1 表示灯泡正常的路灯，0 表示灯泡烧坏的路灯。

接下来的 $q$ 行，每行描述一个事件，包含三个整数 $l_i, r_i, c_i$，表示在该事件后，编号从 $l_i$ 到 $r_i$ 的路灯的所有灯泡：

• 当 $c_i = 0$ 时，全部烧坏；
• 当 $c_i = 1$ 时，全部恢复正常。

所有事件的描述满足 $1 \le l_i \le r_i \le n$，且 $c_i$ 取值为 $0$ 或 $1$。

输出格式

输出的第一行包含一个整数，表示初始状态下正常段的数量。接下来输出 $q$ 行，每行一个整数，表示每次事件后报告中包含的段的数量。

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

5
13
13
19
28

数据范围与提示

详细子任务附加限制及分值如下表所示：