NAND（与非）是一种按位运算，定义如下：$a \text{ NAND } b := \text{NOT } (a \text{ AND } b)$。

Zag 得到了一个由 $n$ 个 32 位无符号整数组成的数组 $a$。他要求你为他执行两种类型的操作，具体描述如下。

输入格式

第一行包含两个整数 $n, q$（$1 \le n, q \le 10^5$），分别表示数组的长度和询问的个数。

第二行包含 $n$ 个整数 $a_i$（$0 \le a_i < 2^{32}$）。

接下来 $q$ 行，每行包含一个以下两种类型之一的操作：

• 1 l r x（$1 \le l \le r \le n, 0 \le x < 2^{32}$），表示你需要计算并输出 $x \text{ NAND } a_l \text{ NAND } a_{l+1} \text{ NAND } \dots \text{ NAND } a_r$ 的值。
• 2 p x（$1 \le p \le n, 0 \le x < 2^{32}$），表示你需要将位置 $p$ 处的数替换为给定的 $x$。

输出格式

对于每个第一类型的询问，输出一行，包含对应的答案。

样例

输入样例 1

5 5
571 342 228 152 192
1 1 5 409
2 1 414
1 1 2 100
2 4 341
1 2 5 315

输出样例 1

4294967103
4294966957
4294967103