Time-Dependent Sequence Queries

Fusu loves to listen to ancient style songs while writing challenging block problems. In this problem, you are given a sequence where each element is associated with three parameters: \(v_i, a_i, b_i\). The sequence has a magical time-dependent property: every time unit, the value \(v_i\) of the \(i\)-th element increases by \(a_i \times b_i\) (i.e., \(v_i = v_i + a_i \times b_i\)).

You will be given a series of operations that occur at various time moments. Initially, the time is \(0\). An operation at time \(t\) is processed as follows:

• Before performing any operation at time \(t\), update every element in the sequence: for each \(i\), add \((t - t_0) \times (a_i \times b_i)\) to \(v_i\), where \(t_0\) is the time of the previous operation (or \(0\) if none exists).
• Then, execute the operation.

There are four types of operations:

1. Query: 1 t l r — At time \(t\), query the sum of \(v_i\) for all indices \(i\) in the interval \([l, r]\).
2. Modify \(a\): 2 t l r x — At time \(t\), add an integer \(x\) to every \(a_i\) in the interval \([l, r]\).
3. Modify \(b\): 3 t l r y — At time \(t\), add an integer \(y\) to every \(b_i\) in the interval \([l, r]\).
4. Modify \(v\): 4 t l r z — At time \(t\), add an integer \(z\) to every \(v_i\) in the interval \([l, r]\).

Note that indices are 1-indexed. Your task is to simulate these operations and output the answer to each query.

inputFormat

The input begins with two integers \(n\) and \(q\), separated by spaces, where \(n\) is the length of the sequence and \(q\) is the number of operations.

The second line contains \(3n\) integers: \(v_1\, a_1\, b_1\, v_2\, a_2\, b_2\, ..., v_n\, a_n\, b_n\), which represent the initial values for each element.

Each of the next \(q\) lines describes an operation in one of the following formats:

• 1 t l r: Query the sum of \(v_i\) for \(i \in [l, r]\) at time \(t\).
• 2 t l r x: For each \(i \in [l, r]\), add \(x\) to \(a_i\) at time \(t\).
• 3 t l r y: For each \(i \in [l, r]\), add \(y\) to \(b_i\) at time \(t\).
• 4 t l r z: For each \(i \in [l, r]\), add \(z\) to \(v_i\) at time \(t\).

Before each operation at time \(t\), update every element \(i\) with the formula:

[ v_i = v_i + (t - t_0) \times (a_i \times b_i),, ]

where \(t_0\) is the time at which the previous operation occurred (or \(0\) initially). All indices are 1-indexed.

outputFormat

For each query (operation type 1), output a single line containing the sum of \(v_i\) over the queried interval, after processing the time updates and the operation.

sample

5 5
1 2 3 2 1 1 3 0 2 4 2 0 5 1 1
1 1 1 5
2 2 2 4 1
3 3 1 3 2
4 5 3 5 3
1 6 1 3

23
93

</p>