#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int T,n,Q;
int a[250005],b[250005];
int sta[200005][20],stb[200005][20];
int cnt(int G)
{
	int js=0;
	while(G)
	{
		G>>=1;
		js++;
	}
	js-=1;
	return js;
}
signed main()
{
	ios::sync_with_stdio(false);
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	cin>>T>>n;
//	cout<<T<<n<<Q;
	for(int i=1;i<=n;++i) cin>>a[i],sta[i][0]=a[i];
	for(int i=1;i<=n;++i) cin>>b[i],stb[i][0]=b[i];
	
	int js=cnt(n);
	
//	cout<<js<<endl;
//	cout<<sta[1][0];
	for(int bt=1;bt<=js;++bt)
	{
		for(int i=1;i+(1<<bt)-1<=n;++i)
		{//cout<<"?"<<endl;
			sta[i][bt]=max(sta[i][bt-1],sta[i+(1<<(bt-1))][bt-1]);
			stb[i][bt]=max(stb[i][bt-1],stb[i+(1<<(bt-1))][bt-1]);
//			cout<<i<<' '<<bt<<' '<<sta[i][bt]<<' '<<stb[i][bt]<<endl;
		}	
	}
	cin>>Q;
	while(Q--)
	{
		int l,r;
		cin>>l>>r;
		int ans=0;
		for(int q1=l;q1<=r;++q1)
		{
			for(int q2=q1;q2<=r;++q2)
			{
				int o=cnt(q2-q1+1);
				ans+=max(sta[q1][o],sta[q2-(1<<o)+1][o])*max(stb[q1][o],stb[q2-(1<<o)+1][o]);
			}
		}
		cout<<ans<<endl;
	}
}