题目描述

给定一个长度为 $n$ 的序列 $A_i$，下标从 $1$ 开始。对其依次进行 $m$ 次操作或询问，分为 $3$ 种类型：

• 1 l r x：将 $A_{l...r}$ 中每个元素二进制与上一个数 $x$
• 2 l r x：将 $A_{l...r}$ 中每个元素二进制或上一个数 $x$
• 3 l r：求 $A_{l...r}$ 中的最小值

输入格式

第一行两个整数 $n, m$。

接下来一行 $n$ 个整数表示序列 $A_1, ..., A_n$。

接下来 $m$ 行一行表示一个操作或询问，格式如上文所述。

输出格式

对于每个询问，输出一行一个整数表示最小值。

样例

input

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

output

1
2

数据范围与提示

对于所有数据，$1 \leq n, m \leq 500000, 0 \leq A_i, x_i < 2^{31}$。

• 子任务 $\rm 1(points: 20)$：$n, m \leq 1000$
• 子任务 $\rm 2(points: 20)$：$n, m \leq 10000$
• 子任务 $\rm 3(points: 30)$：$n, m \leq 100000$
• 子任务 $\rm 4(points: 30)$：$n, m \leq 500000$