Maintaining a Sequence with Range Assignment, Sum and Undo Operations

You are given a sequence of length (n) where all elements are initially zero. You need to support three types of operations:

1. Range Assignment: For given integers (l, r, v), assign the value (v) to every element in the segment ([l, r]) (1-indexed). That is, for every (i) with (l \le i \le r), set (a_i = v).
   
   
2. Range Sum Query: For given (l, r), output the sum of the elements in the segment ([l, r]).
   
   
3. Undo Operation: For a given integer (k), undo the (k)-th range assignment operation (which has not been undone yet). Undoing an operation means that the history will behave as if that assignment operation never occurred, without affecting the order or the effect of other operations. For example, if operations (1, 2, 3, 4, 5) are performed sequentially and you undo operation 4, then the sequence becomes the same as if operations (1, 2, 3, 5) were executed. If you then undo operation 2, the sequence will become the same as if only operations (1, 3, 5) had been executed.
   
   A key note is that undo operations are applied permanently and affect all subsequent queries.

inputFormat

The first line contains two integers (n) and (m) ((1 \le n, m \le 1000)), representing the length of the sequence and the number of operations, respectively. Each of the following (m) lines represents an operation in one of the formats below:

• Range Assignment: 1 l r v
• Range Sum Query: 2 l r
• Undo Operation: 3 k

It is guaranteed that every undo operation corresponds to a valid, not-yet-undone assignment operation, and that (1 \le l \le r \le n).

outputFormat

For each range sum query (operation type 2), output the computed sum on a new line.

sample

5 5
1 1 3 5
2 2 4
1 2 5 2
3 3
2 1 5

10
15