#include<bits/stdc++.h>

#define rd(x) x=read()

#define N 3005
#define int unsigned long long

using namespace std;

int T,n,Q;
int a[N][2],mx[N][N][2],s[N],f[N];
const unsigned long long mod = 1ll<<63;

inline int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
	return x*f;
}

signed main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	rd(T),rd(n);
	for(int i=1;i<=n;i++)rd(a[i][0]);
	for(int i=1;i<=n;i++)rd(a[i][1]);
	for(int i=1;i<=n;i++)mx[i][i][0]=a[i][0],mx[i][i][1]=a[i][1];
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			mx[i][j][0]=max(mx[i][j-1][0],a[j][0]),
			mx[i][j][1]=max(mx[i][j-1][1],a[j][1]);
	rd(Q);
	while(Q--)
	{
		int l,r;rd(l),rd(r);
		int ans=0;
		for(int i=l;i<=r;i++)
			for(int j=i;j<=r;j++)
				ans=(ans+mx[i][j][0]*mx[i][j][1]%mod);
		printf("%lld\n",ans);
	}
	
	return 0;
}
