#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=250010;
class SEG{
	// Private section
	int mx[N<<2];
	public:
		// Public Declarations
		SEG(){}
		void build(int x,int l,int r,int *a){
			if(l>r)return;
			if(l==r){
				mx[x]=a[l];
				return;
			}
			int m=(l+r)>>1;
			build(x<<1,l,m,a);
			build(x<<1|1,m+1,r,a);
			mx[x]=max(mx[x<<1],mx[x<<1|1]);
		}
		int ser(int x,int l,int r,int L,int R){
			if(l>r)return 0;;
			if(L<=l&&r<=R)return mx[x];
			int m=(l+r)>>1,ta=0;
			if(L<=m)ta=max(ta,ser(x<<1,l,m,L,R));
			if(R>m)ta=max(ta,ser(x<<1|1,m+1,r,L,R));
			return ta;
		}
	protected:
		// Protected Declarations
}sa,sb;
int T,n;
int a[N],b[N];
int Q;
int l,r;
ull ans;
namespace s1{
	void solve(){
		scanf("%d",&Q);
		for(int i=1;i<=Q;i++){
			scanf("%d%d",&l,&r);
			ans=0;
			for(int i=l;i<=r;i++){
				for(int j=i;j<=r;j++){
					ans+=(ull)sa.ser(1,1,n,i,j)*sb.ser(1,1,n,i,j);
				}
			}
			printf("%llu\n",ans);
		}
		
	}
}
namespace s2{
	ull dp[3030][3030]={};
	void solve(){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n-i+1;j++){
				if(i==1)dp[j][j]=a[j]*b[j];
				else dp[j][j+i-1]=dp[j][j+i-2]+dp[j+1][j+i-1]-dp[j+1][j+i-2]+sa.ser(1,1,n,j,j+i-1)*sb.ser(1,1,n,j,j+i-1);
			}
		}
		scanf("%d",&Q);
		for(int i=1;i<=Q;i++){
			scanf("%d%d",&l,&r);
			printf("%llu\n",dp[l][r]);
		}
	}
}
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	scanf("%d%d",&T,&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	sa.build(1,1,n,a);
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
	}
	sb.build(1,1,n,b);
	if(T<=5){
		s2::solve();
		return 0;
	}
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++){
		scanf("%d%d",&l,&r);
		ans=0;
		printf("%llu\n",ans);
	}
	return 0;
}
