Farmer John tin có đột phá: thuật toán gần tuyến tính cho 3SUM, nổi tiếng vì chưa có lời giải nhanh hơn đáng kể so với thời gian bậc hai. Một cách phát biểu: với mảng số nguyên $s_1,\dots,s_m$, đếm bộ ba chỉ số phân biệt $i,j,k$ không xét thứ tự sao cho $s_i+s_j+s_k=0$.

Bessie kiểm tra bằng mảng $A$ gồm $N$ số nguyên ($1\leq N\leq5000$) và $Q$ truy vấn ($1\leq Q\leq10^5$), mỗi truy vấn có $1\leq a_i\leq b_i\leq N$. Phải giải 3SUM trên mỗi mảng con $A[a_i\dots b_i]$.

Tiếc là FJ vừa phát hiện lỗi. Ông tin sửa được, nhưng trong lúc đó nhờ bạn giúp qua bài kiểm tra của Bessie!

Dữ liệu vào

Dòng đầu: số nguyên $N,Q$ cách nhau bởi dấu cách. Dòng hai: phần tử $A_1,\dots,A_N$ cách nhau bởi dấu cách. $Q$ dòng tiếp mỗi dòng có số nguyên $a_i,b_i$ cách nhau bởi dấu cách cho truy vấn.

Mọi phần tử thỏa $-10^6\leq A_i\leq10^6$.

Dữ liệu ra

$Q$ dòng; dòng $i$ chứa một số nguyên, đáp án truy vấn $i$. Dùng số nguyên 64 bit để tránh tràn.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2
1
4

Ghi chú

Các bộ ba ở truy vấn đầu là $(A_1,A_2,A_5)$ và $(A_2,A_3,A_4)$.

Nhiệm vụ con

• Test 2–4: $N\le500$.
• Test 5–7: $N\le2000$.
• Test 8–15: không thêm ràng buộc.

Tác giả bài toán: Dhruv Rohatgi