#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define ull unsigned long long
using namespace std;
//const ull Mod=(1ull<<64);
int T,n,a[300000][20],b[300000][20],lo[300000],q;
long long ans=0;
int read()
{
	int p=1,ans=0;
	char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar())
	if(ch=='-') p=-1;
	ans=ch-'0';
	for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())
	ans=(ans<<1)+(ans<<3)+ch-'0';
	return ans*p;
}
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	scanf("%d %d",&T,&n);
	lo[1]=0;
	for(int i=2;i<=n;i++)
	lo[i]=lo[i/2]+1;
	{
		for(int i=1;i<=n;i++)
		scanf("%d",&a[i][0]);
		for(int i=1;i<=n;i++)
		scanf("%d",&b[i][0]);
		for(int i=0;i<15;i++)
		for(int j=1;j<=n;j++)
		a[j][i+1]=max(a[j][i],a[j+(1<<i)][i]),b[j][i+1]=max(b[j][i],b[j+(1<<i)][i]);
		//cout<<Mod<<endl;
		scanf("%d",&q);
		for(int i=1;i<=q;i++)
		{
			int l,r;
			ans=0;
			scanf("%d %d",&l,&r);
			for(int j=l;j<=r;j++)
			for(int k=j;k<=r;k++)
			{
				int st=lo[k-j+1];
				ull max_a=max(a[j][st],a[k-(1<<st)+1][st]);
				ull max_b=max(b[j][st],b[k-(1<<st)+1][st]);
				//cout<<ans<<" "<<max_a<<" "<<max_b<<endl;
				ans=(ans+max_a*max_b);
			}
			printf("%lld\n",ans);
		}
		
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}