# ADA University - March 7 - Segment Tree

# Sum of Squares with Segment Tree

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** ≤ `10`

) and ^{5}**q** (**q** ≤ `10`

). The next line contains ^{5}**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.

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

Case 1: 30 7 13 Case 2: 1