#include <bits/stdc++.h>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	int t, n;
	cin >> t >> n;
	vector<int> a(n);
	vector<int> b(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}
	int Q;
	cin >> Q;
	if (n <= 3000) {
		vector<vector<unsigned long long>> res(n, vector<unsigned long long>(n, 0));
		for (int i = 0; i < n; i++) {
			int mxa = 0, mxb = 0;
			unsigned long long ans = 0;
			for (int j = i; j < n; j++) {
				mxa = max(mxa, a[j]);
				mxb = max(mxb, b[j]);
				ans += 1ull * mxa * mxb;
				res[i][j] = ans;
			}
		}
		while (Q--) {
			int l, r;
			cin >> l >> r;
			--l;
			unsigned long long ans = 0;
			for (int p = l; p < r; p++) {
				ans += res[p][r - 1];
			}
			cout << ans << "\n";
		}
	} else {
		vector<int> stk;
		vector<int> ra(n), rb(n);
		for (int i = n - 1; i >= 0; i--) {
			while (stk.size() && a[stk.back()] < a[i])
				stk.pop_back();
			if (stk.size())
				ra[i] = stk.back();
			else
				ra[i] = n;
			stk.push_back(i);
		}
		stk.clear();
		for (int i = n - 1; i >= 0; i--) {
			while (stk.size() && b[stk.back()] < b[i])
				stk.pop_back();
			if (stk.size())
				rb[i] = stk.back();
			else
				rb[i] = n;
			stk.push_back(i);
		}
		stk.clear();
		while (Q--) {
			int l, r;
			cin >> l >> r;
			--l;
			unsigned long long ans = 0;
			for (int p = l; p < r; p++) {
				vector<array<int, 2>> aa, bb;
				int i = p;
				int j = p;
				while (ra[i] < r) aa.push_back(array<int, 2>{i, ra[i]}), i = ra[i];
				aa.push_back(array<int, 2>{i, min(r, ra[i])});
				while (rb[j] < r) bb.push_back(array<int, 2>{j, rb[j]}), j = rb[j];
				bb.push_back(array<int, 2>{j, min(r, rb[j])});

				for (auto x : aa) {
					for (auto y : bb) {
						int l = max(x[0], y[0]);
						int r = min(x[1], y[1]);
						if (l < r)
							ans += 1ull * (r - l) * a[x[0]] * b[y[0]];
					}
				}
			}
			cout << ans << "\n";
		}
	}
	return 0;
}