#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;

int T,n,a[25001],b[25001],q,ma[3005][3005],mb[3005][3005],now,ans;

signed main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	cin>>T>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		cin>>b[i];
	for(int i=1;i<=n;i++)
	{
		now=a[i];
		for(int j=i;j<=n;j++)
		{
			if(i==j)
			{
				ma[i][j]=a[i];
				continue;
			}
			if(a[j]>now)
			{
				ma[i][j]=a[j];
				now=a[j];
			}
			else ma[i][j]=now;
		}
	}
	for(int i=1;i<=n;i++)
	{
		now=b[i];
		for(int j=i;j<=n;j++)
		{
			if(i==j)
			{
				mb[i][j]=b[i];
				continue;
			}
			if(b[j]>now)
			{
				mb[i][j]=b[j];
				now=b[j];
			}
			else mb[i][j]=now;
		}
	}
	cin>>q;
	while(q--)
	{
		int l,r;
		cin>>l>>r;
		ans=0;
		for(register int i=l;i<=r;i++)
		for(register int j=i;j<=r;j++)
			ans=ans+(ma[i][j]*mb[i][j]);
		cout<<ans<<endl;
	}
}
