Dima and the Time Machine

Mom gave Dima a time machine. However, this machine only functions with a built-in array of length (n). It can revert the array to its state at any specified moment in time. This array is not ordinary; it's special. Dima can select two numbers — (i) and (d) ((1 $\le$ i $\le$ j $\le$ n), (-1000 $\le$ d $\le$ 1000)) — and magically add (d) to the element at index (i) in the array. As Dima experiments with his array, his mom occasionally asks him questions about the sum of the numbers in the array from index (f) to (t). Dima can easily answer these questions, but can you?

Input

The first line contains two integers (n) and (q) ((1 $\le$ n, q $\le$ 10^5)) — the number of elements in the array and the total number of operations and queries, respectively. The next line contains (n) integers (a_1, a_2, ..., a_n) ((-1000 $\le$ a_i $\le$ 1000)) — representing the initial state of the array. The following (q) lines describe operations and queries. Each line begins with a character: (t), (+), or (?). If the line starts with (t), it indicates a time machine operation, followed by a number (i) ((1 $\le$ i)) — the operation or query number to which the array should revert. (i) is always less than or equal to the current operation number. If the line starts with (+), it signifies an addition operation, followed by (i) and (d), adhering to the constraints mentioned. If the line starts with (?), it is a query, followed by numbers (f) and (t) ((1 $\le$ f, t $\le$ n)).

Output

For each query, output the sum of the numbers in the array from indices (f) to (t), with each result on a new line.

Examples