Farmer John croit avoir fait une percée : un algorithme presque linéaire pour 3SUM, problème célèbre pour n’avoir aucune solution connue sensiblement plus rapide que le temps quadratique. Une formulation : dans un tableau d’entiers $s_1,\dots,s_m$, compter les triplets non ordonnés d’indices distincts $i,j,k$ tels que $s_i+s_j+s_k=0$.

Pour vérifier, Bessie fournit un tableau $A$ de $N$ entiers ($1\leq N\leq5000$) et $Q$ requêtes ($1\leq Q\leq10^5$), chacune avec $1\leq a_i\leq b_i\leq N$. Il faut résoudre 3SUM sur chaque sous-tableau $A[a_i\dots b_i]$.

Hélas, FJ vient de trouver un défaut. Il pense pouvoir le corriger, mais demande entre-temps votre aide pour réussir le test de Bessie !

Entrée

Première ligne : entiers $N,Q$ séparés par des espaces. Deuxième : éléments $A_1,\dots,A_N$ séparés par des espaces. Les $Q$ lignes suivantes ont les entiers $a_i,b_i$ séparés par des espaces pour une requête.

Chaque élément vérifie $-10^6\leq A_i\leq10^6$.

Sortie

$Q$ lignes, avec à la ligne $i$ un entier répondant à la requête $i$. Utilisez des entiers sur 64 bits pour éviter les débordements.

Exemples

Entrée 1

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

Sortie 1

2
1
4

Remarque

Les triplets de la première requête sont $(A_1,A_2,A_5)$ et $(A_2,A_3,A_4)$.

Sous-tâches

• Tests 2–4 : $N\le500$.
• Tests 5–7 : $N\le2000$.
• Tests 8–15 : aucune contrainte supplémentaire.

Auteur du problème : Dhruv Rohatgi