#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=250005,maxm=250005;
int n,Q;
ll a[maxn],b[maxn],fa[maxn][20],fb[maxn][20];
ll querya(int x,int y){
	int len=y-x+1,l=(int)log2(len);
	return max(fa[x][l],fa[y-(1<<l)+1][l]);
}
ll queryb(int x,int y){
	int len=y-x+1,l=(int)log2(len);
	return max(fb[x][l],fb[y-(1<<l)+1][l]);
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int T;
	scanf("%d%d",&T,&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),fa[i][0]=a[i];
	for(int i=1;i<=n;i++) scanf("%d",&b[i]),fb[i][0]=b[i];
	for(int i=1;i<20;i++){
		for(int j=1;j+(1ull<<i)-1<=n;j++){
			fa[j][i]=max(fa[j][i-1],fa[j+(1ull<<i-1)][i-1]);
			fb[j][i]=max(fb[j][i-1],fb[j+(1ull<<i-1)][i-1]);
		}
	}
	scanf("%d",&Q);
	while(Q--){
		int left,right;
		scanf("%d%d",&left,&right);
		if(T<=2){
			unsigned long long s=0;
			for(int i=left;i<=right;i++){
				for(int j=left;j<=i;j++){
					s=s+querya(j,i)*queryb(j,i);
				}
			}
			cout<<s<<endl;
		}
	}
	return 0;
}
