版权声明

本题版权归 CTFPC 出题组 所有。

题目背景

摇啊摇十五摇过春分就是外婆桥

盼啊盼阿嬷阿嬷地甜甜叫

吵啊吵米花糖挂嘴角总是吃不饱

美啊美小脚桥上翘啊翘

——任然《外婆桥》

题目描述

2lf 中秋节要回老家，途中看到了小时候的外婆桥。泥路总是崎岖不平，邻居家的王二狗已经死了，2lf 感慨，时间变换得真快啊。

外婆桥是精心布置过的，小桥有 $n$ 段，每段有一个正整数拱高 $h_i$。

定义外婆桥一段的美观度 $f(l,r)$：

$$f(l,r)=h_l\ \mathrm{or}\ h_{l+1}\ \mathrm{or}\ h_{l+2}\ \ldots\ \mathrm{or}\ h_r$$

在织布的外婆用几经沧桑的手，对我笑着，搭在我手上，“小 2，你去求一下 $(l,r)$ 区间的美观度”。

输入格式

第一行两个正整数 $n,q$。

第二行 $n$ 个整数，表示 $h_i$。

第三行到第 $q+2$ 行，每行两个整数 $l,r$。

输出格式

$q$ 行，每行 $1$ 个整数，表示结果。

样例

6 5
10 12 1 2 4 0
1 6
2 6
1 5
2 5
1 4
6 6

15
15
15
15
15

说明/提示

Subtask	$n \le$	$q \le$	特殊性质	分值	依赖子任务
0	$6$	$5$	是样例	0	-
1	$100$		$h_1, h_2, \ldots, h_n$ 中有且仅有一项大于 $0$	10
2		$3$	无	20
3	$10^4$	$10$	$h_1 = h_2 = \ldots = h_n$	10
4			无	20	0 - 3
5	$5 \times 10^5$			40	0 - 4

对于 $100\%$ 的数据，$1 \le n, q \le 5 \times 10^5$，$0 \le h_i \le 2^{63} - 1$，$1 \le l \le r \le n$。