#include<bits/stdc++.h>
using namespace std;
int t,n;
struct NODE
{
	int num;
	int id;
}a[250001],b[250001];
//bool cmp(NODE x,NODE y)
//{
//	return x.num>y.num?1:0;
//}
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	scanf("%d%d",&t,&n);
	for(int i=1; i<=n; i++) 
	{
		scanf("%d",&a[i].num);
		a[i].id=i;
	}
	for(int i=1; i<=n; i++) 
	{
		scanf("%d",&b[i].num);
		b[i].id=i;
	}
	int Q;
	int sum;
	scanf("%d",&Q);
	for(int q=1; q<=Q; q++)
	{
		sum=0;
		int l,r;
		cin>>l>>r;
		for(int i=l; i<=r; i++)
			for(int j=l; j<=r; j++)
			{
				int maxa=0,maxb=0;
			//	if(f[i][j]==0)
				{
					for(int k=i; k<=j; k++)
					{
						maxa=max(maxa,a[k].num);
						maxb=max(maxb,b[k].num);
					}
				}
				sum=(sum+maxa*maxb)%(1<<24);
			}
		cout<<sum<<endl;		
	}
	return 0;
}
