Druid accumulates numbers very fast, once he had some numbers, and some queries, he asks you to play a game, the game goes as follows, given N numbers and Q queries; the fastest to answer all the Q queries wins the game. Druid challenges you to answer all the queries faster than him.

Can you beat Druid in his game?

Input

The first line contains 2 space separated integers N, Q (1 <= N, Q <= 10⁵), the second line contains N space separated integers (0 <= N_i < 2³¹), after that follows Q lines, the ith line contains 3 space separated integers T, A, and B, T (0 <= T <= 1) is the query type, A and B (1 <= A <=  B <= N) are indices (1-based).

Output

For each query, output one line contains the answer to the i-th query. If T is 0, then the answer should be the number of odd numbers between the 2 indices A and B inclusive, otherwise, the answer should be the number of even numbers between the 2 indices A and B inclusive.

Example

Input:
10 5
10 6 4 9 46 21 99 36 45 1
1 1 2
1 1 3
1 1 4
0 1 5
0 5 10

Output:
2
3
3
1
4