在 Pigeland 有 $n$ 只小猪。它们都精通程序设计竞赛，第 $i$ 只小猪的评分为 $a_i$。如果 $k$ 只小猪 $p_1, p_2, \dots, p_k$ 组成一个团队，那么该团队的评分将是 $a_{p_1} \& a_{p_2} \& a_{p_3} \& \dots \& a_{p_k}$，其中 $\&$ 表示按位与运算。

有一些程序设计竞赛即将举行。Pigeland 可以在每场比赛中派出恰好一个团队。对于第 $i$ 场比赛，只有编号在 $l_i$ 到 $r_i$ 之间（包含边界）的小猪有时间参加。不幸的是，由于资金短缺，必须从编号在 $l_i$ 到 $r_i$ 之间的小猪中恰好移除一只。同时，区间内的所有其他小猪都将参加比赛。Pigeland 的教练 Pig-head 需要妥善选择不参加比赛的小猪，以使团队的评分最大化。

然而，通过训练和参加比赛，小猪的评分可能会发生变化。作为 Pig-head 最好的朋友，你的任务是维护这些小猪的评分，以应对以下三种类型的 $q$ 个事件：

• $1\ l\ r\ x$：Pig-head 将编号在 $l$ 到 $r$ 之间（包含边界）的每只小猪的评分与 $x$ 进行按位与运算。更正式地说，对于所有 $l \le i \le r$，$a_i$ 变为 $a_i \& x$。
• $2\ s\ x$：Pig-head 将第 $s$ 只小猪的评分修改为 $x$。
• $3\ l\ r$：Pig-head 询问在编号 $l$ 到 $r$ 之间（包含边界）选择小猪组成团队并移除恰好一只小猪时，所能获得的最大评分。

输入格式

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

第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 10^6, 1 \le q \le 10^6$)，分别表示小猪的数量和事件的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i < 2^{63}$)，其中 $a_i$ 表示第 $i$ 只小猪的评分。

接下来的 $q$ 行中，第 $i$ 行首先包含一个整数 $op_i$ ($op_i \in \{1, 2, 3\}$)，表示第 $i$ 个事件的类型。如果 $op_i = 1$，则后面跟着三个整数 $l, r$ 和 $x$ ($1 \le l \le r \le n, 0 \le x < 2^{63}$)；如果 $op_i = 2$，则后面跟着两个整数 $s$ 和 $x$ ($1 \le s \le n, 0 \le x < 2^{63}$)；如果 $op_i = 3$，则后面跟着两个整数 $l$ 和 $r$ ($1 \le l < r \le n$)。

输出格式

对于每个第三类事件，输出一行，包含一个整数，表示团队的最大评分。

样例

输入 1

5 9
7 7 7 6 7
3 1 5
2 1 3
3 1 5
3 1 3
1 1 2 3
3 1 3
2 2 8
3 1 3
3 1 2

输出 1

7
6
7
3
3
8