Description

猪国有 $n$ 只小猪。 它们都精通竞赛编程，第 $i$ 只小猪的 rating 为 $a_i$。 如果有 $k$ 只小猪 $p_1, p_2, \cdots, p_k$ 组队，那么队伍的 rating 为 $a_{p_1} \ \&\ a_{p_2}\ \&\ a_{p_3}\ \& \cdots \&\ a_{p_k}$，其中 $\&$ 表示按位与操作。

将要举办多场编程竞赛。 每场比赛，猪国只能派出一支队伍参赛。 对于第 $i$ 场比赛，只有编号在 $l_i$ 到 $r_i$ 之间（包含两端）的猪有空参加。 但由于经费短缺，必须从 $l_i$ 到 $r_i$ 之间恰好移除一只小猪，剩下的小猪才组队参赛。 猪头（教练）需要恰当选择不参赛的小猪，使得队伍 rating 最大。

但是，小猪们的 rating 可能会因为训练或参赛而变化。 作为猪头的好朋友，你的任务是维护小猪 rating 并处理以下 $q$ 个事件，事件有三种类型：

• $1 \; l \; r \; x$：猪头把编号 $l$ 到 $r$（包含两端）的每只小猪的 rating 与 $x$ 执行按位与操作。即对于所有 $l \le i \le r$，$a_i$ 变为 $a_i\ \&\ x$。
• $2 \; s \; x$：将第 $s$ 只小猪的 rating 变为 $x$。
• $3 \; l \; r$：猪头询问编号在 $l$ 到 $r$（包含两端）的小猪组队，并移除其中恰好一只后，队伍 rating 的最大值是多少。

Input Format

每个测试点仅有一组数据。

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

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$0 \le a_i < 2^{63}$），其中 $a_i$ 表示第 $i$ 只小猪的 rating。

接下来的 $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$）。

Output Format

对于每个第三类事件，输出一行一个整数，表示队伍可能得到的最大 rating。

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

7
6
7
3
3
8

Hint

由 ChatGPT 5 翻译