Taco Query Processing

You are given an array \(A\) of \(N\) integers and need to handle \(Q\) queries on it. The array is 1-indexed. There are three types of queries:

• Add Query: + x y — Append \(y\) copies of integer \(x\) to the end of the array.
• Multiplication Query: * l r k — Multiply every element from index \(l\) to \(r\) (inclusive) by \(k\).
• Sum Query: ? l r — Compute and print the sum of elements from index \(l\) to \(r\) (inclusive).

Note that operations affect the current state of the array for subsequent queries.

inputFormat

The input is given via stdin in the following format:

• The first line contains two integers \(N\) and \(Q\): the number of elements in the initial array and the number of queries.
• The second line contains \(N\) space-separated integers representing the array \(A\).
• Each of the next \(Q\) lines contains one query in one of the formats: + x y, * l r k, or ? l r.

outputFormat

For each sum query (i.e. queries starting with ?), output the computed sum on a new line to stdout.

## sample

5 5
1 2 3 4 5
+ 7 3
? 1 8
* 2 4 2
? 2 5
+ 10 2

36
23

</p>