版权声明

本题版权归 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

说明/提示

测试点编号	$n \le$	$q \le$	特殊性质
$1$	$10^3$	$5$	$h_1 \sim h_n$ 中只有一项非 $0$
$2 \sim 3$			无
$4$	$10^4$	$10$	$h_1=h_2=\ldots=h_n$
$5 \sim 6$			无
$7 \sim 10$	$5 \times 10^5$