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

В этой задаче вместо легенды Настя попросила нас написать формальное условие.

Дан массив чисел $$$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}$$$.

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

В первой строке вводится целое число $$$n$$$ ($$$2 \leq n \leq 10^{5}$$$) — число элементов массива $$$a$$$.

Во второй строке вводятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^{9} \leq a_i \leq 10^{9}$$$) — элементы массива $$$a$$$.

В третьей строке вводится $$$n-1$$$ целое число $$$k_1, k_2, \ldots, k_{n-1}$$$ ($$$-10^{6} \leq k_i \leq 10^{6}$$$) — элементы массива $$$k$$$.

В четвертой строке вводится целое число $$$q$$$ ($$$1 \leq q \leq 10^{5}$$$) — количество запросов.

В следующих $$$q$$$ строках вводятся запросы одного из двух видов, по одному в строке:

  • если запрос первого типа, то вводится символ «+» (без кавычек), затем вводятся целые числа $$$i$$$ и $$$x$$$ ($$$1 \leq i \leq n$$$, $$$0 \leq x \leq 10^{6}$$$), что значит, что число $$$x$$$ добавляется к $$$i$$$-му элементу массива $$$a$$$, как описано в условии;
  • если запрос второго типа, то вводится символ «s» (без кавычек), затем вводятся два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$).
Выходные данные

Для каждого запроса второго типа в отдельной строке выведите одно целое число — сумму на соответствующем отрезке.

Примеры
Входные данные
3
1 2 3
1 -1
5
s 2 3
+ 1 2
s 1 2
+ 3 1
s 2 3
Выходные данные
5
7
8
Входные данные
3
3 6 7
3 1
3
+ 1 3
+ 2 4
s 1 3
Выходные данные
33
Примечание

В первом примере:

  • после первого изменения $$$a = [3, 4, 3]$$$;
  • после второго изменения $$$a = [3, 4, 4]$$$.

Во втором примере:

  • после первого изменения $$$a = [6, 9, 10]$$$;
  • после второго изменения $$$a = [6, 13, 14]$$$.