E. Nastya Hasn't Written a Legend
binary search; data structures
In this task, Nastya asked us to write a formal statement.An array \(a\) of length \(n\) and an array \(k\) of length \(n-1\) are given. Two types of queries should be processed: increase \(a_i\) by \(x\). Then if \(a_{i+1} < a_i + k_i\), \(a_{i+1}\) becomes exactly \(a_i + k_i\); again, if \(a_{i+2} < a_{i+1} + k_{i+1}\), \(a_{i+2}\) becomes exactly \(a_{i+1} + k_{i+1}\), and so far for \(a_{i+3}\), ..., \(a_n\); print the sum of the contiguous subarray from the \(l\)-th element to the \(r\)-th element of the array \(a\). It's guaranteed that initially \(a_i + k_i \leq a_{i+1}\) for all \(1 \leq i \leq n-1\).
The first line contains a single integer \(n\) (\(2 \leq n \leq 10^{5}\)) — the number of elements in the array \(a\).The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(-10^{9} \leq a_i \leq 10^{9}\)) — the elements of the array \(a\).The third line contains \(n-1\) integers \(k_1, k_2, \ldots, k_{n-1}\) (\(-10^{6} \leq k_i \leq 10^{6}\)) — the elements of the array \(k\).The fourth line contains a single integer \(q\) (\(1 \leq q \leq 10^{5}\)) — the number of queries.Each of the following \(q\) lines contains a query of one of two types: if the query has the first type, the corresponding line contains the character '+' (without quotes), and then there are two integers \(i\) and \(x\) (\(1 \leq i \leq n\), \(0 \leq x \leq 10^{6}\)), it means that integer \(x\) is added to the \(i\)-th element of the array \(a\) as described in the statement. if the query has the second type, the corresponding line contains the character 's' (without quotes) and then there are two integers \(l\) and \(r\) (\(1 \leq l \leq r \leq n\)).
For each query of the second type print a single integer in a new line — the sum of the corresponding subarray.
In the first example: after the first change \(a = [3, 4, 3]\); after the second change \(a = [3, 4, 4]\). In the second example: after the first change \(a = [6, 9, 10]\); after the second change \(a = [6, 13, 14]\).