题目描述

给您一个长度为 $n$ 的序列 $a$，请您支持 $m$ 次操作：

1. 将 $[l,r]$ 区间中 $> x$ 的数减去 $x$。
2. 求 $[l,r]$ 区间中 $\le x$ 的数的个数。

输入格式

本题强制在线。

第一行两个整数 $n,m$。

第二行 $n$ 个整数表示 $a$。

下面 $m$ 行，每行四个整数 $opt,l,r,x'$，$opt$ 表示操作编号，$x'$ 异或上次操作 $2$ 答案得到真实的 $x$。若此前没有操作 $2$，则不需要进行异或操作，真实的 $x$ 即为 $x'$。

输出格式

对于所有操作 $2$，每行输出一个整数表示答案。

10 10
20 10 20 14 4 15 11 20 2 13 
2 5 9 1
1 7 8 2
1 2 3 8
1 4 6 12
2 1 7 9
2 2 7 20
2 3 9 4
2 8 9 7
1 3 10 0
2 8 9 7

0
5
6
2
1
1

5 5
6 10 3 4 7 
1 1 3 3
1 3 4 3
2 3 5 3
1 1 3 11
2 2 3 5

2
2

提示

Idea：Ntokisq&nzhtl1477，Solution：Ntokisq，Code：Ntokisq，Data：Ntokisq

样例解释

样例 $1$ 未加密前：

10 10
20 10 20 14 4 15 11 20 2 13
2 5 9 1
1 7 8 2
1 2 3 8
1 4 6 12
2 1 7 9
2 2 7 17
2 3 9 2
2 8 9 5
1 3 10 1
2 8 9 6

样例 $2$ 未加密前：

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

数据规模

本题采用捆绑测试。 | $\text{Subtask}$ | $n\le$ | $m\le$ | $\text{Score}$ | 时间限制 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $10^4$ | $10^4$ | $10$ | $\text{1s}$ | | $2$ | $3\times 10^5$ | $3\times 10^5$ | $30$ | $\text{5s}$ | | $3$ | $7\times 10^5$ | $5\times 10^5$ | $60$ | $\text{20s}$ |

对于 $100\%$ 的数据，$1\le n \le 7\times 10^5$，$1\le m\le 5\times 10^5$，$1\le a_i,x\le 10^9$，$1\le l\le r\le n$。

提示

如果您认为您的算法时间复杂度正确但常数过大，您可以使用同样思路但时间复杂度略高、常数小的算法。