Farmer John считает, что совершил прорыв: нашёл почти линейный алгоритм для 3SUM. Задача известна отсутствием решения, работающего существенно быстрее квадратичного времени. Одна формулировка: для массива целых $s_1,\dots,s_m$ посчитать неупорядоченные тройки различных индексов $i,j,k$, где $s_i+s_j+s_k=0$.

Для проверки Bessie даёт массив $A$ из $N$ целых ($1\leq N\leq5000$) и $Q$ запросов ($1\leq Q\leq10^5$) с двумя индексами $1\leq a_i\leq b_i\leq N$. Для каждого надо решить 3SUM на подмассиве $A[a_i\dots b_i]$.

Увы, FJ обнаружил ошибку. Он уверен, что исправит её, но пока просит помочь пройти тест Bessie!

Входные данные

Первая строка: целые $N,Q$ через пробел. Вторая: элементы $A_1,\dots,A_N$ через пробел. Следующие $Q$ строк: целые $a_i,b_i$ через пробел, запрос.

Для каждого элемента гарантируется $-10^6\leq A_i\leq10^6$.

Выходные данные

$Q$ строк, в строке $i$ одно целое — ответ на запрос $i$. Используйте 64-битные целые во избежание переполнения.

Примеры

Входные данные 1

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

Выходные данные 1

2
1
4

Примечание

Для первого запроса тройки: $(A_1,A_2,A_5)$ и $(A_2,A_3,A_4)$.

Подзадачи

• Тесты 2–4: $N\le500$.
• Тесты 5–7: $N\le2000$.
• Тесты 8–15: без дополнительных ограничений.

Автор задачи: Dhruv Rohatgi