题目背景

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

题目描述

在“水下运河”街上共有 $n$ 盏路灯，沿街从 1 到 $n$ 编号。连续的一段路灯称为一个区段。因此，总的区段数量等于 $\frac{n(n+1)}{2}$。如果某个区段内的所有路灯都亮着（即灯泡完好），则称该区段为正常工作的。

路灯上可能发生两种类型的事件：

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

在每次事件发生后，市政$$府都会要求提交一份报告，说明当前正常工作的区段数量。为了提升业绩指标，维修部门在报告中会包含所有现在正常或曾经正常的区段。

请你编写一个程序，在每次事件之后，计算到目前为止（包括此次事件）当前正常或曾经正常的区段数量。

输入格式

第一行包含两个整数 $n$ 和 $q$ —— 分别表示路灯的数量和事件的数量。

第二行包含一个由 $n$ 个字符组成的字符串，仅包含 0 和 1：

• 1 表示该路灯灯泡完好；
• 0 表示该路灯灯泡已烧坏。

接下来 $q$ 行中，每行包含三个整数 $l_i, r_i, c_i$，表示一次事件：

• 若 $c_i = 0$，则编号从 $l_i$ 到 $r_i$（包含两端）的所有路灯灯泡全部烧坏；
• 若 $c_i = 1$，则编号从 $l_i$ 到 $r_i$ 的所有灯泡全部更换为新的、完好的灯泡。

保证 $1 \le l_i \le r_i \le n$，且 $c_i$ 仅取值 0 或 1。

输出格式

第一行输出一个整数 —— 初始状态下正常工作的区段数量。接下来输出 $q$ 行，第 $i$ 行输出在第 $i$ 次事件之后，所有当前正常或曾经正常的区段数量。

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

5
13
13
19
28

提示

数据范围

子任务编号	分值	$n$ 范围	$q$ 范围
1	17	$1 \le n \le 50$	$1 \le q \le 150$
2	19	$1 \le n \le 500$	$1 \le q \le 250$
3	12	$1 \le n \le 5000$	$1 \le q \le 1000$
4	20	$1 \le n \le 50\,000$
5	32	$1 \le n \le 300\,000$	$1 \le q \le 300\,000$