#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;

const ull mod=(1ll<<64)-1;

ll mo(ll a,ll b)
{
	if(a>mod-b)return a-mod+b-1;
	return a+b;
}

int T,n;

namespace Subtask1
{
	const int M=105;
	
	int a[M],b[M];
	int q,l,r;
	
	void solve()
	{
		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);
		while(q--)
		{
			ull ans=0;
			scanf("%d %d",&l,&r);
			for(int p=l;p<=r;p++)
				for(int q=p;q<=r;q++)
				{
					ull mxa=0,mxb=0;
					for(int i=p;i<=q;i++)
					{
						mxa=max(mxa,1ull*a[i]);
						mxb=max(mxb,1ull*b[i]);
					}
					ans=mo(ans,mxa*mxb);
				}
			printf("%lld\n",ans);
					
		}
	}
}

namespace Subtask2
{
	const int M=3e3+5;
	
	int mxa[M][M],mxb[M][M];
	int a[M],b[M];
	int q,l,r;
	
	void solve()
	{
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		for(int i=1;i<=n;i++)
			scanf("%d",&b[i]);
		
		for(int i=1;i<=n;i++)
			for(int j=i;j<=n;j++)
			{
				mxa[i][j]=max(mxa[i][j-1],a[j]);
				mxb[i][j]=max(mxb[i][j-1],b[j]);
			}
				
		
		
		scanf("%d",&q);
		while(q--)
		{
			ull ans=0;
			scanf("%d %d",&l,&r);
			for(int p=l;p<=r;p++)
				for(int q=p;q<=r;q++)
				{
//					int mxa=0,mxb=0;
//					for(int i=p;i<=q;i++)
//					{
//						mxa=max(mxa,a[i]);
//						mxb=max(mxb,b[i]);
//					}
					ans=mo(ans,1ll*mxa[p][q]*mxb[p][q]);
				}
			printf("%lld\n",ans);
		}
	}
}

int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	
//	unsigned long long a=(1ll<<64)-1;
	
	scanf("%d %d",&T,&n);
	if(T<=2)Subtask1::solve();	
	else if(T<=5)Subtask2::solve();
	
}
/*
3 2
2 1
1 2
1
1 2
*/