题目来自第 42 次 CSP 认证 T4，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 2.0 秒

空间限制： 256 MB

题目背景

小 C 和小 S 正在玩一种石子游戏，规则如下：

• 有 $m$ 个仓库，从左到右编号为 $1,2,\cdots,m$，$i$ 号仓库初始存有 $a_i$ 个石子。
• 两位玩家轮流操作，小 S 先手。每轮操作可任选一个仓库 $i$，从中取出任意大于 $0$ 数量的石子，将取出石子移至 $i−1$ 号仓库。特别地，若 $i=1$，取出的石子将直接被丢弃。
• 当全部仓库石子均被清空时游戏终止，此时无法进行操作的玩家判负。

聪明的小 C 发现他必胜的条件为：所有奇数编号仓库的石子数异或和为 $0$，即 $a_1 \oplus a_3 \oplus \cdots \oplus a_{2k - 1} = 0$，$m=2k - 1$ 或 $2k$，其中 $\oplus$ 表示二进制异或操作。

题目描述

给定 $n$ 个仓库，从左到右编号为 $1,2,\cdots,n$，$i$ 号仓库初始存有 $b_i$ 个石子。

定义子游戏 $\left(l,r\right)$：选取仓库 $l \sim r$ 进行上述石子游戏，将其视作一组新仓库，$i$ 号仓库初始石子数为 $a_i=b_{i+l-1}$。

共有 $q$ 个互相独立的询问，每个询问给出区间 $[L,R]$。小 C 需要把 $[L,R]$ 分割为若干个子区间 $[l_1,r_1], [l_2,r_2], \cdots, [l_k,r_k]$，满足 $l_1=L, r_k=R, r_i=l_{i+1}-1 \left(1 \le i < k \right)$，使得在 $k$ 个子游戏 $(l_1,r_1), (l_2,r_2), \cdots, (l_k,r_k)$ 中他必胜的子游戏数量尽可能地多。求所有合法分割方案里，小 C 必胜的子游戏数量的最大值。

输入格式

从标准输入读入数据。

第一行读入两个正整数 $n,q$，表示仓库数量和询问次数。

第二行读入 $n$ 个非负整数 $b_1,b_2,\cdots,b_n$，表示各仓库的石子个数。

接下来 $q$ 行，每行读入两个正整数 $L,R$，表示一个询问。题目保证 $1 \le L \le R \le n$。

输出格式

输出到标准输出。

输出 $q$ 行，每行一个整数，表示每组询问中小 C 能得到的必胜子游戏数量的最大值。

4 2
1 2 1 0
2 3
1 4

0
2

样例 1 解释

容易得知，只有子游戏 $\left(1,3\right), \left(1,4\right), \left(4,4\right)$ 是小 C 必胜的。

因此第一个询问 $\left(2,3\right)$ 中不存在一个区间满足小 C 必胜，答案为 $0$；

第二个询问 $\left(1,4\right)$ 可以分割为 $\left(1,3\right)$ 和 $\left(4,4\right)$，答案为 $2$。

子任务

保证对于所有测试点，均有 $1\le n,q\le 10^6,\ 0\le b_i<2^{31}$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

提示

本题输入输出量较大，请采用效率较高的输入输出方式。