#include<bits/stdc++.h>
using namespace std;
const int maxn=250010;
const long long mod=184467440730000;
long long a[maxn],b[maxn];
long long t,n,Q;
long long l,r;
long long ans;
int main() {
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	ios::sync_with_stdio(false);
	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;
		cin>>l>>r;
		for(int i=l; i<=r; ++i) {
			ans=(ans+a[i]*b[i])%mod;
		}
		for(int p=l; p<=r-1; ++p) {
			long long maxa=a[p];
			long long maxb=b[p];
			for(int q=p+1; q<=r; ++q) {
				maxa=max(maxa,a[q]);
				maxb=max(maxb,b[q]);
				ans=(ans+maxa*maxb)%mod;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
