#include<bits/stdc++.h>
using namespace std;
const int N = 250005;
typedef unsigned long long ull;
int n;
ull a[N], b[N];
ull ta[4*N], tb[4*N];
inline ull Max(ull a,ull b)
{
	if(a>b)
		return a;
	else
		return b;
}
void build(int k,int l,int r,ull *t, ull *c)
{
	if(l==r)
	{
		t[k] = c[l];
	//	cout<<t[k]<<"\n";
		return;
	}
	int mid = (l+r)>>1;
//	cout<<k<<" "<<l<<" "<<r<<"\n";
	build(k<<1,l,mid,t,c);
	build(k<<1|1,mid+1,r,t,c);
	t[k] = Max(t[k<<1],t[k<<1|1]);
}
ull inquire(int k,int l,int r,int x,int y,ull *t,ull *c)
{
	if(x<=l && r<=y)
		return t[k];
	int mid = l+r>>1;
	ull ans = 0;
	if(x<=mid) ans = Max(ans,inquire(k<<1,l,mid,x,y,t,c));
	if(y>mid) ans = Max(ans,inquire(k<<1|1,mid+1,r,x,y,t,c));
	return ans;
}
namespace sub2{
	const int NN = 3e3+5;
	ull an[NN][NN], sn[NN][NN];
	void work()
	{
		memset(an,0,sizeof(an));
		int Q;
		for(int i=1;i<=n;i++)
			scanf("%ull", &a[i]);
		for(int i=1;i<=n;i++)
			scanf("%ull", &b[i]);
		build(1,1,n,ta,a); 
		build(1,1,n,tb,b);
		scanf("%d", &Q);
	//	cout<<Q<<"\n";
		for(int i=1;i<=n;i++)
		{
			for(int j=i;j<=n;j++)
			{
				ull aa = inquire(1,1,n,i,j,ta,a);
				ull bb = inquire(1,1,n,i,j,tb,b);
				an[i][j] = aa*bb;
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				sn[i][j] = sn[i-1][j]+sn[i][j-1]-sn[i-1][j-1]+an[i][j];
			}
		}
		int l, r;
		while(Q--)
		{
			ull ans = 0;
			scanf("%d%d", &l, &r);
			cout<<sn[l][r]<<"\n";
		}	
	}
};
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int T;
	scanf("%d%d", &T, &n);
	if(T==1 || T==2)
	{
		int Q;
		for(int i=1;i<=n;i++)
			scanf("%ull", &a[i]);
		for(int i=1;i<=n;i++)
			scanf("%ull", &b[i]);
		build(1,1,n,ta,a); 
		build(1,1,n,tb,b);
		scanf("%d", &Q);
	//	cout<<Q<<"\n";
		int l, r;
		while(Q--)
		{
			ull ans = 0;
			scanf("%d%d", &l, &r);
			for(int i=l;i<=r;i++)
			{
				for(int j=i;j<=r;j++)
				{
					ull aa = inquire(1,1,n,i,j,ta,a);
					ull bb = inquire(1,1,n,i,j,tb,b);
					//cout<<i<<" "<<j<<" "<<aa<<" "<<bb<<"\n";
					ans = ans+aa*bb;
				}
			}
			cout<<ans<<"\n";
		}	
	}
	if(T==3 || T==4 || T==5)
		sub2::work();
	return 0;
}
/*
0 2
2 1
1 2
1
1 2
*/
