Dima and the Time Machine
Mom gave Dima a time machine, but it only works with a special array of length n that's built into it. This machine can restore the array to its state at any given moment in time. The array isn't ordinary; it's quite unique. Dima can select three numbers - i, j, and d (1 ≤ i ≤ j ≤ n, -1000 ≤ d ≤ 1000) and magically add d to all elements of the array from index i to j. 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 answer these questions effortlessly, but can you?
Input
The first line contains two integers n and q (1 ≤ n, q ≤ 10^5), representing 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 ≤ a[i] ≤ 1000) - the initial state of the array. The following q lines describe operations and queries. Each line begins with either t, +, or ?. If a line starts with t, it indicates a time machine operation, followed by an integer i (1 ≤ i), which specifies the operation or query number to which the array should revert. i will always be less than or equal to the current operation number. If a line starts with +, it signifies an addition operation, followed by i, j, and d, adhering to the constraints mentioned. If a line starts with ?, it is a query, followed by the numbers f and t (1 ≤ f, t ≤ n).
Output
For each query, print the sum of the numbers in the array from index f to t, with each result on a new line.