Background

Problem Description

Ai Hoshino Aiku Aimi gives you a sequence $a_1,\dots,a_n$ of length $n$, with a total of $m$ operations. There are two types of operations:

1. Given $l,r,x$, add $x$ to $a_l,\dots,a_r$.
2. Given $l,r$, query $\mathop{\max}\limits_{l\le L<R\le r}\frac{\sum\limits_{i=L}^R a_i}{R-L+1}$.

Input Format

The first line contains two integers $n,m$.

The second line contains $n$ integers $a_1,\dots,a_n$.

The next $m$ lines each contain either 1,l,r,x or 2,l,r, describing one operation.

Output Format

For each operation of type 2, output one line containing the answer as an irreducible fraction (in the form a/b or -a/b or 0/1; $a,b$ are coprime positive integers). For example, $\frac{5}{3},\;-\frac46,\;-1,\;0,\;2$ should be output as 5/3, -2/3, -1/1, 0/1, 2/1, respectively.

5 8
-7 -8 -1 5 8
1 4 5 -3
1 2 3 7
1 5 5 3
1 1 4 1
2 4 5
1 3 4 -1
1 1 2 7
2 4 5

11/2
5/1

Hint

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

For $25\%$ of the testdata, $n,m\le 100$.

For $50\%$ of the testdata, $n,m\le 8000$.

For the other $25\%$ of the testdata, there is no operation 1.

For $100\%$ of the testdata, $1\le n,m\le 10^6$, $|a_i|,|x|\le 10^3$, and all values are integers. For operation 2, it is guaranteed that there is no case with $l=r$.

Translated by ChatGPT 5