Sum of Squares with Segment Tree

Source: SPOJ

Version: Phuoc Hung OJ Extended

Problem Statement

Maintain an array with range assignment and range addition; queries return the sum of squares on a range.

Input

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

• 0 l r x: assign every value in $[l,r]$ to $x$.
• 1 l r x: add $x$ to every value in $[l,r]$.
• 2 l r: print $\sum_{i=l}^{r}a_i^2$.

Output

Print one line for each type 2 query. The PHOJ version omits the original multi-case Case k: line.

Subtasks

• 20 points: $n,q\le50$.
• 30 points: $n,q\le5000$.
• 50 points: $n,q\le10^5$, $|a_i|,|x|\le1000$; use 64-bit signed integers for intermediate values.

Examples

Input

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

Output

30
7
13

Explanation

The initial square sum is $30$. Assigning the last two values to 1 gives $7$. Adding 1 to those two positions produces 1 2 2 2, whose square sum is 13.