Migrated from Lutece 3252 嘴大疑惑盒

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定序列 $\{a_n\}$，$Q$ 次询问。每次给定 $L,R$，求

$\max_{S\subseteq [L,R]} \{\oplus_{i\in S}\ a_i\}$

$\oplus$ 表示异或。

Input

第一行，两个整数，分别为 $n$ 和 $Q$。

第二行，$n$ 个正整数，描述序列 $\{a_n\}$ ，下标从 $1$ 开始。

接下 $Q$ 行，每行两个数，表示 $L$ 和 $R$。

Output

共 $Q$ 行，每行一个整数，表示答案。

Samples

5 5
6 1 4 9 11 
1 4
2 3
3 4
3 5
2 5

15
5
13
15
15

Constraints

$1\leq n,Q\leq 10^5$ ，$1\leq a_i < 2^{20}$，$1\leq L\leq R\leq n$

Resources

2024 UESTC ICPC Training for Math