题目描述

给你 $n$ 个数 $a_1,a_2,...,a_n$ 。

有 $q$ 次询问,每次询问在 $a_l,$ $a[l+1],$ $...,$ $a_r$ 里选一个子集,选出来的子集的最大的异或和是多少。


输入格式

第一行两个整数表示$n,q(n,q \le q \le 2 \times 10^5)$。

接下来$n$个整数$a_1,a_2,...,a_n(0\le q \le a_i \lt2^{60})$。

接下来q行,每行两个整数$l,r(1 \le l \le r \le n)$。


输出格式

$q$行,每行一个整数,表示答案


样例数据

输入

5 15
1 7 8 2 4
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5

输出

1
7
15
15
15
7
15
15
15
8
10
14
2
6
4

备注


操作

评测记录

优秀代码

信息

时间限制: 1s
内存限制: 256MB
评测模式: Normal

题解