Description

Frank is very interested in astronomy. He often observes stars with a telescope and records their information, such as brightness and color, and then estimates properties like distance and radius.

Frank not only enjoys observing but also analyzing the data he collects. He often checks whether there is some relationship between two parameters (for example, brightness and radius).

Now Frank wants to analyze the relationship between parameters $X$ and $Y$. He has $n$ groups of observations. The $i$-th group records $x_i$ and $y_i$. He needs to perform the following types of operations.

$\verb!1 L R!$

Fit a line to the observations from group $L$ to group $R$. Let $\overline{x}$ denote the mean of $x$ among these observations, and let $\overline{y}$ denote the mean of $y$, that is,

$$\begin{aligned}\overline{x}&={1 \over R-L+1} \sum _{i=L} ^R x_i \\\overline{y}&={1 \over R-L+1} \sum _{i=L} ^R y_i\end{aligned}$$

If the line equation is $y=ax+b$, then $a$ should be computed as:

$$a={\displaystyle\sum_{i=L} ^R (x_i-\overline{x})(y_i-\overline{y}) \over \displaystyle\sum _{i=L} ^R (x_i -\overline{x})^2}$$

You need to help Frank compute $a$.

$\verb!2 L R S T!$

Frank found that the measurements from group $L$ to group $R$ have errors. For each $i$ with $L \leq i \leq R$, add $S$ to $x_i$ and add $T$ to $y_i$.

$\verb!3 L R S T!$

Frank needs to modify the data from group $L$ to group $R$. For each $i$ with $L \leq i \leq R$, set $x_i$ to $(S+i)$ and set $y_i$ to $(T+i)$.

Input Format

The first line contains two numbers $n,m$, denoting the number of observation groups and the number of operations.

The next line contains $n$ numbers, where the $i$-th number is $x_i$.

The next line contains $n$ numbers, where the $i$-th number is $y_i$.

The next $m$ lines describe the operations. See the formats in the problem statement.

Output Format

For each operation of type $1$, output one line containing the slope $a$. Your output is considered correct if the absolute or relative error does not exceed $10^{-5}$.

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

1.0000000000
-1.5000000000
-0.6153846154

Hint

Constraints and Notes

• For $20\%$ of the testdata, $1 \leq n,m \leq 1000$.
• For another $20\%$ of the testdata, there is no operation $3$, and in operation $2$ we have $S=0$.
• For another $30\%$ of the testdata, there is no operation $3$.

For $100\%$ of the testdata, $1 \leq n,m \leq 10^5$, $0 \leq |S|,|T| \leq 10^5$, $0 \leq |x_i|,|y_i| \leq 10^5$.

It is guaranteed that in operation $1$ the denominator will not be $0$.

Translated by ChatGPT 5