#include <iostream>
#include <cstdio>
#include <algorithm>

constexpr int N = 3005;

int type, n, m;
int a[N], b[N];
int lg[N], ma[N][20], mb[N][20];
unsigned long long f[N][N];

int main() {
    freopen("match.in", "r", stdin);
    freopen("match.out", "w", stdout);
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
    std::cin >> type >> n;
    for (int i = 1; i <= n; ++i) std::cin >> a[i], ma[i][0] = a[i];
    for (int i = 1; i <= n; ++i) std::cin >> b[i], mb[i][0] = b[i];
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= lg[n]; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
            ma[j][i] = std::max(ma[j][i - 1], ma[j + (1 << (i - 1))][i - 1]);
            mb[j][i] = std::max(mb[j][i - 1], mb[j + (1 << (i - 1))][i - 1]);
        }
    auto query = [&](int l, int r) {
        int k = lg[r - l + 1];
        return static_cast<unsigned long long>(std::max(ma[l][k], ma[r - (1 << k) + 1][k])) * std::max(mb[l][k], mb[r - (1 << k) + 1][k]);
    };
    for (int len = 1; len <= n; ++len)
        for (int i = 1, j = len; j <= n; ++i, ++j)
            f[i][j] = f[i + 1][j] + f[i][j - 1] - f[i + 1][j - 1] + query(i, j);
    std::cin >> m;
    while (m--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << f[l][r] << '\n';
    }
    return 0;
}
