Farmer John cree haber logrado un gran avance: un algoritmo casi lineal para 3SUM, famoso por no tener solución conocida sustancialmente mejor que el tiempo cuadrático. Una formulación: dado el arreglo entero $s_1,\dots,s_m$, contar ternas no ordenadas de índices distintos $i,j,k$ con $s_i+s_j+s_k=0$.

Para probarlo, Bessie da un arreglo $A$ de $N$ enteros ($1\leq N\leq5000$) y $Q$ consultas ($1\leq Q\leq10^5$), cada una con $1\leq a_i\leq b_i\leq N$. Hay que resolver 3SUM en cada subarreglo $A[a_i\dots b_i]$.

Por desgracia, FJ acaba de descubrir un fallo. Confía en arreglarlo, pero mientras tanto te pide ayuda para pasar la prueba de Bessie.

Entrada

Primera línea: enteros $N,Q$ separados por espacios. Segunda: elementos $A_1,\dots,A_N$ separados por espacios. Las siguientes $Q$ líneas tienen enteros $a_i,b_i$ separados por espacios, una consulta.

Cada elemento cumple $-10^6\leq A_i\leq10^6$.

Salida

$Q$ líneas; la $i$ contiene un entero, respuesta a la consulta $i$. Usa enteros de 64 bits para evitar desbordamiento.

Ejemplos

Entrada 1

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

Salida 1

2
1
4

Nota

Las ternas de la primera consulta son $(A_1,A_2,A_5)$ y $(A_2,A_3,A_4)$.

Subtareas

• Casos 2–4: $N\le500$.
• Casos 5–7: $N\le2000$.
• Casos 8–15: sin restricciones adicionales.

Autor del problema: Dhruv Rohatgi