Светлячку дан массив \(a\) длины \(n\). Пусть \(c_i\) обозначает \(i\)-й циклический сдвиг\(^{\text{∗}}\) массива \(a\). Она создает новый массив \(b\) так, что \(b = c_1 + c_2 + \dots + c_n\), где \(+\) представляет собой конкатенацию\(^{\text{†}}\).
Затем она задает вам \(q\) запросов. Для каждого запроса выведите сумму всех элементов в подмассиве \(b\), который начинается с \(l\)-го элемента и заканчивается \(r\)-м, включая оба конца.
Выходные данные
Для каждого запроса выведите ответ на новой строке.
Примечание
Для первого набора входных данных, \(b = [1, 2, 3, 2, 3, 1, 3, 1, 2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|