Phoenix 喜欢玩位——具体来说,就是使用按位运算 AND、OR 和 XOR。他有 $$$n$$$ 个整数 $$$a_1, a_2, \dots, a_n$$$,并将执行 $$$q$$$ 以下查询:
1. 将 $$$l \le a_i \le r$$$ 处的所有数字 $$$a_i$$$ 替换为 $$$a_i$$$ AND $$$x$$$;
2. 将 $$$l \le a_i \le r$$$ 处的所有数字 $$$a_i$$$ 替换为 $$$a_i$$$ 或 $$$x$$$;
3. 将 $$$l \le a_i \le r$$$ 处的所有数字 $$$a_i$$$ 替换为 $$$a_i$$$ XOR $$$x$$$;
4.输出多少个不同的整数$$$a_i$$$,其中$$$l \le a_i \le r$$$。
对于每个查询,Phoenix 都会获得 $$$l$$$、$$$r$$$ 和 $$$x$$$。请注意,他考虑的是数字的值,而不是它们的指数。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le q \le 10^5$$$) - 分别是整数的数量和查询的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < 2^{20}$$$) - Phoenix 开头的整数。
接下来的 $$$q$$$ 行包含查询。对于每个查询,每行的第一个整数是 $$$t$$$ ($$$1 \le t \le 4$$$) — 查询的类型。
如果 $$$t \in \{1, 2, 3\}$$$,则后面将是三个整数 $$$l_i$$$、$$$r_i$$$ 和 $$$x_i$$$ ($$$0 \le l_i, r_i, x_i < 2^{20}$$$; $$$l_i \le r_i$$$)。
否则,如果 $$$t=4$$$,则后面将有两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$0 \le l_i \le r_i < 2^{20}$$$)。
保证至少有一个$$$t=4$$$ 的查询。
输出
打印每个查询的答案,其中 $$$t=4$$$。
示例
输入 #1
5 6 5 4 3 2 1 1 2 3 2 4 2 5 3 2 5 3 4 1 6 2 1 1 8 4 8 10
输出 #1
3 2 1
输入 #2
6 7 6 0 2 3 2 7 1 0 4 3 2 6 8 4 4 0 7 3 2 5 3 1 0 1 2 4 0 3 4 2 7
输出 #2
5 1 2
注意
在第一个示例中:
- 对于第一个查询,$$$2$$$ 替换为 $$$2$$$ AND $$$2 = 2$$$,$$$3$$$ 替换为 $$$3$$$ AND $$$2 = 2$$$。这组数字是 $$$\{1, 2, 4, 5\}$$$。
- 对于第二个查询,$$$2$$$ 和 $$$5$$$ 之间有 $$$3$$$ 不同的数字:$$$2$$$、$$$4$$$ 和 $$$5$$$。
- 对于第三个查询,$$$2$$$ 替换为 $$$2$$$ XOR $$$3 = 1$$$,$$$4$$$ 替换为 $$$4$$$ XOR $$$3 = 7$$$,$$$5$$$ 替换为 $$$5$$$ XOR $$$3 = 6$$$。这组数字是 $$$\{1, 6, 7\}$$$。
- 对于第四个查询,$$$1$$$ 和 $$$6$$$ 之间有 $$$2$$$ 不同的数字:$$$1$$$ 和 $$$6$$$。
- 对于第五个查询,$$$1$$$ 替换为 $$$1$$$ OR $$$8 = 9$$$。这组数字是 $$$\{6, 7, 9\}$$$。
- 对于第六个查询,$$$8$$$ 和 $$$10$$$ 之间有一个不同的数字:$$$9$$$。