#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

//bool _u;

namespace AK {

typedef pair <int, int> pii;
typedef unsigned long long ll;
typedef double db;

#define fi first
#define se second

#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++ i)
#define per(i, l, r) for(int i = l, i##end = r; i >= i##end; -- i)

template <class T>
inline void chmax(T &x,const T &y) {
	if(x < y) x = y;
}

template <class T>
inline void chmin(T &x, const T &y) {
	if(y < x) x = y;
}

inline int read() {
	int res = 0; char ch = getchar(); bool f = 1;
	for(; ch < '0' || ch > '9'; ch = getchar())
		if(ch == '-') f = 0;
	for(; ch >= '0' && ch <= '9'; ch = getchar())
		res = res * 10 + ch - '0';
	return f ? res : -res;
}

const int N = 5e5 + 15;

vector <pii> Q[N];
ll ans[N];
ll sum[N], sa[N], sb[N];
int s1[N], s2[N], t1, t2;
int a[N], b[N];
int n;

/*
struct node {
	ll len;
	ll hs, sa, sb, sab;
	ll ta, tb, hk, ha, hb;

	inline void add(ll xa, ll xb) {
		sab += xa * sb + xb * sa + xa * xb * len;
		sa += xa * len; sb += xb * len;
		ta += xa; tb += xb;
	}

	inline void hadd(ll k, ll xa, ll xb) {
		hs += sab * k + xa * sb + xb * sa + xa * xb * len;
		hk += k; ha += xa + ta * k; hb += xb + tb * k;
	}

} t[N * 4];



#define lc (p << 1)
#define rc (p << 1 | 1)

inline void upd(int p) {
	t[p].sa = t[lc].sa + t[rc].sa;
	t[p].sb = t[lc].sb + t[rc].sb;
	t[p].sab = t[lc].sab + t[rc].sab;
	t[p].hs = t[lc].hs + t[rc].hs;
}

inline void push(int p) {
	if(t[p].hk || t[p].ha || t[p].hb) {
		t[lc].hadd(t[p].hk, t[p].ha, t[p].hb);
		t[rc].hadd(t[p].hk, t[p].ha, t[p].hb);
		t[p].hk = t[p].ha = t[p].hb = 0;
	}
	if(t[p].ta || t[p].tb) {
		t[lc].add(t[p].ta, t[p].tb);
		t[rc].add(t[p].ta, t[p].tb);
		t[p].ta = t[p].tb = 0;
	}
}

void build(int p, int l, int r) {
	t[p].len = r - l + 1;
	if(l == r) return ;
	int mid = l + r >> 1;
	build(lc, l, mid);
	build(rc, mid + 1, r);
}

void modify(int p, int l, int r, int tl, int tr, ll xa, ll xb) {
	if(tl <= l && r <= tr) {
		t[p].add(xa, xb);
		return ;
	}
	int mid = l + r >> 1;
	push(p);
	if(tl <= mid) modify(lc, l, mid, tl, tr, xa, xb);
	if(mid < tr) modify(rc, mid + 1, r, tl, tr, xa, xb);
	upd(p);
}

ll query(int p, int l, int r, int tl, int tr) {
	if(tl <= l && r <= tr) return t[p].hs;
	int mid = l + r >> 1;
	ll res = 0;
	push(p);
	if(tl <= mid) res += query(lc, l, mid, tl, tr);
	if(mid < tr) res += query(rc, mid + 1, r, tl, tr);
	return res;
}
*/

void modify(int p, int l, int r, int tl, int tr, ll x, ll y) {
	if(x) rep(i, tl, tr) sa[i] += x;
	if(y) rep(i, tl, tr) sb[i] += y;
}

void gg() {
	rep(i, 1, n) sum[i] += sa[i] * sb[i];
}

ll query(int p, int l, int r, int tl, int tr) {
	ll res = 0;
	rep(i, tl, tr) res += sum[i];
	return res;
}

void Main() {
	int l, r, q;
	read(); n = read();
	rep(i, 1, n) a[i] = read();
	rep(i, 1, n) b[i] = read();
	q = read();
	rep(i, 1, q) {
		l = read(); r = read();
		Q[r].emplace_back(l, i);
	}
	//build(1, 1, n);
	rep(i, 1, n) {
		for(; t1 && a[s1[t1]] < a[i]; -- t1)
			modify(1, 1, n, s1[t1 - 1] + 1, s1[t1], a[i] - a[s1[t1]], 0);
		s1[++ t1] = i;
		for(; t2 && b[s2[t2]] < b[i]; -- t2)
			modify(1, 1, n, s2[t2 - 1] + 1, s2[t2], 0, b[i] - b[s2[t2]]);
		modify(1, 1, n, i, i, a[i], b[i]);
		s2[++ t2] = i;
		//t[1].hadd(1, 0, 0);
		gg();
		for(pii p : Q[i]) ans[p.se] = query(1, 1, n, p.fi, i);
	}
	rep(i, 1, q) printf("%llu\n", ans[i]);
}

}

//bool _v;

signed main() {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	//clock_t st = clock();
	AK :: Main();
	//cerr << "time = " << (clock() - st) * 1.0 / CLOCKS_PER_SEC << endl;
	//cerr << "space = " << (&_u - &_v) / 1048576.0 << endl;
	return 0;
}
