#include<bits/stdc++.h>
using namespace std;

//#define int long long
#define PB emplace_back
#define siz(a) ((int) (a.size()))
#define vi vector<int>
#define ll long long
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

#define u64 unsigned long long
const int N = 2.5e5;
int T, a, k1[N + 5], k2[N + 5], t1, t2, b;
u64 s1[N + 5], s2[N + 5], ans[N + 5], lzy[N * 4 + 5], w[N * 4 + 5];
struct pii {int x, y;};
vector<pii> q[N + 5];

#define ls n << 1
#define rs n << 1 | 1
void upd(int n, int l, int r, u64 k) {
	w[n] += (r - l + 1) * k;
	lzy[n] += k;
}
void dw(int n, int l, int r) {
	int mid = (l + r) >> 1;
	upd(ls, l, mid, lzy[n]);
	upd(rs, mid + 1, r, lzy[n]);
	lzy[n] = 0;
}
void add(int n, int l, int r, int L, int R, u64 k) {
	if(l >= L && r <= R) return upd(n, l, r, k), void();
	dw(n, l, r);
	int mid = (l + r) >> 1;
	if(L <= mid) add(ls, l, mid, L, R, k);
	if(mid < R) add(rs, mid + 1, r, L, R, k);
	w[n] = w[ls] + w[rs];
}
u64 ask(int n, int l, int r, int L, int R) {
	if(l >= L && r <= R) return w[n];
	dw(n, l, r);
	int mid = (l + r) >> 1;
	u64 res = 0;
	if(L <= mid) res += ask(ls, l, mid, L, R);
	if(mid < R) res += ask(rs, mid + 1, r, L, R);
	return res;
}

signed main() {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T >> a;
	rep(i, 1, a) cin >> s1[i];
	rep(i, 1, a) cin >> s2[i];
	cin >> b;
//	if(T >= 10 && T <= 13) {
//		
//	}
	int x, y;
	rep(i, 1, b) cin >> x >> y, q[y].PB((pii) {x, i});
	rep(i, 1, a) {
		while(t1 && s1[k1[t1]] < s1[i]) --t1;
		k1[++t1] = i;
		while(t2 && s2[k2[t2]] < s2[i]) --t2;
		k2[++t2] = i;
		u64 val;
		int now = i;
		for(int j = t1, k = t2; now; ) {
			val = s1[k1[j]] * s2[k2[k]];
			int mx = max(k1[j - 1], k2[k - 1]);
//			cout << mx << ' ' << now << ' ' << val << endl;
			add(1, 1, a, mx + 1, now, val);
			now = mx;
			if(k1[j - 1] == mx) --j;
			if(k2[k - 1] == mx) --k;
		}
		for(pii x : q[i]) ans[x.y] = ask(1, 1, a, x.x, i);
	}
	rep(i, 1, b) cout << ans[i] << '\n';
	return 0;
}