Cho số nguyên dương \(N\) và dãy số nguyên \(a_1,a_2,…,a_N\).

Yêu cầu: Cho \(Q\) truy vấn, mỗi truy vấn cho hai số nguyên \(L, R\). Đếm số lượng bộ ba \((i,j,k)\) sao cho:

• \(L ≤ i < j < k ≤ R\)

• \(a_i+a_j+a_k = 0\)

Input

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

• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1,a_2,…,a_N (|a_i |≤10^6\)).

• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L, R (1 ≤ L ≤ R ≤ N\))

Output

Ghi trên \(Q\) dòng, dòng thứ \(i\) chứa một số nguyên - kết quả của truy vấn thứ \(i\).

Sample Input

7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7

Sample Output

2
1
4

Ràng buộc

• Subtask 1: N≤500.

• Subtask 2: N≤2000.

• Subtask 3: không có thêm ràng buộc nào.