## SEGSQRSS - Sum of Squares with Segment Tree

Segment trees are extremely useful. In particular "Lazy Propagation" (i.e. see here, for example) allows one to compute sums over a range in O(lg(n)), and update ranges in O(lg(n)) as well. In this problem you will compute something much harder:

The sum of squares over a range with range updates of 2 types:

1) increment in a range

2) set all numbers the same in a range.

### Input

There will be T (T <= 25) test cases in the input file. First line of the input contains two positive integers, N (N <= 100,000) and Q (Q <= 100,000). The next line contains N integers, each at most 1000. Each of the next Q lines starts with a number, which indicates the type of operation:

2 st nd -- return the sum of the squares of the numbers with indices in [st, nd] {i.e., from st to nd inclusive} (1 <= st <= nd <= N).

1 st nd x -- add "x" to all numbers with indices in [st, nd] (1 <= st <= nd <= N, and -1,000 <= x <= 1,000).

0 st nd x -- set all numbers with indices in [st, nd] to "x" (1 <= st <= nd <= N, and -1,000 <= x <= 1,000).

### Output

For each test case output the “Case <caseno>:” in the first line and from the second line output the sum of squares for each operation of type 2. Intermediate overflow will not occur with proper use of 64-bit signed integer.

### Example

```Input:
2
4 5
1 2 3 4
2 1 4
0 3 4 1
2 1 4
1 3 4 1
2 1 4
1 1
1
2 1 1

Output:
Case 1:
30
7
13
Case 2:
1```

 < Previous 1 2 3 4 5 6 Next > anonymous: 2014-07-02 01:03:09 cake walk...AC without lazy propagation...:) Last edit: 2014-07-02 01:04:02 GURVINDER SINGH: 2014-06-04 19:12:30 Got wa for printing case #%d :( silly me :p Ashwin. K: 2013-04-23 16:38:39 um. Test cases are very weak. Consider adding a testcase similar to 1 6 2 3 3 3 3 3 3 0 1 3 2 2 1 2 Chen Xiaohong: 2012-07-11 22:01:53 Thanks! This is now fixed. Note also that "x" can be 0 for the set operation (it's -1000 <= x <= 1000). Also note that increments can happen after sets, and sets can happen after increments. Rejudged after fixing this also in the dataset. Last edit: 2012-07-13 20:29:52 Buda IM (retired): 2012-07-11 22:01:26 I don't think input example is correct. You have 5 queries, but Q=4