#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
const long long MOD = 1e9;
int f1[N][N];
int f2[N][N];
int a[N],b[N];
int n;
long long ans;
int erfen1(int x,int y){
	if(x == y) return a[x];
	if(x > y) return 0;
	int mid = x+y>>1;
	if(f1[x][y]) return f1[x][y];
	f1[x][y] = max(erfen1(x,mid),erfen1(mid+1,y));
	return f1[x][y];
}
int erfen2(int x,int y){
	if(x == y) return b[x];
	if(x > y) return 0;
	int mid = x+y>>1;
	if(f2[x][y]) return f2[x][y];
	f2[x][y] = max(erfen2(x,mid),erfen2(mid+1,y));
	return f2[x][y];
}
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
    int T;
    cin >> T;
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
	}
	for(int i = 1;i <= n;i++) cin >> b[i];
	
    int Q;
    cin >> Q;
    for(int i = 1;i <= Q;i++){
    	memset(f1,0,sizeof(f1));
    	memset(f2,0,sizeof(f2));
		for(int i = 1;i <= n;i++){
		    f1[i][i] = a[i];
		    f2[i][i] = b[i];
	    }
    	ans = 0;
    	int l,r;
    	cin >> l >> r;
    	erfen1(l,r);
    	erfen2(l,r);
    	for(int q = l;q <= r;q++){
    		for(int p = q;p <= r;p++){
    			if(!f1[q][p]) f1[q][p] = erfen1(q,p);
    			if(!f2[q][p]) f2[q][p] = erfen2(q,p);
    			ans += f1[q][p]*f2[q][p];
    			ans %= MOD;
			}
		}
		cout << ans;
	}
    return 0;
}
