25655번 - 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 in it. Two players participate in the game and operate the stones in turn.

In each player's turn, the player will do the following two steps:

1. Select a non-empty pile of stones, select a positive amount of stones to remove from it.
2. Keep the remaining stones in the pile still or merge them all into another non-empty pile of stones.

Those who cannot operate lose the game.

Now, Grammy has $q$ questions. For each question, she asks you how many sub-segments of $[l,r]$ satisfy that if the piles in the segment are taken out alone for the game, the first player will win.

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, denoting the answer to the question.