#include<bits/stdc++.h>
using namespace std;
#define N 250005
#define ull unsigned long long
#define mod 184467440737095516
int maxa[N<<2],maxb[N<<2];
void up(int c,int maxx[])
{
	maxx[c]=max(maxx[c<<1],maxx[c<<1|1]);
}
void build(int c,int l,int r,int maxx[])
{
	if(l==r){
		scanf("%d",&maxx[c]);
		return ;
	}
	int mid=l+r>>1;
	build(c<<1,l,mid,maxx);
	build(c<<1|1,mid+1,r,maxx);
	up(c,maxx);
}
int query(int c,int l,int r,int x,int y,int maxx[])
{
	if(x<=l&&r<=y) return maxx[c];
	int mid=l+r>>1;int ans=-1;
	if(x<=mid) ans=max(ans,query(c<<1,l,mid,x,y,maxx));
	if(y>mid) ans=max(ans,query(c<<1|1,mid+1,r,x,y,maxx));
	return ans;
}
int T,n,Q;
void file()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
}
int main()
{
	file();
	cin>>T>>n;
	build(1,1,n,maxa);
	build(1,1,n,maxb);
	cin>>Q;
	int l,r;
	while(Q--)
	{
		scanf("%d%d",&l,&r);
		ull ans=0;
		for(int i=l;i<=r;i++)
		{
			for(int j=i;j<=r;j++)
			{
				(ans+=query(1,1,n,i,j,maxa)*query(1,1,n,i,j,maxb))%=mod;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}
