#include <bits/stdc++.h>
#define reopen(A) { freopen(#A".in", "r", stdin); freopen(#A".out", "w", stdout); }
#define F(i, l, r) for(int i = l; i < r; ++i)
#define Fe(i, l, r) for(int i = l; i <= r; ++i)
#define Fer(i, l, r) for(int i = l; i >= r; --i)
#define debug(a) cout<< #a": " << a <<endl;
#define endl '\n'
using namespace std;
typedef long long ll;
constexpr int N = 250010;
int n;
int a[N], b[N];
int lg[N];
int sta[N][18], stb[N][18];

void init(){
	lg[1] = 0;
	for(int i = 2; i <= n; i++){
		lg[i] = lg[i >> 1] + 1;
	}
	Fe(i, 1, n){
		sta[i][0] = a[i];
		stb[i][0] = b[i];
	}
	Fe(i, 1, lg[n]){
		Fe(j, 1, n - (1 << (i - 1)) + 1){
			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]);
		}
	}
}

int querya(int l, int r){
	int len = r - l + 1;
//	debug(lg[len]);
	int res = max(sta[l][lg[len]], sta[r - (1 << lg[len]) + 1][lg[len]]);
//	cout<<sta[l][lg[len]]<<' '<<sta[r - (1 << lg[len]) + 1][lg[len]]<<endl;
	return res;
}

int queryb(int l, int r){
	int len = r - l + 1;
	int res = max(stb[l][lg[len]], stb[r - (1 << lg[len]) + 1][lg[len]]);
	return res;
}

signed main(){
	reopen(match);
	ios::sync_with_stdio(0); cin.tie(0);
	int T;
	cin>>T>>n;
	Fe(i, 1, n) cin>>a[i];
	Fe(i, 1, n) cin>>b[i];
	init();
	int Q;
	cin>>Q;
	while(Q--){
		unsigned long long ans = 0;
		int l, r;
		cin>>l>>r;
		if(n <= 30){
			Fe(p, l, r){
				Fe(q, p, r){
					int maxa = -1, maxb = -1;
					Fe(k, p, q){
						maxa = max(maxa, a[k]);
						maxb = max(maxb, b[k]);
					}
					ans += (unsigned long long) maxa * maxb;
				}
			}
			cout<<ans<<endl;	
		} else { // CCF give me some pts though ST table must be wrong, please
			Fe(p, l, r){
				Fe(q, p, r){
					int maxa = -1, maxb = -1;
					maxa = querya(p, q);
					maxb = queryb(p, q);
					ans += (unsigned long long) maxa * maxb;
				}
			}
			cout<<ans<<endl;
		}
	}
	
	return 0;
}
