#include <iostream>

using namespace std;
const int MAXN =3002;
int a[MAXN],b[MAXN];
int mxa[MAXN][MAXN], mxb[MAXN][MAXN];
unsigned long long dp[MAXN][MAXN];
int main()
{
    freopen("match.in", "r", stdin);
    freopen("match.out","w",stdout);
    ios::sync_with_stdio(false);
    int T, n;
    cin >> T >>n;
    for (int i =1;i<=n;i++){
        cin >>a[i];
        mxa[i][i]=a[i];
    }
    for (int i=1;i<=n;i++){
        cin >>b[i];
        mxb[i][i]=b[i];
    }
    for (int len=2; len<=n;len++){
        for (int i = 1; i+len-1<=n;i++){
            int j=i+len-1;
            mxa[i][j]=max(a[i], max(a[j], max (mxa[i][j-1], mxa[i+1][j])));
            mxb[i][j]=max(b[i], max(b[j], max (mxb[i][j-1], mxb[i+1][j])));
        }
    }
    int Q;
    cin >> Q;
    if (n > 30){for (int len=2; len<=n;len++){
        for (int i = 1; i+len-1<=n;i++){
            int j=i+len-1;
            for (int k=i+1;k<=n;k++) {

            }
        }
    }} else {
        while (Q--) {
            int l, r;
            cin >> l >> r;
            unsigned long long ans=0;
            for (int p1=l;p1<=r;p1++) {
                for (int q1=p1;q1<=r;q1++){
                    ans += mxa[p1][q1]*mxb[p1][q1];
                }
            }
            cout << ans <<'\n';
        }
    }
    return 0;
}

