Description

Kotori 和 Umi 正在玩由 Honoka 主持的石子游戏。规则与经典游戏相同：有若干堆石子，玩家轮流从一堆中移走任意数量的石子。不能进行合法移动的玩家输掉游戏。

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

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

Kotori 总是第一个行动。作为 Kotori 的忠实粉丝，你想知道对于每个石子游戏，如果双方都使用最佳策略，Kotori 在第一步中确保胜利的方法数。我们认为两种方法不同，如果 Kotori 从不同的堆中取石子，或者从同一堆中取不同数量的石子。

Input Format

每个测试文件中只有一个测试用例。

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

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, 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$ 是操作类型，其他是操作的参数。操作按执行顺序给出。

Output Format

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

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

1
0
3

Hint

对于第一个操作，玩家将进行一个由 $1$、$2$、$1$ 和 $1$ 个石子组成的石子游戏。Kotori 唯一的获胜方式是将有 $2$ 个石子的堆减少到 $1$ 个石子。

在第二个操作之后，候选石子堆中的石子数量变为 $1$、$3$、$3$、$4$ 和 $1$。

对于第四个操作，玩家将进行一个由 $1$、$3$、$3$、$4$ 和 $4$ 个石子组成的石子游戏。Kotori 的获胜方式是将有 $1$ 个石子的堆减少到 $0$ 个石子，或者将任何有 $3$ 个石子的堆减少到 $2$ 个石子。

题面翻译由 ChatGPT-4o 提供。