题目内容

监控系统记录了长度为 $n$ 的状态数组 $a$（下标从 1 开始）。运维人员会提出 $q$ 次查询，每次给出 $(op,l,r)$：当 $op=1$ 时，从 $a_l$ 起按 $\&$、$|$、$\&$、$|$、$\ldots$ 的顺序从左到右计算到 $a_r$；当 $op=2$ 时，从 $a_l$ 起按 $|$、$\&$、$|$、$\&$、$\ldots$ 的顺序从左到右计算到 $a_r$。本题中 $\&$ 与 $|$ 不区分优先级，一律从左到右求值。$x \& y$ 表示按位与，$x | y$ 表示按位或。

约束：$1 \le n,q \le 200000$，$0 \le a_i < 2^{30}$，$1 \le op \le 2$，$1 \le l \le r \le n$。

输入描述

第一行两个整数 $n$ 和 $q$，表示数组长度与查询次数。 第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$。 接下来 $q$ 行，每行三个整数 $op$、$l$、$r$，表示一次查询。