Range Operations and Operation Reversal

In ancient times, there was a sequence of length \( n \), initially filled with zeros. \( m \) operations are executed on this sequence. Each operation can be one of the following:

• Range addition: add an integer \( x \) to every element in the interval \( [l, r] \).
• Range multiplication: multiply every element in the interval \( [l, r] \) by an integer \( x \).

After some operations, there might be a query for the value of a specific element, and sometimes it is discovered that one of the previous modification operations was a mistake. In that case, an undo operation is performed to cancel the effect of the \( k \)-th modification operation (where \( k \) is 1-indexed among the modification operations). Note that the order of the remaining operations is preserved.

Note: All input data is randomly generated.

inputFormat

The first line contains two integers \( n \) and \( m \) \( (1 \leq n, m \leq 10^5) \), representing the length of the sequence and the number of operations.

Each of the next \( m \) lines contains an operation in one of the following formats:

• 1 l r x — Add integer \( x \) to every element in the range \( [l, r] \) (indices are 1-indexed).
• 2 l r x — Multiply every element in the range \( [l, r] \) by integer \( x \).
• 3 i — Query: output the current value of the element at index \( i \).
• 4 k — Undo the \( k \)-th modification operation (i.e. an operation of type 1 or 2). The undo command will cancel that operation for all subsequent queries.

outputFormat

For each query operation (type 3), output the value at the corresponding index on a separate line.

sample

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

6
0