Great Party

그램미(Grammy)가 멋진 파티에 참석했다.

파티에서 흥미로운 게임이 진행된다. 테이블 위에 돌 더미 $n$개가 있고, $i$번째 더미에는 돌이 $a_i$개 있다. 두 명의 플레이어가 번갈아 가며 돌을 조작한다.

플레이어는 자기 차례에 다음 두 단계를 수행한다.

1. 비어 있지 않은 더미 하나를 골라, 그 더미에서 양의 개수만큼 돌을 제거한다.
2. 남은 돌을 그 더미에 그대로 두거나, 남은 돌을 모두 비어 있지 않은 다른 더미에 합친다.

조작할 수 없는 플레이어가 게임에서 진다.

그램미는 질문 $q$개를 준비했다. 각 질문마다 구간 $[l, r]$의 부분 구간 중에서, 그 부분 구간에 있는 더미만 떼어 내어 게임을 한다고 할 때 첫 번째 플레이어가 이기는 부분 구간의 개수를 구하시오.

첫 줄에 두 정수 $n$과 $q$가 주어진다 ($1 \leq n, q \leq 10^5$).

둘째 줄에 정수 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \leq a_i \leq 10^6$).

다음 $q$개의 줄에는 각각 두 정수 $l_i$와 $r_i$가 주어진다 ($1 \leq l_i \leq r_i \leq n$).

$q$개의 줄을 출력한다. 각 줄에는 질문에 대한 답을 나타내는 정수 하나를 출력한다.