Correlation Analysis

Frank is very interested in astronomy. He often uses a telescope to observe stars and records their information, such as brightness, color, etc., to estimate properties like distance and radius.

Frank not only likes observing but also enjoys analyzing the observed data. He often analyzes the relationship between two parameters (such as brightness and radius) to see if there is any correlation.

Frank now wants to analyze the relationship between parameters $X$ and $Y$. He has $n$ sets of observational data, where the $i$-th set records $x_i$ and $y_i$. He needs to perform the following operations:

• $1 \ L \ R$: Perform linear regression on the observational data from $L$ to $R$. Let $\bar{x}$ be the mean of $x$ in these observations, and $\bar{y}$ be the mean of $y$ in these observations, i.e.,

  $$\bar{x} = \frac{1}{R - L + 1} \sum_{i=L}^{R} x_i$$

  $$\bar{y} = \frac{1}{R - L + 1} \sum_{i=L}^{R} y_i$$

  If the linear equation is $y = ax + b$, then $a$ and $b$ should be calculated as follows:

  $$a = \frac{\sum_{i=L}^{R} (x_i - \bar{x})(y_i - \bar{y})}{\sum_{i=L}^{R} (x_i - \bar{x})^2}$$

  $$b = \bar{y} - a\bar{x}$$

  You need to help Frank calculate $a$.

• $2 \ L \ R \ S \ T$: Frank discovers an error in the measurements from $L$ to $R$. For every $i$ such that $L \le i \le R$, $x_i$ needs to be increased by $S$, and $y_i$ needs to be increased by $T$.

• $3 \ L \ R \ S \ T$: Frank discovers that the data from $L$ to $R$ needs to be modified. For every $i$ such that $L \le i \le R$, $x_i$ needs to be modified to $(S + i)$, and $y_i$ needs to be modified to $(T + i)$.

Input

The first line contains two integers $n$ and $m$, representing the number of observational data sets and the number of operations.

The next line contains $n$ integers, where the $i$-th integer is $x_i$.

The next line contains $n$ integers, where the $i$-th integer is $y_i$.

The next $m$ lines each contain an operation, formatted as described in the problem statement.

Output

For each operation of type 1, output the slope $a$ on a new line. The absolute or relative error between your output and the standard output should not exceed $10^{-5}$.

Examples

Input 1

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

Output 1

1.0000000000
-1.5000000000
-0.6153846154

Constraints

• For 20% of the data, $1 \le n, m \le 1000$.
• For another 20% of the data, there are no type 3 operations, and for type 2 operations, $S = 0$.
• For another 30% of the data, there are no type 3 operations.
• For 100% of the data, $1 \le n, m \le 10^5$.
• For all data, $1 \le L \le R \le n$, $0 \le |S|, |T| \le 10^5$, $0 \le |x_i|, |y_i| \le 10^5$.
• For all data, type 1 operations will not result in a denominator of 0.