题目描述

Grammy 参加了一场热闹的晚会。会场角落里摆着一张长桌，桌上排成一行放着 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个石子。两名玩家轮流操作这些石子。

每名玩家在自己的回合中，需要依次完成下面两步：

1. 选择一堆非空石子，并从中取走正整数个石子；
2. 对这堆剩下的石子，可以让它们留在原处，也可以把它们全部合并到另一堆非空石子中。

无法进行操作的玩家输掉游戏。

晚会主持人给 Grammy 提出了 $q$ 个问题。对于每个询问 $[l,r]$，请统计有多少个连续子段完全位于 $[l,r]$ 内，并且如果只取出这个子段中的石堆进行上述游戏，先手玩家必胜。

输入格式

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

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，第 $i$ 行包含两个整数 $l_i,r_i$，表示一个询问区间。

输出格式

输出 $q$ 行。对于每个询问，输出一行一个整数，表示该询问的答案。

数据范围

• $1\le n,q\le 10^5$；
• $1\le a_i\le 10^6$；
• $1\le l_i\le r_i\le n$。

样例 1

输入

4 5
1 2 2 4
1 2
2 3
3 4
1 3
2 4

输出

3
2
3
5
5

样例 2

输入

4 5
5 6 7 8
1 2
2 3
3 4
1 3
2 4

输出

3
3
3
6
6