#include<bits/stdc++.h>
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#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 pt(x) cerr << #x << " = " << (x) << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 250000 + 5;
int testid, n, a[N], b[N], q;
struct SegmentTree {
	struct Node {
		int l, r, val, pos;
	} tr[N * 4];
	void pushup(int p) {
		tr[p].pos = tr[p*2].val >= tr[p*2+1].val ? tr[p*2].pos : tr[p*2+1].pos;
		tr[p].val = max(tr[p*2].val, tr[p*2+1].val);
	}
	void build(int p, int l, int r, int num[N]) {
		tr[p].l = l, tr[p].r = r;
		if(l == r) { tr[p].val = num[l], tr[p].pos = l; return; }
		int mid = (l + r) >> 1;
		build(p * 2, l, mid, num);
		build(p * 2 + 1, mid + 1, r, num);
		pushup(p);
	}
	pii query(int p, int l, int r) {
		if(l <= tr[p].l && r >= tr[p].r) return mkp(tr[p].val, tr[p].pos);
		int mid = (tr[p].l + tr[p].r) >> 1;
		if(l <= mid && r > mid) {
			pii res1 = query(p * 2, l, r), res2 = query(p * 2 + 1, l, r);
			return res1.fi >= res2.fi ? res1 : res2;
		}
		else if(l <= mid) return query(p * 2, l, r);
		else return query(p * 2 + 1, l, r);
	}
} smta, smtb;
namespace case1 {
	ull query(int l, int r) {
		ull res = 0;
		rep(p, l, r) {
			int maxa = 0, maxb = 0;
			rep(q, p, r) {
				maxa = max(maxa, a[q]);
				maxb = max(maxb, b[q]);
				res += (ull)maxa * maxb;
			}
		}
		return res;
	}
	void solve() {
		cin >> q;
		while(q--) {
			int l, r; scanf("%d%d", &l, &r);
			printf("%llu\n", query(l, r));
		}
	}
}
namespace case2 {
	ull c[3005][3005], sc[3005][3005];
	ull query(int l, int r) {
		ull res = 0;
		rep(i, l, r) res += sc[i][r];
		return res;
	}
	void solve() {
		rep(i, 1, n) {
			int maxa = 0, maxb = 0;
			sc[i][i-1] = 0;
			rep(j, i, n) {
				maxa = max(maxa, a[j]);
				maxb = max(maxb, b[j]);
				c[i][j] = (ull)maxa * maxb;
				sc[i][j] = sc[i][j-1] + c[i][j];
			}
		}
		cin >> q;
		while(q--) {
			int l, r; scanf("%d%d", &l, &r);
			printf("%llu\n", query(l, r));
		}
	}
}
namespace case3 {
	ull queryb(int l, int r) {
		if(l > r) return 0;
		pii t = smtb.query(1, l, r);
		ull res = queryb(l, t.se - 1) + queryb(t.se + 1, r);
		res += (ull)t.fi * (t.se - l + 1) * (r - t.se + 1);
		return res;
	}
	ull queryb(int l, int r, int mid) {
		return queryb(l, r) - queryb(l, mid - 1) - queryb(mid + 1, r);
	}
	ull query(int l, int r) {
		if(l > r) return 0;
		pii t = smta.query(1, l, r);
		ull res = query(l, t.se - 1) + query(t.se + 1, r);
		res += (ull)t.fi * queryb(l, r, t.se);
		return res;
	}
	void solve() {
		smta.build(1, 1, n, a);
		smtb.build(1, 1, n, b);
		cin >> q;
		while(q--) {
			int l, r; scanf("%d%d", &l, &r);
			printf("%llu\n", query(l, r));
		}
	}
}
int main() {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	cin >> testid >> n;
	rep(i, 1, n) scanf("%d", &a[i]);
	rep(i, 1, n) scanf("%d", &b[i]);
	if(n <= 3000 && q <= 3000) case2::solve();
	else case3::solve();
	return 0;
}
/*
0 2
2 1
1 2
1
1 2
*/
