Farmer John wierzy w przełom: niemal liniowy algorytm dla 3SUM, słynnego z braku znanego rozwiązania istotnie lepszego od czasu kwadratowego. Jedna wersja: dla tablicy całkowitej $s_1,\dots,s_m$ policzyć nieuporządkowane trójki różnych indeksów $i,j,k$ z $s_i+s_j+s_k=0$.

Bessie sprawdza to, dając tablicę $A$ z $N$ liczbami całkowitymi ($1\leq N\leq5000$) i $Q$ zapytań ($1\leq Q\leq10^5$), każde z $1\leq a_i\leq b_i\leq N$. Trzeba rozwiązać 3SUM dla każdej podtablicy $A[a_i\dots b_i]$.

Niestety FJ znalazł błąd. Wierzy, że go naprawi, ale na razie prosi o pomoc w teście Bessie!

Wejście

Pierwszy wiersz: całkowite $N,Q$ oddzielone spacjami. Drugi: elementy $A_1,\dots,A_N$ oddzielone spacjami. Kolejne $Q$ wierszy mają całkowite $a_i,b_i$ oddzielone spacjami, zapytanie.

Każdy element spełnia $-10^6\leq A_i\leq10^6$.

Wyjście

$Q$ wierszy; wiersz $i$ zawiera jedną liczbę całkowitą, odpowiedź na zapytanie $i$. Użyj 64-bitowych liczb całkowitych, by uniknąć przepełnienia.

Przykład

Wejście 1

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

Wyjście 1

2
1
4

Uwagi

Trójki w pierwszym zapytaniu to $(A_1,A_2,A_5)$ i $(A_2,A_3,A_4)$.

Podzadania

• Testy 2–4: $N\le500$.
• Testy 5–7: $N\le2000$.
• Testy 8–15: bez dodatkowych ograniczeń.

Autor zadania: Dhruv Rohatgi