#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<vector>
#include<map>
#include<set>
using namespace std;

#define pb push_back
#define fi first
#define se second
typedef unsigned long long ll;
typedef double db;
const int N=3e3+86;

int T,n,Q;
ll a[N],b[N];
ll ma[N][N];
struct Segment_Tree
{
	int l;
	int r;
	ll a;
	ll b;
}t[N<<2];
void push_up(int o){t[o].a=max(t[o<<1].a,t[o<<1|1].a),t[o].b=max(t[o<<1].b,t[o<<1|1].b);}
void build(int o,int l,int r)
{
	t[o].l=l,t[o].r=r;
	if(l==r)
	{
		t[o].a=a[l];
		t[o].b=b[l];
		return;
	}
	int mid=l+r>>1;
	build(o<<1,l,mid);
	build(o<<1|1,mid+1,r);
	push_up(o);
}
ll ansa,ansb;
void query(int o,int l,int r)
{
	if(t[o].l>=l&&t[o].r<=r) 
	{
		ansa=max(ansa,t[o].a);
		ansb=max(ansb,t[o].b);
		return;
	}
	if(t[o<<1].r>=l) query(o<<1,l,r);
	if(t[o<<1|1].l<=r) query(o<<1|1,l,r);
}

void solve(int l,int r)
{
	ll ans=0;
	for(int i=l;i<=r;i++)
		for(int j=i;j<=r;j++)
		{
			ansa=ansb=0;
			if(!ma[i][j]) query(1,i,j),ma[i][j]=ansa*ansb;
			ans=ans+ma[i][j];
		}
	printf("%llu\n",ans);
}

template<typename T>
inline void read(T &x)
{
	T k=1;x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')k=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x*=k;
}

int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
//	freopen("match3.in","r",stdin);
//	freopen("OUT.txt","w",stdout);
	read(T),read(n);
	while(T--)
	{
		memset(ma,0,sizeof(ma));
		for(int i=1;i<=n;i++) read(a[i]);
		for(int i=1;i<=n;i++) read(b[i]);
		build(1,1,n);
		read(Q);
		while(Q--)
		{
			int l,r;
			read(l),read(r);
			solve(l,r);
		}
	}
	return 0;
}

