В этой задаче вместо легенды Настя попросила нас написать формальное условие.
Дан массив чисел \(a\) длины \(n\) и массив чисел \(k\) длины \(n-1\). Нужно обрабатывать два типа запросов:
- увеличить \(a_i\) на \(x\). После этого, если \(a_{i+1} < a_i + k_i\), то \(a_{i+1}\) становится равно \(a_i + k_i\), затем, если \(a_{i+2} < a_{i+1} + k_{i+1}\), то \(a_{i+2}\) становится равно \(a_{i+1} + k_{i+1}\), затем то же самое происходит для \(a_{i+3}\), ..., \(a_n\);
- вывести сумму чисел на отрезке c \(l\) по \(r\) в массиве \(a\).
Гарантируется, что изначально для любого \(1 \leq i \leq n-1\) верно, что \(a_i + k_i \leq a_{i+1}\).
Выходные данные
Для каждого запроса второго типа в отдельной строке выведите одно целое число — сумму на соответствующем отрезке.
Примечание
В первом примере:
- после первого изменения \(a = [3, 4, 3]\);
- после второго изменения \(a = [3, 4, 4]\).
Во втором примере:
- после первого изменения \(a = [6, 9, 10]\);
- после второго изменения \(a = [6, 13, 14]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
1 -1
5
s 2 3
+ 1 2
s 1 2
+ 3 1
s 2 3
|
5
7
8
|
|
2
|
3
3 6 7
3 1
3
+ 1 3
+ 2 4
s 1 3
|
33
|