#include<bits/stdc++.h>
//#define int long long
#define rint register int
#define UF(i,x,y) for(rint i=x;i<=y;i++)
#define DF(i,x,y) for(rint i=x;i>=y;i--)
#define ce continue
#define sf scanf
#define pf printf
#define inf 0x7fffffff
#define N 3005
using namespace std;
const unsigned long long mod=0x1999999999999999;
int a[N],b[N],T,n,l,r,Q,ma,mb;
long long f[N][N],ans;
signed main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	sf("%d%d",&T,&n);
	UF(i,1,n) sf("%d",&a[i]);
	UF(i,1,n) sf("%d",&b[i]);
	UF(i,1,n)
	{
		ma=a[i]; mb=b[i];
		f[i][i]=ma*mb%mod;
		UF(j,i+1,n)
		{
			ma=max(ma,a[j]);
			mb=max(mb,b[j]);
			f[i][j]=(f[i][j-1]+ma*mb%mod)%mod;
			//sigma i,i~j
		}
	}
	sf("%d",&Q);
	while(Q--)
	{
		sf("%d%d",&l,&r);
		ans=0;
		UF(i,l,r) ans=(ans+f[i][r])%mod;
		pf("%lld\n",ans%mod);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}