Range Add and Range Sum

N numbers sit in a row. Two kinds of operations arrive in order. One adds the same value to every number in a range. The other reports the sum of the numbers in a range.

Take the sequence 1, 2, 3, 4, 5. Adding 6 to the 3rd through the 4th number gives 1, 2, 9, 10, 5, and the sum of the 2nd through the 5th number is 26. Adding -2 to the 1st through the 3rd number then gives -1, 0, 7, 10, 5, and the sum of the 2nd through the 5th number is 22.

Process the operations in the order they are given and print the value of every sum operation.

The first line contains the count of numbers N (1 ≤ N ≤ 1,000,000), the number of update operations M (1 ≤ M ≤ 10,000), and the number of range sum operations K (1 ≤ K ≤ 10,000), separated by spaces.

Each of the next N lines contains one value of the sequence, in order.

Each of the following M+K lines contains one operation. A line of the form 1 b c d adds d to every number from the bth through the cth. A line of the form 2 b c asks for the sum of the numbers from the bth through the cth. Both forms satisfy 1 ≤ b ≤ c ≤ N.

Every number given in the input is an integer between $-2^{63}$ and $2^{63}-1$, inclusive.

For each sum operation, print the sum of that range on its own line, in the order the operations appear in the input. Every printed value is between $-2^{63}$ and $2^{63}-1$, inclusive.