Range Operations on Sequence

You are given a sequence of numbers. You need to perform three types of operations on a subrange of the sequence:

• Multiply every number in the range by a given value \(x\). (Operation 1)
• Add a given value \(x\) to every number in the range. (Operation 2)
• Query the sum of all numbers in the range. (Operation 3)

Note: The operations use a 1-indexed array.

For example, if the sequence is \( [a_1, a_2, \dots, a_n] \), then:

• Operation 1 on the interval \([l, r]\): \( a_i = a_i \times x \) for all \( l \le i \le r \).
• Operation 2 on the interval \([l, r]\): \( a_i = a_i + x \) for all \( l \le i \le r \).
• Operation 3 on the interval \([l, r]\): output \( \sum_{i=l}^{r} a_i \).

inputFormat

The first line contains two integers \( n \) and \( q \) representing the number of elements in the sequence and the number of operations, respectively.

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

Each of the following \( q \) lines describes an operation. The format for an operation is as follows:

• 1 l r x: Multiply every number in the subrange \([l, r]\) by \( x \).
• 2 l r x: Add \( x \) to every number in the subrange \([l, r]\).
• 3 l r: Output the sum of the subrange \([l, r]\).

All indices are 1-indexed.

outputFormat

For each query of type 3, output the sum of the numbers in the specified subrange on a new line.

sample

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

15
12
39