#include<bits/stdc++.h>
const int N = 3005;
int T, n, a[N], b[N], Q;
int l, r; unsigned long long ans;
void slv(){
    ans = 0;
    scanf("%d%d", &l, &r);
    for(int i=l; i<=r; i++){
        int mxa = a[i], mxb = b[i];
        for(int j=i; j<=r; j++){
            mxa = std::max(mxa, a[j]);
            mxb = std::max(mxb, b[j]);
            ans += mxa * mxb;
        }
    }
    printf("%llu\n", ans);
}
int main(){
    freopen("match.in", "r", stdin);
    freopen("match.out", "w", stdout);
    scanf("%d%d", &T, &n);
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
    for(int j=1; j<=n; j++)
        scanf("%d", b+j);
    scanf("%d", &Q);
    while(Q--) slv();
    return 0;
}