#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ans,tem;
const int maxn = 250005, sqmaxn = 125005;
const ll mop = 4294967296;//1<<32
ll tot;
int n,Q,T,a[maxn],b[maxn],l[maxn],r[maxn],m[100];
int pa[maxn][2000],pb[maxn][2000];

template <typename T>
inline T read(){
	T x = 0, f = 1;
	char ch = 0;
	while(!isdigit(ch)){
		if(ch == '-')	f = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x<<3) + (x<<1) + (ch - '0');
		ch = getchar();
	}
	return x * f;
}

template <typename T>
inline void write(T x){
	static int sta[135];
	int top = 0;
	if(x < 0){
		x = -x;
		putchar('-');
	}
	do{
		sta[top++] = x%10;
		x /= 10;
	} while(x);
	while(top){
		putchar(sta[--top] + '0');
	}
}

void pre_max(int l,int r,int op){
	if(op == 1){
		for(int t=l;t<=r;t++){
			for(int k=1; (t-l)>=k && k<=(sqrt(n)+1); k++){
				if(k == 1){
				pa[t][k] = a[t];
				continue;}
				pa[t][k] = max(pa[t-1][k-1],a[t]);
			}
		}
	}
	if(op == 2){
		for(int t=l;t<=r;t++){
			for(int k=1; (t-l)>=k && k<=(sqrt(n)+1); k++){
				if(k == 1){
				pb[t][k] = b[t];
				continue;}
				pb[t][k] = max(pb[t-1][k-1],b[t]);
			}
		}
	}
	
}

void mo(ll &a){
	if(a >= mop){
		tot++;
		a -= mop;
	}
}

void reans(){
	if(tot >= 4294967296){
		tot = tot % 4294967296;
	}
	int an[100],bn[100];
	int u = 1,v = 1;
	do{
		an[u] = ans%100000;
		ans /= 100000;
		u++;
	}while(ans);
	if(tot == 0){
		for(int z=1;z<=u;z++){
			m[z] = an[z];
		}
		return;
	}
	else{
		for(int z = tot;z > 0;z--){
			bn[v] += mop%100000;
			v++;
		}
		for(int z = 1;z<=v;z++){
			if(bn[z] >= 100000){
				bn[z+1] += (bn[z]/100000);
				bn[z] = bn[z] % 100000;
			}
		}
		for(int z=1;z <= max(v,u);z++){
			if(an[z] + bn[z] >= 100000){
				m[z] = (an[z] + bn[z]) % 100000;
				m[z+1] = (an[z] + bn[z]) / 100000;
			}
			else{
				m[z] = an[z] + bn[z];
			}
		}
	}
}

int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	cin>>T>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		cin>>b[i];
	cin>>Q;
	for(int i=1;i<=Q;i++)
		cin>>l[i]>>r[i];
	int i = 1;
	while(Q--){
		memset(pa,0,sizeof(pa));
		memset(pb,0,sizeof(pb));
		tot = 0;
		ans = 0;
		pre_max(l[i],r[i],1);//a
		pre_max(l[i],r[i],2);//b
		int le = r[i] - l[i] + 1;
		for(int j=1; j <= le; j++)//q-p
			for(int s =l[i]; (s+j-1)<=r[i]; s++){
				int h = sqrt(j)+1;
				ans += max(pa[s+h][j],pa[s+j-1][j])*max(pb[s+h][j],pb[s+j-1][j]);
				mo(ans);
			}
		i++;
		reans();
		int z = 1,top = 0;
		while(!m[z]){
			top++;
			z++;
		}
		while(top--){
			write(m[top]);
		}
		cout<<endl;
	}
	return 0;
}
