Hoshino Aquamarine gives you a sequence $a_1, \dots, a_n$ of length $n$ and $m$ operations of two types:

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

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 $1, l, r, x$ or $2, l, r$, representing an operation.

Output

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

Examples

Input 1

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

Output 1

11/2
5/1

Subtasks

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

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

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

For another $25\%$ of the data, there are no operations of type 1.

For $100\%$ of the data, $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 $l < r$.