Kotori 和 Umi 正在进行一场由 Honoka 主持的取石子游戏。规则与经典游戏相同：有若干堆石子，玩家轮流从某一堆中取出任意数量的石子。无法进行合法操作的玩家输掉游戏。

然而，这次情况有所不同。作为主持人，Honoka 将准备 $n$ 堆候选石子堆，其中第 $i$ 堆初始有 $a_i$ 个石子。Honoka 将执行 $q$ 次操作，操作分为以下两种类型：

1. 给定三个整数 $l, r$ 和 $x$，对于所有 $l \le i \le r$，将第 $i$ 堆候选石子的数量更改为 $\max(b_i, x)$，其中 $b_i$ 是第 $i$ 堆候选石子当前的石子数量。
2. 给定三个整数 $l, r$ 和 $x$，开始一场由 $(r - l + 2)$ 堆石子组成的游戏，其中对于所有 $1 \le i < (r - l + 2)$，第 $i$ 堆包含 $b_{l-1+i}$ 个石子，而第 $(r - l + 2)$ 堆包含 $x$ 个石子。注意，此操作仅为查询答案，不会影响 $n$ 堆候选石子的状态。

Kotori 总是先手。作为 Kotori 的忠实粉丝，你想知道对于每一场石子游戏，如果双方都采取最优策略，Kotori 在第一步有多少种方法可以确保获胜。如果 Kotori 从不同的堆中取石子，或者从同一堆中取出不同数量的石子，我们认为这是两种不同的方式。

输入格式

每个测试文件中仅包含一组测试数据。

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 2 \times 10^5$)，分别表示候选石子堆的数量和操作次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 2^{30} - 1$)，其中 $a_i$ 表示第 $i$ 堆石子的初始数量。

接下来的 $q$ 行中，第 $i$ 行包含四个整数 $op_i, l_i, r_i$ 和 $x_i$ ($op_i \in \{1, 2\}, 1 \le l_i \le r_i \le n, 0 \le x_i \le 2^{30} - 1$)，表示第 $i$ 次操作，其中 $op_i$ 是操作类型，其余为操作参数。操作按执行顺序给出。

输出格式

对于每一种第二类型的操作，输出一行，包含一个整数，表示答案。

样例

样例输入 1

5 4
1 2 1 4 1
2 1 3 1
1 2 4 3
2 2 4 4
2 1 4 4

样例输出 1

1
0
3

说明

对于第一次操作，玩家将进行一场分别由 1, 2, 1 和 1 个石子组成的石子游戏。Kotori 唯一的获胜走法是将 2 个石子的堆减少到 1 个石子。

第二次操作后，候选石子堆中的石子数量变为 1, 3, 3, 4 和 1。

对于第四次操作，玩家将进行一场分别由 1, 3, 3, 4 和 4 个石子组成的石子游戏。Kotori 的获胜走法是将 1 个石子的堆减少到 0 个石子，或者将任意 3 个石子的堆减少到 2 个石子。