Sequence Maintenance with Rollback and Reversed Updates

You are given a sequence \(A\) of \(n\) integers and you need to perform \(m\) operations on it. The operations are described below:

• 1 l r x: For every index \(i\) such that \(l \le i \le r\), perform \(A_i \leftarrow A_i + x\).
• 2 l r x: For every index \(i\) such that \(l \le i \le r\), perform \(A_i \leftarrow A_i \times x\).
• 3 l r: Output \(S \bmod 19260817\), where \(S = \sum_{i=l}^{r} A_i\).
• 4: Rollback the sequence \(A\) to the state before the last 4 operation (or to the initial state if no such operation exists). Then, re-execute all the update operations (of types 1 and 2) that were performed after that checkpoint, but in reversed order. (See the sample explanation for details.)

In other words, maintain a checkpoint state of the sequence. For each update (operations of type 1 or 2) after the checkpoint, record it. When a rollback is requested via operation 4, first revert \(A\) to the checkpoint state, then apply all recorded updates in reverse order (without recording them), update the checkpoint to the new state, and clear the recorded update history.

Note that the indices are 1-indexed.

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space.

The second line contains \(n\) integers representing the initial array \(A\).

The following \(m\) lines each contain an operation in one of the following formats:

• 1 l r x
• 2 l r x
• 3 l r
• 4

outputFormat

For each operation of type 3, output a single line containing the value \(S \bmod 19260817\), where \(S\) is the sum of elements between indices \(l\) and \(r\) in the current array \(A\).

sample

2 4
10 20
1 1 2 5
3 1 1
4
3 2 2

15
25