Maximizing Contest Feature

Alice is a master problem setter who creates one problem per day for n days. On the (n+1)-th day, she decides to choose a set of problems from her previous days to form a contest. To keep things simple, she will only pick a contiguous block of days, i.e. all problems from day l to day r (1 ≤ l ≤ r ≤ n).

Each problem has an associated score a_i (−1000 ≤ a_i ≤ 1001). A higher score implies that the problem is more intellectually challenging, while a lower score shows it favors coding skill.

The feature of a contest formed using problems from day l to day r is defined as follows:

$$\frac{(\sum_{i=l}^{r}a_i)^2}{r-l+1}$$

Alice wants the contest to have a strong characteristic by being either overall coding‐oriented or intelligence‐oriented. Therefore, she is interested in maximizing the above value.

You are given m queries. For each query, you are only allowed to choose problems from days ql to qr. Determine the maximum contest feature value that can be achieved using a contiguous segment within the query range. The answer must be output in fractional form (i.e. in the format p/q, where the fraction is in its irreducible form).

Note: You can assume that the scores are randomly generated.

inputFormat

The first line contains two integers n and m, the number of days and the number of queries respectively.

The second line contains n integers a₁, a₂, ..., a_n representing the scores for each day.

Each of the next m lines contains two integers ql and qr, indicating that only the problems from day ql to day qr (inclusive) can be chosen.

outputFormat

For each query, output a single line containing the maximum contest feature value in its irreducible fractional form (p/q).

sample

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

9/1
25/1
25/1