经过几天的战斗,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