#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int n = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		n *= 10, n += ch ^ 48;
		ch = getchar();
	}
	return n * f;
}
inline void write(unsigned long long n){
	if(n > 9) write(n / 10);
	putchar(n % 10 + 48);
}
int T, n, sta[250010][19], stb[250010][19], q, l, r;
unsigned long long ans;
int main(){
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	T = read(), n = read();
	for(int i = 1; i <= n; i++){
		sta[i][0] = read();
	}
	for(int i = 1; i <= n; i++){
		stb[i][0] = read();
	}
	for(int i = 1; i <= 18; i++){
		for(int j = 1; j + (1 << (i - 1)) <= n; j++){
			sta[j][i] = max(sta[j][i - 1], sta[j + (1 << (i - 1))][i - 1]);
			stb[j][i] = max(stb[j][i - 1], stb[j + (1 << (i - 1))][i - 1]);
		}
	}
	q = read();
	while(q--){
		ans = 0;
		l = read(), r = read();
		for(int i = l; i <= r; i++){
			for(int j = i; j <= r; j++){
				int tmp = log2(j - i + 1);
				ans += 1llu * max(sta[i][tmp], sta[j - (1 << tmp) + 1][tmp])
							* max(stb[i][tmp], stb[j - (1 << tmp) + 1][tmp]);
			}
		}
		write(ans);
		putchar(10);
	}
	return 0;
}
/*
我好菜啊qwq 
//freopen
freeopen
feropen
freopen("match.in", "w", stdout);
freopen("match.out", "r", stdoin);

完全的暴力：按照题意模拟。复杂度O(qn^2 + nlogn)爆炸 
期望得分8 
期望总分[70,100] + [0,15] + 0 + 8 = [78,123] 
(删除线)比赛体验很好，明年再来(删除线) 
*/
