A3143 | 狒狒食肆

时间限制:1000ms

空间限制:128mb

$Yuilice$正在游玩一款名为$FF14$的游戏，在这款游戏当中，有一个大$BOSS$佐迪亚克，为了打败他,$Yuilice$需要在古代人世界当中搜索十四人委员会留下来的徽章，最后合成阿谢姆徽章打败佐迪亚克。

现在已知共有$n$个徽章，每个徽章都有着一定的力量，他们的力量值分别为$a_1,a_2,a_3..\dots a_n$，这些力量之间可能会有一些微妙的冲突，若$a_i$与$a_j(i \neq j)$进行合并，那么他们会按照下面的规则进行合并力量。

- 首先我们会将$a_i$与$a_j$转换为二进制形式进行比较
- 若$a_i$的最后一位1与$a_j$的最后一位1处于相同位数上，那么力量总和为$a_i | a_j$。
- 若$a_i$的最后一位1与$a_j$的最后一位1不处于相同位数上，那么力量总和为两者当中最低位1的数字。

例: 若数字5与7进行合并，那么他们会进行5 | 7 = 7的运算，若12与32进行合并，那么他们会保留两者当中最低位的1，即为4。

现在$Yuilice$会给出$q$个搜索计划，每次计划都会提出一个区间$[L,R]$，即为将$a_L,a_{L+1} \dots a_R$，面对每个区间，你需要寻找区间当中所有数合并出来的最大值$MX$与最小值$Mi$并且输出。

输入第一行为两个正整数$n,q(1 \leq n \leq 10^2,1 \leq q \leq 10^3)$ - 代表共有$n$个徽章的力量值与$q$次提问

随后一行，共输入$n$个正整数$a_i(1 \leq a_i \leq 2^{31} - 1)$,代表每个徽章的力量值。

随后$q$行，每行给出一对整数$l_i,r_i$，代表当前要查阅的区间。

针对于每一次询问，输出一个整数$x$ - 代表区间的力量总值