← 返回题目列表

Codeforces · 896/E

E. 欢迎回家,Chtholly

中文机器翻译题面 查看原题

经过几天的战斗,Chtholly Nota Seniorious 奇迹般地从激战中归来。

正如所承诺的,威廉现在正在为她烤黄油蛋糕。

不过,威廉虽然擅长制作甜点,却很少烤黄油蛋糕。

这一次,威廉犯了一个大错误——他不小心打破了烤箱!

幸运的是,Chtholly决定帮助他。

威廉将 n 个蛋糕放在卷上,蛋糕编号从 1 到 n,第 i 个蛋糕需要 ai 秒的烘烤时间。

威廉需要 Chtholly 进行 m 次操作来烘烤蛋糕。

操作 1:1 l r x

Willem要求Chtholly检查[l,r]范围内的每个蛋糕,如果蛋糕需要烘烤超过x秒,他会烘烤x秒并将其放回原位。更准确地说,对于范围 [l, r] 中的每个 i,如果 ai 严格大于 x,则 ai 等于 ai - x。

操作 2:2 l r x

Willem 要求 Chtholly 计算 [l, r] 范围内需要精确烹饪 x 秒的蛋糕数量。更正式地说,您应该在 [l, r] 范围内找到这样的 i 的数量,即 ai = x。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 105)。

第二行包含n个整数,其中第i个是ai (1 ≤ ai ≤ 105)。

接下来的 m 行是上面描述的 m 个操作。保证 1 ≤ l ≤ r ≤ n 且 1 ≤ x ≤ 105。

输出

对于第二类操作,打印答案。

示例

输入 #1

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

输出 #1

3
3
0
3

输入 #2

7 7
1 9 2 6 8 1 7
2 1 7 1
2 2 5 2
1 4 7 7
2 2 4 2
1 3 4 5
2 3 3 3
2 3 7 2

输出 #2

2
1
1
0
1

输入 #3

8 13
75 85 88 100 105 120 122 128
1 1 8 70
2 3 8 30
1 3 8 3
2 2 5 15
1 2 4 10
2 1 5 5
1 2 7 27
2 1 5 5
1 3 7 12
1 1 7 4
2 1 8 1
1 4 8 5
2 1 8 1

输出 #3

1
2
3
4
5
6