- Time limit: 1.00 s
- Memory limit: 512 MB
Your task is to maintain an array of values and efficiently process the following types of queries:
- Increase each value in range by .
- Set each value in range to .
- Calculate the sum of values in range .
Input
The first input line has two integers and : the array size and the number of queries.
The next line has values : the initial contents of the array.
Finally, there are lines describing the queries. The format of each line is one of the following: "1 ", "2 ", or "3 ".
Output
Print the answer to each sum query.
Constraints
Example
Input:
6 5 2 3 1 1 5 3 3 3 5 1 2 4 2 3 3 5 2 2 4 5 3 3 5
Output:
7 11 15