Description

Kaiser终于成为冒险协会的一员。这次，冒险协会派他去冒险。他来到一处古墓，却被大门上的守护神挡住了去路。守护神给出了一个问题，只有答对了问题才能进入古墓。守护神给出了一个自然数序列 $a$，并要求你在序列上执行以下三种操作：

1. 给定 $l, r, x$，将序列第 $l$ 到第 $r$ 之间的所有数都执行按位与（AND）操作，操作数为 $x$。
2. 给定 $l, r, x$，将序列第 $l$ 到第 $r$ 之间的所有数都执行按位或（OR）操作，操作数为 $x$。
3. 给定 $l, r$，查询序列第 $l$ 到第 $r$ 之间的最大值。

Input Format

第一行包含两个整数 $n$ 和 $m$，分别表示序列的长度和操作的数量。

第二行包含 $n$ 个整数，表示序列 $a$。

接下来 $m$ 行，每行描述一个操作：

• 1：给出 $l, r, x$，将序列第 $l$ 到第 $r$ 之间的所有数都执行 AND 操作，操作数为 $x$。
• 2：给出 $l, r, x$，将序列第 $l$ 到第 $r$ 之间的所有数都执行 OR 操作，操作数为 $x$。
• 3：给出 $l, r$，询问序列第 $l$ 到第 $r$ 之间的最大值。

约束条件：

• $2 \leq n \leq 2 \times 10^5$
• $2 \leq m \leq 2 \times 10^5$
• $0 \leq a_i < 2^{20}$

Output Format

对于每个第三类询问，输出一个数字，即对应区间的最大值。

Example

3 5
9 19 0
3 2 3
2 3 3 18
1 2 2 10
3 1 2
1 1 3 11

19
9

Hint

出处: https://csacademy.com/contest/round-70/task/and-or-max/

Source

By 佚名上传