题目描述

薯条哥拿到了一个长度为$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\le n,q\le 2×10^5)$，表示数组大小和询问个数。

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

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

输出描述

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

样例

输入

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$。