Farmer John believes he has made a major breakthrough in algorithm design: he claims to have found a nearly linear time algorithm for the 3SUM problem, an algorithmic problem famous for the fact that no known solution exists running in substantially better than quadratic time. One formulation of the 3SUM problem is the following: given an array s1**,…,sms1,…,sm of integers, count the number of unordered triples of distinct indices i,j,ki,j,k such that si+sj**+sk**=0si+sj+sk=0.To test Farmer John's claim, Bessie has provided an array AA of NN integers (1≤N≤50001≤N≤5000). Bessie also asks QQ queries (1≤Q≤1051≤Q≤105), each of which consists of two indices 1≤ai≤bi≤N1≤ai≤bi≤N. For each query, Farmer John must solve the 3SUM problem on the subarray A[ai…bi**]A[ai…bi].

Unfortunately, Farmer John has just discovered a flaw in his algorithm. He is confident that he can fix the algorithm, but in the meantime, he asks that you help him pass Bessie's test!

SCORING:

• Test cases 2-4 satisfy N≤**500.**N≤500.
• Test cases 5-7 satisfy N≤**2000.**N≤2000.
• Test cases 8-15 satisfy no additional constraints.

INPUT FORMAT (file threesum.in):

The first line contains two space-separated integers NN and QQ. The second line contains the space-separated elements A1**,…,ANA1,…,AN of array AA. Each of the subsequent QQ lines contains two space-separated integers aiai and bibi, representing a query.It is guaranteed that −106≤Ai≤106**−106≤Ai≤106 for every array element AiAi.

OUTPUT FORMAT (file threesum.out):

The output should consist of QQ lines, with each line ii containing a single integer---the answer to the ii-th query. Note that you should use 64-bit integers to avoid overflow.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

2
1
4

For the first query, the possible triples are (A1,A2**,A5**)(A1,A2,A5) and (A2,A3**,A4**).