题目内容

塔塔拿到了一个长度为$n$的数组$a$，下标从$1$开始，$q$次询问($op,l,r$)。

$op=1$, 计算$a_l$ & $a_l+1$ | $a_l+2$& $a_l+3$| $a_l+4...a_r$, 的值。以&开始，交替 &|。

$op=2$，计算$a_l | a_l+1$ & $a_l+2$|$a_1+3$&$a_1+4...a_r$, 的值。以|开始，交替|&。

例如:询问 ($1,3,9$)，计算$a_3$&$a_4$|$a_5$&$a_6$|$a_7$&$a_8$|$a_9$。询问($2,3,9$)，计算$a_3$|$a_4$&$a_5$|$a_6$&$a_7$|$a_8$&$a_9$

本题的&和|不区分优先级，从左往右计算。

$a|b$表示$a$按位或$b$(按位或运算符“|”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的两个二进位有一个为1时，结果位就为1)。

$a$&$b$表示$a$按位与$b$(按位与运算符“&”是双目运算符。其功能是参与运算的两数各对应的二进位相与。只要对应的两个二进位两个都为$1$时，结果位就为$1$)。

输入描述

第一行包含两个整数$n\ q$($1≤n,q≤2×10^5$)，表示数组大小和询问个数。

第二行包含$n$个整数$a_i$($0≤a_i<2^{30}$),表示数组$a$。

接下来$q$行，每行包含三个整数$op\ l\ r$($1≤op≤2,1≤l≤r≤n$),表示询问。

输出描述

输出包含$q$行，每行包含一个整数，分别表示每次询问结果。

样例1

输入

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

输出

2
0

说明

$op=1,l=2,r=3$对应$2$&$3$，答案为$2$。 $op=2,l=2,r=4$对应$2|3$&$4$，答案为$0$。