Description

The noob HansBug found a magical sequence in a math book, consisting of $N$ real numbers. He wants to compute the mean and variance of this sequence.

Input Format

The first line contains two positive integers $N, M$, denoting the number of real numbers in the sequence and the number of operations.

The second line contains $N$ real numbers, where the $i$-th real number is the $i$-th term of the sequence.

The next $M$ lines each describe an operation, in one of the following three formats:

• Operation 1: 1 x y k, add $k$ (a real number) to every term from the $x$-th to the $y$-th item.
• Operation 2: 2 x y, compute the mean of the subsequence from the $x$-th to the $y$-th item.
• Operation 3: 3 x y, compute the variance of the subsequence from the $x$-th to the $y$-th item.

Output Format

Output several lines, each containing one real number, which are the results of every Operation 2 or Operation 3 in order. Round all results to $4$ decimal places using standard rounding.

5 5
1 5 4 2 3
2 1 4
3 1 5
1 1 1 1
1 2 2 -1
3 1 5

3.0000
2.0000
0.8000

Hint

About variance: For a sequence $A$ with $n$ terms, its variance $s^2$ is defined as:

$$s^2=\frac{1}{n}\sum\limits_{i=1}^n\left(A_i-\overline A\right)^2$$

where $\overline A$ is the mean of sequence $A$, and $A_i$ is the $i$-th term of sequence $A$.

Sample explanation: | Step | Input | Requirement | Sequence | Output | Note | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $0$ | - | - | 1 5 4 2 3 | - | - | | $1$ | 2 1 4 | Compute the mean of all numbers in $\left[1,4\right]$ | 1 5 4 2 3 | 3.0000 | Mean $=\left(1+5+4+2\right)\div 4=3.0000$. | | $2$ | 3 1 5 | Compute the variance of all numbers in $\left[1,5\right]$ | 1 5 4 2 3 | 2.0000 | Mean $=\left(1+5+4+2+3\right)\div 5=3$, variance $=\left(\left(1-3\right)^2+\left(5-3\right)^2+\left(4-3\right)^2+\left(2-3\right)^2+\left(3-3\right)^2\right)\div 5=2.0000$. | | $3$ | 1 1 1 1 | Add $1$ to all numbers in $\left[1,1\right]$ | 2 5 4 2 3 | - | - | | $4$ | 1 2 2 -1 | Add $-1$ to all numbers in $\left[2,2\right]$ | 2 4 4 2 3 | - | - | | $5$ | 3 1 5 | Compute the variance of all numbers in $\left[1,5\right]$ | 2 4 4 2 3 | 0.8000 | Mean $=\left(2+4+4+2+3\right)\div 5=3$, variance $=\left(\left(2-3\right)^2+\left(4-3\right)^2+\left(4-3\right)^2+\left(2-3\right)^2+\left(3-3\right)^2\right)\div 5=0.8000$. |

Constraints: | Test points | $N$ | $M$ | Note | | :----------: | :----------: | :----------: | :----------: | | $1\sim3$ | $N\le 8$ | $M\le 15$ | - | | $4\sim7$ | $N\le 10^5$ | $M\le 10^5$ | Operation $3$ not included. | | $8\sim10$ | $N\le 10^5$ | $M\le 10^5$ | - |

All numbers in the original sequence and all input $k$ are real numbers within the range $[-100, 100]$.

Translated by ChatGPT 5