최소 비용 경로

파머 존의 목초지는 $N\times M$ 크기의 정사각형 칸으로 이루어진 격자이다 ($2\le N\le 10^9$, $2\le M\le 2\cdot 10^5$). 위에서 $x$번째 행, 오른쪽에서 $y$번째 열에 있는 칸을 $(x,y)$로 나타내며, $x\in[1,N]$, $y\in[1,M]$이다. 각 열 $y\in[1,M]$에는 비용 $c_y$ ($1\le c_y\le 10^9$)가 정해져 있다.

베시는 $(1,1)$에서 출발한다. 칸 $(x,y)$에 있을 때 다음 중 하나를 할 수 있다.

• $y<M$이면 비용 $x^2$을 내고 다음 열로 이동한다 ($y$가 1 증가한다).
• $x<N$이면 비용 $c_y$를 내고 다음 행으로 이동한다 ($x$가 1 증가한다).

$Q$개의 질의 ($1\le Q\le 2\cdot 10^5$)가 주어지며, 각 질의는 칸 $(x_i,y_i)$이다. 각 질의마다 $(1,1)$에서 $(x_i,y_i)$까지 이동하는 데 드는 최소 총 비용을 구하라. 질의들은 서로 독립이다.

첫 줄에 $N$과 $M$이 주어진다.

둘째 줄에는 공백으로 구분된 정수 $c_1, c_2, \ldots, c_M$이 주어진다.

셋째 줄에 $Q$가 주어진다.

이후 $Q$개의 줄에 각각 공백으로 구분된 정수 $x_i$와 $y_i$가 주어진다.

$Q$개의 줄에 각 질의의 답을 출력한다.

값이 커질 수 있으므로 C나 C++에서는 "long long" 같은 64비트 정수형을 사용해야 할 수 있다.

답을 격자 형태로 나타내면 다음과 같다.

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