Farmer John 的牧草地可以看作是一个 N×M（2≤N≤10$^9$, 2≤M≤2⋅10$^5$）的正方形方格组成的二维方阵（想象一个巨大的棋盘）。对于 x∈[1,N],y∈[1,M]，从上往下第 x 行、从左往右第 y 列的方格记为 (x,y)。此外，对于每一个 y∈[1,M]，第y 列拥有一个代价 c$_y$（1≤c$_y$≤109）。Bessie 从方格 (1,1) 出发。如果她现在位于方格 (x,y)，则她可以执行以下操作之一：

• 如果 y<M，Bessie 可以以x$^2$ 的代价移动到下一列（y 增加一）。
• 如果 x<N，Bessie 可以以 c$_y$ 的代价移动到下一行（x 增加一）。

给定 Q（1≤Q≤2⋅10$^5$）个独立的询问，每个询问给定 (x$_i$,y$_i$)（x$_i$∈[1,N],y$_i$∈[1,M]），计算 Bessie 从 (1,1) 移动到 (x$_i$,y$_i$) 的最小总代价。

输入格式（从终端/标准输入读入）：

输入的第一行包含 N 和 M。第二行包含 M 个空格分隔的整数 c$_1$,c$_2$,…,c$_M$。

第三行包含 Q。

最后 Q 行每行包含两个空格分隔的整数x$_i$ 和 y$_i$。

输出格式（输出至终端/标准输出）：

输出 Q 行，为每个询问的答案。注意本题计算中所使用的整数大小可能需要使用 64 位整数型（例如，C/C++ 中的 long long）。

输入样例：

5 4
1 100 100 20
20
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 3
2 3
3 3
4 3
5 3
1 4
2 4
3 4
4 4
5 4

输出样例：

0
1
2
3
4
1
5
11
19
29
2
9
20
35
54
3
13
29
49
69

输出以方阵形式表示如下：

1  2  3  4
  *--*--*--*--*
1 | 0| 1| 2| 3|
  *--*--*--*--*
2 | 1| 5| 9|13|
  *--*--*--*--*
3 | 2|11|20|29|
  *--*--*--*--*
4 | 3|19|35|49|
  *--*--*--*--*
5 | 4|29|54|69|
  *--*--*--*--*

测试点性质：

• 测试点 1-3 满足 N,M≤2000。
• 测试点 4-8 满足 c$_2$>c$_3$>⋯>c$_M$。
• 测试点 9-15 满足 N≤2⋅10$^5$。
• 测试点 16-20 没有额外限制。