Description

During the $n$ days when rental requests were accepted, on day $i$ there are $a_i$ classrooms remaining. As the person in charge of the university classroom rental service, you need to perform $m$ operations of the following three types:

1. From day $l$ to day $r$, $d$ classrooms are returned each day.
2. Query the average number of classrooms from day $l$ to day $r$.
3. Query the variance of the number of classrooms from day $l$ to day $r$.

Input Format

The first line contains two positive integers $n$ and $m$, where $n$ is the number of days and $m$ is the number of operations.

The next line contains $n$ integers; the $i$-th integer indicates that on day $i$ the number of remaining classrooms is $a_i$.

The next $m$ lines: each line starts with the operation code (only $1$, $2$, or $3$), followed by two positive integers $l$ and $r$. If the operation code is $1$, then an additional positive integer $d$ follows.

Output Format

For each operation of type $2$ and type $3$, output the answer as a reduced fraction (the numerator and denominator are coprime). In particular, if the answer is $0$, output $\verb!0/1!$.

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

4/1
2/3
14/25

Hint

For all testdata, $1 \leq l \leq r \leq n \leq 10^5$, $m \leq 10^5$, $0 \leq a_i \leq 10$, $1 \leq d \leq 3$, and the number of type $1$ operations does not exceed $10\%$.

Note: The small ranges of $a_i$ and $d$, and the small number of type $1$ operations, are intended to ensure that the numerator of the answer will not be large, preventing overflow beyond the $64$-bit integer range; this is unrelated to the intended solution.

Translated by ChatGPT 5