Cho dãy số nguyên không âm gồm N số: A1, A2, ..AN và Q truy vấn, mỗi truy vấn gồm hai số nguyên dương L, R (1 ≤ L ≤ R ≤ 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 ≤ i < j < k ≤ R.
• Ai + Aj + Ak là một số chẵn.

Dữ liệu: gồm:

• Dòng đầu chứa hai số nguyên dương N và Q (N, Q ≤ 10^5);
• Dòng thứ hai chứa N số nguyên A1, A2, ..AN (0 ≤ Ai ≤ 10^6 với mọi i = 1..N);
• Q dòng tiếp theo, mỗi dòng chứa hai số L, R mô tả một truy vấn (1 ≤ L ≤ R ≤ N).

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

INPUT

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

OUTPUT

1
2
10