给定一个大小为 $n$ 的数组 $a$，你需要对其执行 $m$ 次查询。查询共有三种类型：

1. & l r x：将所有 $i = l, l + 1, \dots, r$ 的 $a_i$ 修改为 $(a_i \text{ AND } x)$；
2. | l r x：将所有 $i = l, l + 1, \dots, r$ 的 $a_i$ 修改为 $(a_i \text{ OR } x)$；
3. ? l r：查询 $a_l, a_{l+1}, \dots, a_r$ 中的最小值。

输出所有第三类查询的答案。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)，表示数组的大小。 第二行包含 $n$ 个空格分隔的整数 $a_i$ ($0 \le a_i < 2^{30}$)，表示数组元素。 第三行包含一个整数 $m$ ($1 \le m \le 2 \cdot 10^5$)，表示查询次数。 接下来的 $m$ 行包含上述格式的查询描述。对于所有查询，满足 $1 \le l \le r \le n$；对于第一类和第二类查询，满足 $0 \le x < 2^{30}$。

输出格式

对于每个第三类查询，在一行中输出答案。

样例

输入 1

5
1 2 3 4 5
4
& 1 2 6
| 3 5 4
? 1 2
? 3 5

输出 1

0
4