#include<bits/stdc++.h>
using namespace std;
#define gc getchar
#define pc putchar
#define ll long long
#define int ll
#define ull unsigned ll
int read(){
	int ret=0;bool f=1;char c=gc();
	while(!isdigit(c))(c=='-'?f=!f:0),c=gc();
	while(isdigit(c))ret=(ret<<3)+(ret<<1)+(c^48),c=gc();
	return f?ret:-ret;
}
const int maxn=2.5e5+5;
int n,q,a[2][maxn];
int L[2][maxn],R[2][maxn];
int tr[2][maxn<<2];
void build(int op,int p,int L,int R){
	if(L==R){tr[op][p]=a[op][L];return;}
	int mid=L+R>>1;
	build(op,p<<1,L,mid),build(op,p<<1|1,mid+1,R);
	tr[op][p]=max(tr[op][p<<1],tr[op][p<<1|1]);
}
int get(int op,int p,int L,int R,int l,int r){
	if(l<=L&&R<=r)return tr[op][p];
	if(R<l||r<L)return 0;
	int mid=L+R>>1;
	return max(get(op,p<<1,L,mid,l,r),get(op,p<<1|1,mid+1,R,l,r));
}
const ll mod=1ll<<63;
ll sum(int x,int y){
	int a=x>>1,b=y>>1,c=x&1,d=y&1;
	if(c&&d)a++,c=d=0;
	if(a+b>=mod)return (a+b-mod<<1)|c|d;
	return x+y;
}
signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	read(),n=read();
	for(int i=1;i<=n;i++)a[0][i]=read();
	for(int i=1;i<=n;i++)a[1][i]=read();
	for(int i=1;i<=n;i++)L[0][i]=R[0][i]=L[1][i]=R[1][i]=i;
	for(int i=2;i<=n;i++)if(a[0][i]>a[0][i-1])L[0][i]=L[0][i-1];
	for(int i=n-1;i;i--)if(a[0][i]>a[0][i+1])R[0][i]=R[0][i+1];
	for(int i=2;i<=n;i++)if(a[1][i]>a[1][i-1])L[1][i]=L[1][i-1];
	for(int i=n-1;i;i--)if(a[1][i]>a[1][i+1])R[1][i]=R[1][i+1];
	q=read();
	while(q--){
		int l=read(),r=read(),ans=0;
		for(int i=l;i<=r;i++)
		for(int j=i;j<=r;j++){
			
			ans=sum(ans,);
		}
		printf("%lld\n",ans);
	}
	return 0;
}