Cho một dãy số gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ và ~q~ truy vấn gồm hai số ~l~ và ~r~ thỏa mãn điều kiện ~1 \le l \le r \le n~. Với mỗi truy vấn, chọn ra bộ ba số ~(a_i, a_j, a_k)~ thỏa mãn điều kiện ~l \le i < j < k \le r~. Bộ ba số ~(a_i, a_j, a_k)~ này được gọi là đẹp nếu ~a_i = -(a_j + a_k)~.

Yêu cầu: Tìm số lượng bộ ba số đẹp tương ứng với mỗi truy vấn trên.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, q~ ~(1 \le n \le 5000; 1 \le q \le 10^5)~, trong đó ~n~ là số lượng phần tử trong dãy số, ~q~ là số lượng các truy vấn;

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(|a_i| \le 10^6; 1 \le i \le n)~;

• ~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~l, r~ ~(1 \le l \le r \le n)~;

• Các số trên mỗi dòng cách nhau bởi dấu cách.

Output

• Gồm ~q~ dòng, mỗi dòng là câu trả lời tương ứng với mỗi truy vấn.

Scoring

Sample Input 1

8 2
1 2 3 0 -2 -3 7 8
1 5
1 8

Sample Output 1

1
3

Notes

Có ~3~ bộ số đẹp tương ứng với truy vấn ~1~ ~8~ là: ~(1, 2, -3)~, ~(2, 0, -2)~, ~(3, 0, -3)~.