Alice is an expert at creating problems.

Alice creates one problem every day, so after $n$ days, she has created $n$ problems.

On the $(n+1)$-th day, Alice does not create a problem. Instead, she plans to select a subset of the previous $n$ problems to form a contest. For convenience, she decides that the selected problems must form a contiguous time interval, meaning the problems must be those created from day $l$ to day $r$ ($1 \le l \le r \le n$).

Alice assigns a rating to each problem. The rating of the $i$-th problem is $a_i$ ($-1000 \le a_i \le 1001$). A higher rating indicates that the problem is more intelligence-oriented, while a lower rating indicates that the problem is more implementation-oriented.

Alice wants the contest to have a distinct character, meaning it should be either heavily implementation-oriented or heavily intelligence-oriented. The "distinctiveness" of a contest consisting of problems from day $l$ to day $r$ is defined as $\Large \frac{(\sum_l^r a_i)^2}{r-l+1}$. Alice wants to maximize this distinctiveness.

Now, for $m$ queries of the form $ql_i, qr_i$, you need to answer the maximum possible distinctiveness Alice can achieve if she is restricted to choosing problems from day $ql_i$ to day $qr_i$. You must output the result as a fraction.

Since Alice's problem-setting skill is exceptionally high, you may assume that the ratings of the problems are randomly generated.

Input

The first line contains a positive integer $n$.

The second line contains $n$ integers $a_1 \dots a_n$, representing the ratings of the problems Alice created on each day.

The third line contains a positive integer $m$.

The next $m$ lines each contain two positive integers $ql_i, qr_i$, representing a query.

Output

Output $m$ lines, each containing two integers $p_i, q_i$ such that $\gcd(p_i, q_i) = 1$, representing the answer as $\frac{p_i}{q_i}$. If the answer is $0$, output $0$ and $1$.

Examples

Input 1

5
-962 -445 -613 -9 920
3
1 5
3 5
1 3

Output 1

4080400 3
846400 1
4080400 3

Constraints

For the 2nd and 3rd subtasks, it is guaranteed that all queries satisfy $ql_i = 1$ and $qr_i = n$.

All $a_i$ are guaranteed to satisfy $-1000 \le a_i \le 1001$.

Furthermore, for $a_i$, the data is generated by independently choosing an integer uniformly at random from $[-1000, 1001]$ for each day.