Description

An array with length $n$ is given.
You should support 2 types of operations.

1.$x$ $y$ change the $x-th$ element to $y$.
2.$l$ $r$ print the variance of the elements with indices $l, l + 1, ... , r$.
As the result may not be an integer, you need print the result after multiplying $(r-l+1)^2$.

The index of the array is from 1.

Format

Input

The first line is two integer $n, m(1 \leq n, m \leq 2^{16})$, indicating the length of the array and the number of operations.
The second line is $n$ integers, indicating the array. The elements of the array $0\leq a_i \leq 10^4$. The following $m$ lines are the operations. It must be either 1 $x$ $y$ or 2 $l$ $r$

Output

For each query, print the result.

Samples

4 4
1 2 3 4
2 1 4
1 2 4
2 1 4
2 2 4

20
24
2