Range Updates and Sums

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

Maintain an array with range addition, range assignment, and range-sum queries.

Input

The first line contains $n,q$ and the next line contains the initial array. Queries are:

• 1 a b x: add $x$ to $[a,b]$.
• 2 a b x: assign every element of $[a,b]$ to $x$.
• 3 a b: calculate the sum of $[a,b]$.

Output

Print the answer for every type 3 query.

Subtasks

• 20 points: $n,q\le50$.
• 30 points: $n,q\le5000$.
• 50 points: $1\le n,q\le2\cdot10^5$, $1\le t_i,x\le10^6$.

Examples

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

Explanation

Initially $a_3+a_4+a_5=7$. Adding 2 to $[2,4]$ changes that sum to 11. Assigning $[2,4]$ to 5 makes $[3,5]$ equal to 5 5 5, so the final answer is 15.