#include<bits/stdc++.h>
//#define int long long
#define int __int128
#define Maxn (200005)

using namespace std;

inline int read()
{
	int pos=1,num=0;
	char ch=getchar();
	while (!(ch>='0'&&ch<='9'))
	{
		if (ch=='-') pos=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9')
	{
		num=num*10+((int)ch-'0');
		ch=getchar();
	}
	return pos*num;
}

inline void write(int x)
{
	if (x<0)
	{
		putchar('-');
		write(-x);
		return;
	}
	if (x>=10) write(x/10);
	putchar((char)(x%10)+'0');
	return;
}
inline void writeln(int x)
{
	write(x);
	puts("");
	return;
}
inline void writesp(int x)
{
	write(x);
	putchar(' ');
	return;
}
int a[Maxn],b[Maxn];
signed main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int mod=1;
	for (int i=1;i<=64;i++)mod*=2;
	int pd=read(),n=read();
	for (int i=1;i<=n;i++)a[i]=read();
	for (int i=1;i<=n;i++)b[i]=read();
	int Q=read();
	while (Q--)
	{
		int l=read(),r=read();
		int sum=0;
		for (int i=l;i<=r;i++)
		{
			int Max1=0,Max2=0;
			for (int j=i;j<=r;j++)
			{
				Max1=max(Max1,a[j]),Max2=max(Max2,b[j]);
				(sum+=((Max1*Max2)%mod))%mod;
			}
		}
		writeln(sum);
	}
	return 0;
}

/*
0 2
1 2 
2 1
1
1 2
*/