Grammy 参加了一个盛大的派对。

派对上有一个有趣的游戏。桌上有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个石子。两名玩家参与游戏，轮流进行操作。

在每一轮中，玩家需要执行以下两个步骤：

1. 选择一个非空的石子堆，从中移除正整数个石子。
2. 将剩余的石子留在原堆中，或者将它们全部合并到另一个非空的石子堆中。

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

现在，Grammy 提出了 $q$ 个问题。对于每个问题，她想知道有多少个子区间 $[l, r]$ 满足：如果仅取出该区间内的石子堆进行游戏，先手玩家必胜。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$)。

接下来的 $q$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le n$)。

输出格式

输出包含 $q$ 行。每行包含一个整数，表示对应问题的答案。

样例

样例输入 1

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

样例输出 1

3
2
3
5
5

样例输入 2

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

样例输出 2

3
3
3
6
6