Great Party

Grammy joined a great party.

There is an interesting game at the party. There are $n$ piles of stones on the table. The $i$-th pile has $a_i$ stones. Two players take turns operating the stones.

On each turn, a player does the following two steps:

1. Select a non-empty pile and remove a positive number of stones from it.
2. Either keep the remaining stones in that pile, or merge all of them into another non-empty pile.

A player who cannot operate loses the game.

Grammy has $q$ questions. For each question, count the sub-segments of $[l, r]$ for which the first player wins when the piles in that sub-segment are played alone as a game.

The first line contains two integers $n$ and $q$ ($1 \leq n, q \leq 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^6$).

The $i$-th of the next $q$ lines contains two integers $l_i$ and $r_i$ ($1 \leq l_i \leq r_i \leq n$).

The output contains $q$ lines. Each line contains a single integer, the answer to the question.