#include<bits/stdc++.h>
using namespace std;
/*------------------------------fast io begin------------------------------*/
namespace Fread{
	const int SIZE=1<<16;
	char buf[SIZE],*S,*T;
	inline char getchar(){
		if(S==T){
			T=(S=buf)+fread(buf,1,SIZE,stdin);
			if(S==T)return '\n';
		}
		return *S++;
	}
}
namespace Fwrite{
	const int SIZE=1<<16;
	char buf[SIZE],*S=buf,*T=buf+SIZE;
	inline void flush(){
		fwrite(buf,1,S-buf,stdout);
		S=buf;
	}
	inline void putchar(char c){
		*S++=c;
		if(S==T)flush();
	}
	struct GreyCrane{
		~GreyCrane(){flush();}
	}HuiHe;
}
#define getchar Fread::getchar
#define putchar Fwrite::putchar
template<typename T>inline void read(T&x){
	x=0;T f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
	while(isdigit(c))x=x*10+(c^48),c=getchar();
	x*=f;
}
inline void read(string&s){
	char c=getchar();s="";
	while(c==' '||c=='\n'||c=='\r')c=getchar();
	while(!(c==' '||c=='\n'||c=='\r'))s+=c,c=getchar();
}
template<typename T>inline void write(T x){
	if(x==0)putchar('0');
	else{
		if(x<0)putchar('-'),x=-x;
		static int sta[45];int top=0;
		while(x)sta[++top]=x%10,x/=10;
		while(top)putchar(sta[top--]+48);
	}
}
inline void write(char c){putchar(c);}
/*------------------------------fast io end------------------------------*/
#define all(x) x.begin(),x.end()
#define siz(x) ((int)x.size())
#define ll long long
#define pb push_back
#define fi first
#define se second
#define edl putchar('\n')
#define spc putchar(' ')
#define ull unsigned long long
const int N=2.5e5+5,M=2.5e5+5;
int id,n,m,_2[N];
ull a[N],b[N],mx1[20][N],mx2[20][N],f[3001][3001];
inline ull q1(int l,int r){
	int k=_2[r-l+1];
	return max(mx1[k][l],mx1[k][r-(1<<k)+1]);
}
inline ull q2(int l,int r){
	int k=_2[r-l+1];
	return max(mx2[k][l],mx2[k][r-(1<<k)+1]);
}
inline ull solve(int l,int r){
	ull res=0;
	for(int p=l;p<=r;p++)res+=f[p][r];
	return res;
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	read(id),read(n);
	for(int i=1;i<=n;i++)read(a[i]),mx1[0][i]=a[i];
	for(int i=1;i<=n;i++)read(b[i]),mx2[0][i]=b[i];
	for(int i=1;i<20;i++){
		for(int j=1;j+(1<<i)-1<=n;j++){
			mx1[i][j]=max(mx1[i-1][j],mx1[i-1][j+(1<<(i-1))]);
			mx2[i][j]=max(mx2[i-1][j],mx2[i-1][j+(1<<(i-1))]);
		}
	}
	for(int i=2;i<=n;i++)_2[i]=_2[i>>1]+1;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			f[i][j]=f[i][j-1]+q1(i,j)*q2(i,j);
		}
	}
	read(m);
	for(int i=1,l,r;i<=m;i++){
		read(l),read(r);
		write(solve(l,r)),edl;
	}
	return 0;
}
