题目背景

某编程网站 BTC 长期在它的 Beginner Contest 的最后一题放科技模板题，于是 APJifengc 愤怒地在它的评测机上洒了若干瓶冰红茶，导致一些评测单元的运行速度快了 $10^{12}$ 倍，暴力跑得和正解一样快。

因为 BTC 不能出科技模板题了，所以 BTC 的站长想要让你维护一下 APJifengc 每次洒冰红茶后可用的评测单元个数，以便于统筹评测资源与灾后重建。

已加入 Hack 数据，位于 Subtask 5，不计分。

题目描述

有 $n$ 个 bot 排成一排，每天所有 bot 都会喝冰红茶。

要求动态维护一排 bot，有三种操作或询问：

• 1 l r k，表示 $[l,r]$ 内的 bot 会喝 $k$ 瓶原味冰红茶、$[l,r]$ 外的 bot 会喝 $k$ 瓶热带风味冰红茶。
• 2 l r k，表示 BTC 站长愤怒地把 $[l,r]$ 中最后连续喝了至少 $k$ 瓶口味相同的冰红茶的 bot 击毁。
• 3，查询有多少个存活的 bot。

注：在 2 操作中，击毁不会改变 bot 的编号。

输入格式

第一行两个正整数 $n,q$。

后 $q$ 行，每行描述一个操作或询问，形如以下三种中的一种：

• 1 l r k；
• 2 l r k；
• 3。

输出格式

若干行，每行回答一个询问 3。

5 12
1 3 4 8
3
2 3 4 6
3
1 2 2 3
3
2 1 5 6
3
1 2 3 3
3
2 1 5 3
3

5
3
3
1
1
0

9 18
1 8 9 5
3
1 5 8 20
3
2 8 9 18
3
2 6 9 6
3
2 1 2 5
3
2 9 9 8
3
2 3 9 14
3
1 6 8 13
3
2 3 5 17
3

9
9
7
5
3
3
0
0
0

提示

样例 1 解释

只说明操作 1 和操作 2。

第一次操作，三号和四号 bot 喝了 8 瓶原味冰红茶，其他 bot 喝了 8 瓶热带风味冰红茶。

第二次操作，三号和四号 bot 连续喝了 8 瓶原味冰红茶，被击毁，现在场上还有 3 个存活 bot。

第三次操作，二号 bot 喝了 3 瓶原味冰红茶，其他 bot 喝了 3 瓶热带风味冰红茶。

第四次操作，一号和五号 bot 连续喝了 11 瓶热带风味冰红茶，被击毁，现在场上还有 1 个存活 bot。

第五次操作，二号 bot 喝了 3 瓶原味冰红茶。

第六次操作，二号 bot 连续喝了 6 瓶原味冰红茶，被击毁，现在场上没有存活的 bot。

数据范围

本题采用捆绑测试。

• Subtask 1 (5pts)：$n,q\le 10^3$。
• Subtask 2 (20pts)：所有操作 2 中 $k\le 20$。
• Subtask 3 (25pts)：保证数据随机生成。
• Subtask 4 (50pts)：无特殊限制。

其中 Subtask 3 的测试数据生成方式如下：

1. 对于每次或询问，从三种类型中等概率选择一个；
2. 若选取的操作不为 3，那么从 $\left[1, n\right]$ 中等概率生成两个数 $l, r$，若 $l > r$，则交换 $l, r$，并将 $l, r$ 作为操作的参数；
3. 若选取的操作不为 3，那么从 $\left[1, 10^6\right]$ 中等概率生成一个数 $k$ 作为操作的参数。

对于全部数据，保证 $1\le n,q\le 2\times 10^5$，$1\le k\le 10^{6}$。