Segment trees are extremely useful. In particular "Lazy Propagation" (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 the sum of squares over a range with range updates of two types:

• increment in a range
• set all numbers the same in a range.

Input

First line contains number of test cases. First line of each test contains two positive integers n (n ≤ 105) and q (q ≤ 105). The next line contains n integers, each no more than 1000 by absolute value. 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 -1000 ≤ x ≤ 1000).

0 st nd x – set all numbers with indices in [st, nd] to "x" (1 ≤ st ≤ nd ≤ n, and -1000 ≤ x ≤ 1000).

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.