Акустический инженер записал последовательность мгновенных амплитуд сигнала a_1, a_2, ..., a_n.

Для анализа он рассматривает временные окна. Мощность сигнала на окне от l до r определяется как сумма квадратов амплитуд на этом отрезке:

a_l^2 + a_{l+1}^2 + ... + a_r^2

Требуется обработать q запросов. В каждом запросе заданы границы окна l и r, и для него нужно вывести суммарную мощность сигнала на этом отрезке.

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

Первая строка содержит два целых числа n и q — количество измерений амплитуды и количество запросов.

Вторая строка содержит n целых чисел a_i — значения амплитуд.

В следующих q строках содержится по два целых числа l и r — границы временного окна.

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

Для каждого запроса выведите в отдельной строке одно целое число — сумму квадратов амплитуд на отрезке [l, r].

Ограничения

• 1 <= n, q <= 2 * 10^5
• -10^4 <= a_i <= 10^4
• 1 <= l <= r <= n

Примеры

Пример 1

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

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

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

0
10
2
8
1

Пример 2

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

6 6
-10000 10000 -9999 9999 0 7
1 6
1 2
2 5
5 6
6 6
3 4

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

399960051
200000000
299960002
49
49
199960002