Bạn được cho một dãy ~A~ chứa ~N~ số nguyên và ~Q~ truy vấn. Mỗi truy vấn được thể hiện bằng hai số nguyên ~L~ và ~R~. Với mỗi truy vấn, in ra số bộ ba ~(i~, ~j~, ~k)~ sao cho ~(L ≤ i < j < k ≤ R)~ và ~(A_i + A_j + A_k)~ là một số chẵn.

Input

• Đọc từ file BBTC.INP:

  • Dòng đầu tiên chứa số nguyên ~N~, ~Q~. ~(1 ≤ N~, ~Q ≤ 10^5)~

  • Dòng tiếp theo chứa ~N~ số nguyên, số nguyên thứ ~i~ có giá trị ~A_i~. ~(0 ≤ A_i ≤ 10^6)~

  • ~Q~ dòng tiếp theo mỗi dòng chứa ~2~ số nguyên ~L_i~, ~R_i~. ~(1 ≤ L_i ≤ R_i ≤ N)~

Output

• Ghi ra file BBTC.OUT gồm ~Q~ dòng, mỗi dòng sẽ chứa số lượng bộ ba được nói đến trong đề bài.

Sample Input

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

Sample Output

1
2
10

Giải thích

• Với truy vấn đầu tiên, ta sẽ chọn bộ ~(1~, ~2~, ~3)~ vì ~A_1 + A_2 + A_3 = 6~ là một số chẵn.

• Với truy vấn thứ hai, ta sẽ chọn ~2~ bộ: bộ ~(2~, ~3~, ~5)~ vì ~A_2 + A_3 + A_5 = 10~ là một số chẵn và bộ ~(3~, ~4~, ~5)~ vì ~A_3 + A_4 + A_5 = 12~ là một số chẵn.