#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define mod 0x3f3f3f3f3f3f3f3f
long long ans;
int T,n,Q;
int a[100005],b[100005];
signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	cin>>T>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	cin>>Q;
	while(Q--){
		ans=0;
		int q1;
		int q2;
		int maxa=0;
		int maxb=0;
		cin>>q1>>q2;
		if(q2<q1) {
			int qq=q1;
			q1=q2;
			q2=qq;
		}
		for(int i=q1;i<=q2;i++){
			for(int j=i;j<=q2;j++){
				for(int w=i;w<=j;w++){
					maxa=max(a[w],maxa);
					maxb=max(b[w],maxb);
				}
				ans+=maxa*maxb;
			}
			maxa=0;
			maxb=0;
		}
        cout<<ans%mod<<endl;
	}
	return 0;
}
//a ha ha ha ha a ------- Â×ÄÉµÂ 
