#include<bits/stdc++.h>
#define gc getchar
#define pc putchar
#define F(i,x,y) for(int i=x;i<=y;++i)
#define R(i,x,y) for(int i=x;i>=y;--i)
#define max std::max
#define min std::min
typedef long long LL;
typedef unsigned long long ULL;
inline int read(){
	int x=0;char ch=gc();bool p=1;
	while (!isdigit(ch)) ch=='-'?p=0:0,ch=gc();
	while ( isdigit(ch)) x=(x<<1)+(x<<3)+(ch^'0'),ch=gc();
	return p?x:-x;
}
const int N=250000+5;
int n,q;
ULL f[3005][3005],maxA[3005][3005],maxB[3005][3005],A[N],B[N];
signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int T=read();
	n=read();
	F(i,1,n) A[i]=read();
	F(i,1,n) B[i]=read();
	if (T<=5){
		F(i,1,n) F(j,i,n){
			maxA[i][j]=max(maxA[i][j-1],A[j]);
			maxB[i][j]=max(maxB[i][j-1],B[j]);
		}
		F(len,1,n) F(i,1,n-len+1){
			int j=i+len-1;
			f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1]+maxA[i][j]*maxB[i][j];
		}
		q=read();
		F(i,1,q){
			int l=read(),r=read();
			printf("%llu\n",f[l][r]);
		}
		return 0;
	}else puts("I can't do this :(");
//	q=read();
//	F(i,1,q){
//		int l=read(),r=read();
//		
//	}
	return 0;
}
