F. Запросы Светлячка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Светлячку дан массив $$$a$$$ длины $$$n$$$. Пусть $$$c_i$$$ обозначает $$$i$$$-й циклический сдвиг$$$^{\text{∗}}$$$ массива $$$a$$$. Она создает новый массив $$$b$$$ так, что $$$b = c_1 + c_2 + \dots + c_n$$$, где $$$+$$$ представляет собой конкатенацию$$$^{\text{†}}$$$.

Затем она задает вам $$$q$$$ запросов. Для каждого запроса выведите сумму всех элементов в подмассиве $$$b$$$, который начинается с $$$l$$$-го элемента и заканчивается $$$r$$$-м, включая оба конца.

$$$^{\text{∗}}$$$Циклический сдвиг $$$x$$$-й ($$$1 \leq x \leq n$$$) массива $$$a$$$ равен $$$a_x, a_{x+1} \ldots a_n, a_1, a_2 \ldots a_{x - 1}$$$. Обратите внимание, что $$$1$$$-й сдвиг — это исходный массив $$$a$$$.

$$$^{\text{†}}$$$Конкатенация двух массивов $$$p$$$ и $$$q$$$ длины $$$n$$$ (другими словами, $$$p + q$$$) равна $$$p_1, p_2, ..., p_n, q_1, q_2, ..., q_n$$$.

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

Первая строка содержит $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$) — длина массива и количество запросов.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, ..., a_n$$$ ($$$1 \leq a_i \leq 10^6$$$).

Следующие $$$q$$$ строк содержат два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n^2$$$) — левую и правую границы запроса.

Обратите внимание, что большие входные данные могут потребовать использования 64-битных целых чисел.

Гарантируется, что сумма $$$n$$$ не превышает $$$2 \cdot 10^5$$$, а сумма $$$q$$$ не превышает $$$2 \cdot 10^5$$$.

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

Для каждого запроса выведите ответ на новой строке.

Пример
Входные данные
5
3 3
1 2 3
1 9
3 5
8 8
5 5
4 8 3 2 4
1 14
3 7
7 10
2 11
1 25
1 1
6
1 1
5 7
3 1 6 10 4
3 21
6 17
2 2
1 5
1 14
9 15
12 13
5 3
4 9 10 10 1
20 25
3 11
20 22
Выходные данные
18
8
1
55
20
13
41
105
6
96
62
1
24
71
31
14
44
65
15
Примечание

Для первого набора входных данных, $$$b = [1, 2, 3, 2, 3, 1, 3, 1, 2]$$$.