Ivan 正在他的笔记本上记录数字。起初，他写下了一个整数集合 $S$。 此后，他可以通过以下操作在笔记本上写下新的数字：

• 如果他已经写下了数字 $x$，他可以写下 $2x$。
• 如果他已经写下了数字 $x$，且 $x$ 能被 $2$ 整除，他可以写下 $\frac{x}{2}$。
• 如果他已经写下了不同的数字 $x$ 和 $y$，他可以写下 $x \oplus y$（其中 $\oplus$ 表示按位异或运算）。

记 $f(S)$ 为 Ivan 对于初始集合 $S$ 在笔记本上能写出的最小数字。 给定一个长度为 $N$ 的数组和 $Q$ 次查询，你需要执行以下操作之一：

• 将 $a[x]$ 的值修改为 $y$。
• 求 $f(\{a[L], a[L + 1], \dots, a[R]\})$ 的值。

输入格式

第一行包含一个整数 $N$ ($N \le 100000$)：数组的长度。 第二行包含 $N$ 个整数 $a[1], a[2], \dots, a[N]$ ($0 < a[i] < 2^{62}$)，即数组的元素。 第三行包含一个整数 $Q$ ($Q \le 100000$)：查询的数量。 接下来的 $Q$ 行描述了查询。查询格式为 "1 $x$ $y$"，表示将 $a[x]$ ($1 \le x \le N$) 修改为 $y$ ($0 < y < 2^{62}$)；或者为 "2 $l$ $r$"，表示求 $f(\{a[L], a[L + 1], \dots, a[R]\})$ 的值 ($1 \le L \le R \le N$)。

输出格式

对于每个类型为二的查询，输出一行 $f(\{a[L], a[L + 1], \dots, a[R]\})$ 的值。

样例

样例输入 1

3
3 5 15
3
2 1 3
1 2 11
2 1 2

样例输出 1

3
1