#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int read() {
    char c; bool f = true;
    while (!isdigit(c = getchar())) f = c != '-';
    int x = c ^ 48;
    while (isdigit(c = getchar())) x = x * 10 + (c ^ 48);
    return f ? x : -x;
}

const int N = 5010;

int T, n;
int a[N], b[N], q, l, r;
int av[N][N], bv[N][N];

typedef unsigned long long ull;

int main() {
    freopen("match.in", "r", stdin);
    freopen("match.out", "w", stdout);
    T = read(); n = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }
    for (int i = 1; i <= n; i++) {
        b[i] = read();
    }
    for (int i = 1; i <= n; i++) {
        av[i][i] = a[i];
        bv[i][i] = b[i];
        for (int j = i + 1; j <= n; j++) {
            av[i][j] = max(av[i][j - 1], a[j]);
            bv[i][j] = max(bv[i][j - 1], b[j]);
        }
    }
    q = read();
    while (q--) {
        l = read();
        r = read();
        ull ans = 0;
        for (int p = l; p <= r; p++) {
            for (int q = p; q <= r; q++) {
                ans += 1ull * av[p][q] * bv[p][q];
            }
        }
        cout << ans << endl;
    }
    return 0;
}
/*
0 2
2 1
1 2
1
1 2
*/