Bài toán 3-SUM được phát biểu đơn giản như sau: cho dãy số nguyên \(s_1\), \(s_2\),..., \(s_m\), hãy đếm số bộ ba chỉ số \(i<j<k\) sao cho \(s_i+s_j+s_k=0\).

Bạn hãy viết chương trình đọc vào mảng \(A\) gồm \(N\) số nguyên và \(Q\) truy vấn. Truy vấn thứ \(i\) cho biết hai chỉ số \(l_i\), \(r_i\) \((1\leq l_i\leq r_i\leq N)\) và bạn phải giải quyết bài toán 3-SUM trên đoạn con \(A[l_i...r_i]\).

Input

Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1\leq N\leq 5000\), \(1\leq Q\leq 10^5\)).

Dòng tiếp theo chứa \(N\) số nguyên \(A_1\), \(A_2\),..., \(A_N\) \((-10^6\leq A_i\leq 10^6)\).

Dòng thứ \(i\) trong \(Q\) dòng tiếp chứa hai số nguyên dương \(l_i\) và \(r_i\).

Output

In ra \(Q\) dòng, mỗi dòng chứa một số nguyên là câu trả lời cho câu hỏi tương ứng.

Ví dụ

Sample input

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

Sample output

2
1
4

Giải thích

Với truy vấn đầu tiên, hai bộ số thỏa mãn là \((A_1, A_2, A_5)\) và \((A_2, A_3, A_4)\).