Let $ans_y(x)$ denote the minimum cost to go from $(1,1)$ to $(x,y)$. The key observation is that for a fixed $y$, the function $ans_y$ is concave up. Specifically, $ans_y[x]-ans_y[x-1]\le ans_y[x+1]-ans_y[x]$.

To get $ans_{y+1}$ from $ans_y$, we must

1. Set $ans_{y+1}(x)=ans_y(x)+x^2$ for all $x$.
2. Set $ans_{y+1}(x)=\min(ans_{y+1}(x),ans_{y+1}(x-1)+c_x)$ for all $x$.

The latter operation is equivalent to replacing a suffix of $ans_{y+1}$ with a straight line.

We can maintain the piecewise quadratic function $ans_y$ with a stack (similarly to convex hull trick). Whenever we perform the second operation, we pop some elements off the top of the stack and add a new element. To answer a query $(x,y)$, binary search on the stack corresponding to $ans_y$ to find the piece of the function that corresponds to $x$ and evaluate it.

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

#define f first 
#define s second

template<class T, class U> T fstTrue(T lo, T hi, U f) { 
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true 
		T mid = lo+(hi-lo)/2;
		f(mid) ? hi = mid : lo = mid+1; 
	} 
	return lo;
}

ll sq(ll x) { return x*x; }

int N,M;
vector<pair<int,int>> todo[200005];
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> M;
	vector<ll> C(M); for (ll& t: C) cin >> t;
	int Q; cin >> Q;
	vector<ll> ans(Q);
	for (int i = 0; i < Q; ++i) {
		int x,y; cin >> x >> y; --y;
		todo[y].push_back({x,i});
	}
	vector<pair<int,pair<int,ll>>> stk;
	for (int col = 0; col < M; ++col) {
		auto eval_pair = [&](const pair<int,ll>& a, ll x) {
			int pre_col = a.f;
			return sq(x)*(col-pre_col)+x*C[pre_col]+a.s;
		};
		auto eval = [&](int x) -> ll { // binary search to find corresponding stack element
			int fst_ind = fstTrue(0,(int)stk.size()-1,[&](int ind) {
				return stk[ind].f >= x; });
			return eval_pair(stk[fst_ind].s,x); // evaluate stack element at x
		};
		if (col) {
			while (stk.size() > 1) { // pop off stack
				int x = end(stk)[-2].f;
				pair<int,ll> lst = stk.back().s;
				ll val_at_x =          eval_pair(lst,x);
				ll val_at_x_plus_one = eval_pair(lst,x+1);
				if (val_at_x+C[col] < val_at_x_plus_one) {
					stk.pop_back();
					continue;
				}
				stk.back().f = fstTrue(x+1,stk.back().f-1,[&](int mid) {
					return eval_pair(lst,mid)+C[col] < eval_pair(lst,mid+1); });
				break;
			}
			if (stk.back().f < N) { // add to stack
				int x = stk.back().f;
				stk.push_back({N,{col,eval_pair(stk.back().s,x)-x*C[col]}});
			}
		} else { // initialize stack
			stk.push_back({1,{0,-C[0]}});
			stk.push_back({N,{0,-C[0]}});
		}
		for (pair<int,int> t: todo[col]) // answer all queries with y=col+1
			ans[t.s] = eval(t.f);
	}
	for (ll t: ans) cout << t << "\n";
}