Cho dãy số nguyên không âm gồm ~N~ số: ~A_1, A_2, \dots, A_N~ và ~Q~ truy vấn, mỗi truy vấn gồm hai số nguyên dương ~L, R~ (~1 \le L \le R \le N~).

Yêu cầu: Với mỗi truy vấn, hãy đếm số bộ ba chỉ số ~i, j, k~ thỏa mãn đồng thời:

• ~L \le i < j < k \le R~.
• ~A_i + A_j + A_k~ là một số chẵn.

Input

• Dòng đầu chứa hai số nguyên dương ~N~ và ~Q~ (~N, Q \le 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \dots, A_N~ (~0 \le A_i \le 10^6~ với mọi ~i = 1 \dots N~).
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số ~L, R~ (~1 \le L \le R \le N~).

Output

• Ghi ra ~Q~ dòng là kết quả tương ứng của ~Q~ truy vấn.

Sample Input 1

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

Sample Output 1

1
2
10