Farmer John's pasture can be regarded as an n * m 2D grid of square "cells" (picture a huge chessboard). The cell at the x-th row from the top and y-th column from the right is denoted by (x, y) for each x ∈ [1, n], y ∈ [1, m]. Furthermore, for each y ∈ [1, m], the y-th column is associated with the cost cy (1 ≤ cy ≤ 109).

Bessie starts at the cell (1, 1). If she is currently located at the cell (x, y), then she may perform one of the following actions:

• If y < m, Bessie may move to the next column (increasing y by one) for a cost of x2.
• If x < n, Bessie may move to the next row (increasing x by one) for a cost of cy.

Given q independent queries each of the form (xi, yi) (xi ∈ [1, n], yi ∈ [1, m]), compute the minimum possible total cost for Bessie to move from (1, 1) to (xi, yi).

Input

The first line contains n and m (2 ≤ n ≤ 109, 2 ≤ m ≤ 2 * 105).

The second line contains m integers c1, c2, ..., cm.

The third line contains q (1 ≤ q ≤ 2 * 105).

The last q lines each contain two space-separated integers xi and yi.

Output

Print q 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++).

Example

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