E. Variance
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Then winter comes — the snow keeps falling and accumulating, eventually covering all sins. Finally spring arrives — along with the melting snow, all punishments are delivered.

Just cure whoever you can. There is no way to fix the problem setter who designed this problem.

As we all know, a person who is obsessed with bad endings just like this problem setter can never be cured. But if a problem can be solved with only slope optimization, it is still worth a try.

Given a sequence of $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$. You need to perform $$$q$$$ operations in total, choosing from the two types below. It is guaranteed that every number in the sequence always stays within the range $$$[1, 2 \times 10^5]$$$.

  1. Add a positive integer $$$x$$$ to all elements in the interval $$$[l,r]$$$.

  2. Consider a subarray $$$a_l, a_{l + 1}, \cdots ,a_r$$$ whose length is at least $$$2$$$. Split it into several consecutive segments, where each segment has a length of no less than $$$2$$$. Suppose a segment has length $$$L$$$ and elements $$$b_1, b_2, \cdots, b_L$$$. Let its variance be $$$$$$ \sigma^2=\frac{1}{L}\sum^L_{i=1}(b_i-\bar{b})^2 $$$$$$ Define the weight of this segment as $$$\sigma^2 L$$$. You need to find an optimal splitting scheme to minimize the total weight. Note that the defined weight is NOT equal to the variance.
Input

The first line contains two positive integers $$$n, q$$$ $$$(2 \le n \le 2 \times 10^5, 1 \le q \le 2 \times 10^5)$$$.

The second line contains $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 2 \times 10^5)$$$.

The following $$$q$$$ lines describe the operations:

Each line starts with an integer $$$op \in \{1,2\}$$$. If $$$op = 1$$$, three positive integers $$$l, r, x$$$ follow $$$(1 \le l \le r \le n, 1 \le x \le 2 \times 10^5)$$$, which means adding $$$x$$$ to every element in interval $$$[l,r]$$$. If $$$op = 2$$$, two positive integers $$$l, r$$$ follow $$$(1 \le l \lt r \le n)$$$, which means querying the minimal total weight of interval $$$[l, r]$$$.

Output

For each query of type $$$op=2$$$, output two integers $$$a$$$ and $$$b$$$ separated by a single space on one line. Constraints: $$$a \ge 0,\ b \gt 0,\ \gcd(a, b) = 1$$$. The minimal weight equals $$$\dfrac{a}{b}$$$. Specially, if the minimal weight is an integer $$$x$$$, you should output $$$x$$$ and $$$1$$$.

Example
Input
6 10
1 2 3 4 5 6
2 2 5
1 1 6 1
2 1 6
1 3 4 2
2 1 3
2 4 6
1 5 5 1
1 1 2 3
1 1 1 1
2 1 6
Output
1 1
3 2
26 3
2 3
0 1