在这个任务中,Nastya 要求我们写一份正式的声明。
给出了长度为 $$$n$$$ 的数组 $$$a$$$ 和长度为 $$$n-1$$$ 的数组 $$$k$$$。应处理两种类型的查询:
- 将 $$$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$$$;
- 打印数组 $$$a$$$ 中从第 $$$l$$$ 个元素到第 $$$r$$$ 个元素的连续子数组的总和。
保证最初 $$$a_i + k_i \leq a_{i+1}$$$ 对于所有 $$$1 \leq i \leq n-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$$$)。
输出
对于第二种类型的每个查询,在新行中打印一个整数 - 相应子数组的总和。
示例
输入 #1
3 1 2 3 1 -1 5 s 2 3 + 1 2 s 1 2 + 3 1 s 2 3
输出 #1
5 7 8
输入 #2
3 3 6 7 3 1 3 + 1 3 + 2 4 s 1 3
输出 #2
33
注意
在第一个示例中:
- 第一次更改后 $$$a = [3, 4, 3]$$$;
- 第二次更改后 $$$a = [3, 4, 4]$$$。
在第二个示例中:
- 第一次更改后 $$$a = [6, 9, 10]$$$;
- 第二次更改后 $$$a = [6, 13, 14]$$$。