#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=250005;
//const long long pi=2<<63;
ll T,n,Q,l,r,p,q,ans,t1,pi=2<<29;
ll a[N],b[N],x[N],y[N],t[N];
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	unsigned long long p=pi*pi*16-1;
	scanf("%d%d",&T,&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&b[i]);
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++)
	{
		ans=0;
		scanf("%d%d",&l,&r);
		for(int j=l;j<=r;j++)
		{
			for(int k=j;k<=r;k++)
			{
				for(int c=1;c<=n;c++)
				{
					x[c]=a[c];
					y[c]=b[c];
				}
				sort(x+j,x+k+1);
				sort(y+j,y+k+1);
				ans+=x[k]*y[k]%p;
			}
		}
//		t[++t1]=ans;
		printf("%lld\n",ans);
	}
//	puts("");
//	puts("");
//	puts("");
//	for(int i=1;i<=t1;i++)
//		printf("%d\n",t[i]);
	fclose(stdin);
	fclose(stdout);
}
/*
0 2
2 1
1 2
1
1 2
*/
