Farmer John's pasture can be regarded as an N×MN×M (2≤N≤1092≤N≤109, 2≤M≤2⋅1052≤M≤2⋅105) 2D grid of square "cells" (picture a huge chessboard). The cell at the xx-th row from the top and yy-th column from the right is denoted by (x,y)(x,y) for each x∈**[1,N],y∈[1,M]x∈[1,N],y∈[1,M]. Furthermore, for each y∈[1,M]y∈[1,M], the yy-th column is associated with the cost cycy (1≤cy≤109**1≤cy≤109).Bessie starts at the cell (1,1)(1,1). If she is currently located at the cell (x,y)(x,y), then she may perform one of the following actions:

• If y<My<M, Bessie may move to the next column (increasing yy by one) for a cost of x2x2.
• If x<Nx<N, Bessie may move to the next row (increasing xx by one) for a cost of cycy.

Given QQ (1≤Q≤2⋅1051≤Q≤2⋅105) independent queries each of the form (xi,yi**)(xi,yi) (xi∈**[1,N],yi∈**[1,M]xi∈[1,N],yi∈[1,M]), compute the minimum possible total cost for Bessie to move from (1,1)(1,1) to (xi,yi)**(xi,yi).

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains NN and MM.The second line contains MM space-separated integers c1**,c2**,…,cMc1,c2,…,cM.

The third line contains QQ.

The last QQ lines each contain two space-separated integers xixi and yiyi.

OUTPUT FORMAT (print output to the terminal / stdout):

QQ lines, containing the answers for each query.Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

SAMPLE INPUT:

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

SAMPLE OUTPUT:

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

The output in grid format:

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|
  *--*--*--*--*

SCORING:

• Test cases 1-3 satisfy N,M≤2000N,M≤2000.
• Test cases 4-8 satisfy c2**>c3**>⋯>cMc2>c3>⋯>cM.
• Test cases 9-15 satisfy N≤2⋅105N≤2⋅105.
• Test cases 16-20 satisfy no additional constraints.