#include <bits/stdc++.h>

template<class T, class...Cond>
using require_ = std::enable_if_t<std::__and_<T, Cond...>::value, bool>;

template<class T, require_<std::is_signed<T>> = true>
void read(T & x) {
    x = 0;
    bool f = false;
    char c = getchar();
    while (!isdigit(c)) f |= (c == '-'), c = getchar();
    while (isdigit(c)) x = (x * 10) - (c ^ 48), c = getchar();
    x = (f ? x : -x);
}

template<class T, require_<std::is_unsigned<T>> = true>
void read(T & x) {
    x = 0;
    char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
}

template<class T, class...Args>
void read(T & x, Args&...args) {
    read(x);
    read(args...);
}

using ull = unsigned long long;

constexpr int N = 3e5 + 5;

int a[2][N];
int st[2][N][24];
int test_case, n;
int lg[N];

void get_mx(int o) {
    auto & stt = st[o];
    auto & v = a[o];

    for (int i = 1; i <= n; ++ i) {
        stt[i][0] = v[i];
    }

    for (int j = 1; j <= lg[n]; ++ j) {
        for (int i = 1; i <= n; ++ i) {
            stt[i][j] = std::max(stt[i][j - 1], stt[std::min(n, i + (1 << (j - 1)))][j - 1]);
        }
    }

    // for (int i = 0; i <= 20; ++ i) {
    //     for (int j = 1; j <= n; ++ j) {
    //         printf("%d ", stt[j][i]);
    //     }
    //     puts("");
    // }
}

inline int ask(int o, int l, int r) {
    if (l > r) {
        return 0;
    }
    int p = lg[r - l + 1];
    return std::max(st[o][l][p], st[o][r - (1 << p) + 1][p]);
}

void solve() {
    read(test_case, n);
    for (int i = 1; i <= n; ++ i) {
        read(a[0][i]);
    }
    for (int i = 1; i <= n; ++ i) {
        read(a[1][i]);
    }

    lg[1] = 0;
    for (int i = 2; i <= n; ++ i) {
        lg[i] = lg[i >> 1] + 1;
    }

    get_mx(0);
    get_mx(1);

    int Q;
    read(Q);

    if (test_case <= 2) {
        while (Q --) {
            int l, r;
            read(l, r);
            ull ans = 0;
            for (int i = l; i <= r; ++ i) {
                for (int j = i; j <= r; ++ j) {
                    ans += 1ull * ask(0, i, j) * ask(1, i, j);
                }
            }
            printf("%llu\n", ans);
        }
    } else if (test_case <= 5) {
        std::vector<std::vector<ull>> f(n + 3, std::vector<ull>(n + 3));
        auto suf = f;

        for (int i = n; i >= 1; -- i) {
            for (int j = i; j <= n; ++ j) {
                suf[i][j] = suf[i + 1][j] + 1ull * ask(0, i, j) * ask(1, i, j);
            }
        }

        for (int i = 1; i <= n; ++ i) {
            f[i][i] = 1ull * a[0][i] * a[1][i];
        }

        for (int i = 1; i <= n; ++ i) {
            for (int j = i + 1; j <= n; ++ j) {
                f[i][j] = f[i][j - 1] + suf[i][j];
            }
        }

        // for (int i = 1; i <= n; ++ i) {
        //     for (int j = 1; j <= n; ++ j) {
        //         printf("%llu ", f[i][j]);
        //     }
        //     puts("");
        // }

        while (Q --) {
            int l, r;
            read(l, r);
            printf("%llu\n", f[l][r]);
        }
    } else if (test_case <= 13) {
        std::vector<ull> f(n + 3);

        while (Q --) {
            f.clear();
            f.resize(n + 3);

            int l, r;
            read(l, r);
            f[l] = 1ull * a[0][l] * a[1][l];
            for (int j = l + 1; j <= r; ++ j) {
                ull tmp = 0;
                for (int i = l; i <= j; ++ i) {
                    tmp += 1ull * ask(0, i, j) * ask(1, i, j);
                }
                f[j] = f[j - 1] + tmp;
            }
            printf("%llu\n", f[r]);
        }
    }
}

int main() {
    std::freopen("match.in", "r", stdin);
    std::freopen("match.out", "w", stdout);

    int T = 1;
    for (int t = 1; t <= T; ++ t) {
        solve();
    }
    return 0;
}
/*
0 2
2 1
1 2
1
1 2
*/
/*
(0 3
2 1 3
1 2 3
3
1 2
2 3
1 3
)
8
20
35
*/
