#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0)
#define lowbit(x) (x&(-x))
using namespace std;
void write(__int128 x)
{
	if (x<0)
	{
		putchar('-');
		write(-x);
		return;
	}
	if (x>=10) write(x/10);
	putchar(x%10+'0');
}
const int N=3e3+10;
int T,n,Max1[N][25],Max2[N][25],Q;
__int128 ans[N][N],mod;
inline int query1(int l,int r)
{
	int k=__lg(r-l+1);
	return max(Max1[l][k],Max1[r-(1<<k)+1][k]);
}
inline int query2(int l,int r)
{
	int k=__lg(r-l+1);
	return max(Max2[l][k],Max2[r-(1<<k)+1][k]);
}
signed main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int T; scanf("%d%d",&T,&n); mod=1;
	for (int i=1;i<=64;i++) mod=mod*2;
	for (int i=1;i<=n;i++) scanf("%d",&Max1[i][0]);
	for (int i=1;i<=n;i++) scanf("%d",&Max2[i][0]);
	for (int j=1;j<=20;j++)
		for (int i=1;i+(1<<j)-1<=n;i++)
			Max1[i][j]=max(Max1[i][j-1],Max1[i+(1<<(j-1))][j-1]),Max2[i][j]=max(Max2[i][j-1],Max2[i+(1<<(j-1))][j-1]);
	for (int len=1;len<=n;len++)
		for (int i=1;i<=n-len+1;i++)
		{
			int j=i+len-1,x=query1(i,j),y=query2(i,j);
			ans[i][j]=(ans[i+1][j]+ans[i][j-1]+(__int128)x*y%mod)%mod;
//			cout<<i<<' '<<j<<' '; write(ans[i][j]); putchar('\n');
		}
	scanf("%d",&Q);
	while (Q--)
	{
		int l,r; cin>>l>>r;
		write(ans[l][r]); putchar('\n');
	}
}
