#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
using ull = unsigned long long;
int SubtaskID,n,a[N],b[N];
namespace Subtask1
{
    int mxa[N][N],mxb[N][N];ull ans[N][N];
    int main ()
    {
        for (int i = 1;i <= n;i++)
            for (int j = i;j <= n;j++)
                mxa[i][j] = max(a[j],mxa[i][j - 1]),mxb[i][j] = max(mxb[i][j - 1],b[j]);
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= n;j++) { ans[i][j] = mxa[i][j] * 1ll * mxb[i][j]; }
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= n;j++) ans[i][j] += ans[i][j - 1];
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= n;j++) ans[i][j] += ans[i - 1][j];
        int q;cin >> q;
        while (q--)
        {
            int l,r;cin >> l >> r;cout << ans[r][r] - ans[l - 1][r] - ans[r][l - 1] + ans[l - 1][l - 1] << endl;
        }
        return 0;
    }
}
int main ()
{
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    ios::sync_with_stdio(false);
    cin >> SubtaskID >> n;for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++) cin >> b[i];
    if (SubtaskID <= 5) return Subtask1::main();
    return 0;
}