题号：NC20710
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
给定一个长n的01串s，有4种操作：
1. 区间赋值为0；
2. 区间赋值为1；
3. 撤销第i次操作（保证第i次操作的种类为区间赋值）（撤销不影响前面或后面的操作）；
4. 查询区间中1的个数。
现在有m次操作，你需要对每次询问（操作4）输出答案。
例如：串s为：0000
1. 区间[3,4]赋值为1：0011
2. 区间[2,3]赋值为1：0111
3. 撤销第1次操作，串s变成：0110
输入描述:
第一行两个整数n,m，分别表示s的长度及操作总数。
第二行一个长为n的串s。
接下来m行，第一个数opt为操作种类（1≤opt≤4）。
若opt=1，接下来两个整数l,r，表示将s[l..r]赋值为0。
若opt=2，接下来两个整数l,r，表示将s[l..r]赋值为1。
若opt=3，接下来一个整数k，表示撤销第k次操作optk。
若opt=4，接下来两个整数l,r，表示询问s[l..r]中1的个数。
保证1≤li≤ri≤n；
保证opti=3时，optk=1或2（即撤销的操作种类为操作一或操作二）。
一个操作不会被撤销多次。
输出描述:
对于每次操作4，输出一行一个整数，表示询问区间s[l..r]中1的个数。
示例1
输入
复制
4 6
0000
2 3 4
4 2 3
2 2 3
4 2 3
3 1
4 2 3
备注:
1≤n≤104，1≤m≤2×104。