Farmer John crede di aver fatto una scoperta importante: un algoritmo quasi lineare per 3SUM, famoso perché non si conosce una soluzione sostanzialmente migliore del tempo quadratico. Una formulazione: dato l’array di interi $s_1,\dots,s_m$, contare triple non ordinate di indici distinti $i,j,k$ con $s_i+s_j+s_k=0$.

Per provarlo, Bessie dà un array $A$ di $N$ interi ($1\leq N\leq5000$) e $Q$ richieste ($1\leq Q\leq10^5$), ciascuna con $1\leq a_i\leq b_i\leq N$. Si deve risolvere 3SUM su ogni sottoarray $A[a_i\dots b_i]$.

Purtroppo FJ ha appena trovato un difetto. È sicuro di correggerlo, ma intanto chiede aiuto per superare il test di Bessie!

Input

Prima riga: interi $N,Q$ separati da spazi. Seconda: elementi $A_1,\dots,A_N$ separati da spazi. Le successive $Q$ righe hanno interi $a_i,b_i$ separati da spazi, una richiesta.

Ogni elemento soddisfa $-10^6\leq A_i\leq10^6$.

Output

$Q$ righe; la $i$ contiene un intero, risposta alla richiesta $i$. Usa interi a 64 bit per evitare overflow.

Esempi

Input 1

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

Output 1

2
1
4

Note

Le triple della prima richiesta sono $(A_1,A_2,A_5)$ e $(A_2,A_3,A_4)$.

Sottoproblemi

• Test 2–4: $N\le500$.
• Test 5–7: $N\le2000$.
• Test 8–15: nessun vincolo aggiuntivo.

Autore del problema: Dhruv Rohatgi