Alice 是一个出题高手。

Alice 每天都会出一道题，这样 $n$ 天过去，她就出了 $n$ 道题了。

第 $n+1$ 天，Alice 没有出题，她打算从之前的 $n$ 道题中选择若干道组成一个比赛。方便起见，她决定这些选择的题目得是连续的一个时间段出的，也就是这些题目必须形如：第 $l$ 天到第 $r$ 天出的所有题目（$1\le l\le r\le n$）。

Alice 还给每个题目一个评分，第 $i$ 个题目的评分为 $a_i(-1000\le a_i\le 1001)$ ，评分越高代表这道题越偏智商，评分越低说明这道题越偏码力。

Alice 希望组成的比赛具备特色，也即整体偏向代码或者整体偏向智商。一场以 Alice 第 $l$ 天到第 $r$ 天出的题目组成的比赛的特色程度定义为 $\frac{(\sum _l^r{a}_i{)}^2}{r-l+1}$ ，Alice 想要最大化这个特色程度。

现在，对于 $m$ 个形如 $q{l}_i,q{r}_i$ 的询问，你需要回答如果将 Alice 能选择的题目限定在第 $q{l}_i$ 到 $q{r}_i$ 天出的题，Alice 能组成的特色程度最大的比赛的特色程度是多少，你需要以分数的形式输出这个特色程度。

由于 Alice 出题的水平过于高超，你可以认为每道题的评分是随机生成的。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$。

输入的第二行包含 $n$ 个整数 $a_1\dots a_n$ ， 代表 Alice 对第 $i$ 天所出的题的评分。

输入的第三行包含一个正整数 $m$ 。

接下来 $m$ 行，每行输入两个正整数 $q{l}_i,q{r}_i$ ，表示询问。

输出格式

输出到标准输出。

共 $m$ 行，每行两个整数 $p_i,q_i$ ， 满足 $gcd(p_i,q_i)=1$，表示答案为 $\frac{p_i}{q_i}$ ，若答案为 $0$ ，则 $p_i=0,q_i=1$。

样例

input

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

输出

4080400 3
846400 1
4080400 3

数据范围与提示

对于 第 $2$ 个和第 $3$ 个子任务，保证所有询问满足 $q{l}_i=1,q{r}_i=n$。

所有的 $a_i$ 保证满足 $-1000\le a_i\le 1001$ 。

且对于 $a_i$ ，数据生成方式为每次独立地从 $[-1000,1001]$ 中等概率随机选取一个整数。

时间限制：$\mathtt{\text{1s}}$

空间限制：$\mathtt{\text{512MB}}$