//qoj5165
#include <bits/stdc++.h>
using namespace std;

const int N = 2.5e5 + 10;
int T, n, Q, sa[N], sb[N];
typedef unsigned long long ll;
ll a[N], b[N], ans[N];
vector<pair<int, int> > q[N];

struct mat{
    ll A, B, C, D, E, F, G, H, I;
    mat operator * (const mat &b) const {
        mat c;
        c.A = A + b.A;
        c.B = B + b.B + A * b.E;
        c.C = C + b.C;
        c.D = D + b.D + C * b.E;
        c.E = E + b.E;
        c.F = F + b.F;
        c.G = G + b.G;
        c.H = H + b.H + F * b.A + G * b.C;
        c.I = I + b.I + F * b.B + G * b.D + H * b.E;
        return c;
    }
} ini;
mat ma(ll x){
    mat k = ini;
    k.C = k.F = x;
    return k;
}
mat mb(ll x){
    mat k = ini;
    k.A = k.G = x;
    return k;
}
mat lsh(){
    mat k = ini;
    k.E = 1;
    return k;
}
struct node{
    ll x, y, xy, all, cnt;
    bool flg;
    mat tag;
    void mdf(mat val){
        all = x * val.B + y * val.D + xy * val.E + all + cnt * val.I;
        xy = x * val.A + y * val.C + xy + cnt * val.H;
        x += cnt * val.F;
        y += cnt * val.G;
    }
} t[N*4];
void psd(int p){
    if(!t[p].flg){
        return;
    }
    t[p].flg = 0;
    t[p<<1].mdf(t[p].tag);
    t[p<<1|1].mdf(t[p].tag);
    t[p<<1].tag = t[p<<1].tag * t[p].tag;
    t[p<<1|1].tag = t[p<<1|1].tag * t[p].tag;
    t[p<<1].flg = t[p<<1|1].flg = 1;
    t[p].tag = ini;
}
void upd(int p){
    t[p].x = t[p<<1].x + t[p<<1|1].x;
    t[p].y = t[p<<1].y + t[p<<1|1].y;
    t[p].xy = t[p<<1].xy + t[p<<1|1].xy;
    t[p].all = t[p<<1].all + t[p<<1|1].all;
    t[p].cnt = t[p<<1].cnt + t[p<<1|1].cnt;
}
void build(int p, int l, int r){
    t[p].cnt = r - l + 1;
    t[p].flg = 0;
    if(l != r){
        int mid = l + r >> 1;
        build(p<<1, l, mid);
        build(p<<1|1, mid+1, r);
        upd(p);
    }
}
void add(int p, int l, int r, int ql, int qr, mat val){
    if(qr < l || r < ql){
        return;
    } else if(ql <= l && r <= qr){
        t[p].mdf(val);
        t[p].tag = t[p].tag * val;
        t[p].flg = 1;
    } else {
        int mid = l + r >> 1;
        psd(p);
        add(p<<1, l, mid, ql, qr, val);
        add(p<<1|1, mid+1, r, ql, qr, val);
        upd(p);
    }
}
ll ask(int p, int l, int r, int ql, int qr){
    if(qr < l || r < ql){
        return 0;
    } else if(ql <= l && r <= qr){
        return t[p].all;
    } else {
        int mid = l + r >> 1;
        psd(p);
        return ask(p<<1, l, mid, ql, qr) + ask(p<<1|1, mid+1, r, ql, qr);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> T >> n;
    for(int i = 1; i <= n; ++ i){
        cin >> a[i];
    }
    for(int i = 1; i <= n; ++ i){
        cin >> b[i];
    }
    cin >> Q;
    for(int i = 1; i <= Q; ++ i){
        int l, r;
        cin >> l >> r;
        q[r].emplace_back(l, i);
    }
    build(1, 1, n);
    int ta = 0, tb = 0;
    for(int i = 1; i <= n; ++ i){
        int la = i, lb = i;
        add(1, 1, n, i, i, ma(a[i]));
        while(ta && a[sa[ta]] <= a[i]){
            add(1, 1, n, sa[ta], la-1, ma(a[i]-a[sa[ta]]));
            la = sa[ta];
            -- ta;
        }
        a[la] = a[i];
        sa[++ta] = la;
        add(1, 1, n, i, i, mb(b[i]));
        while(tb && b[sb[tb]] <= b[i]){
            add(1, 1, n, sb[tb], lb-1, mb(b[i]-b[sb[tb]]));
            lb = sb[tb];
            -- tb;
        }
        b[lb] = b[i];
        sb[++tb] = lb;
        add(1, 1, n, 1, n, lsh());
        for(auto j : q[i]){
            ans[j.second] = ask(1, 1, n, j.first, i);
        }
    }
    for(int i = 1; i <= Q; ++ i){
        cout << ans[i] << '\n';
    }
    return 0;
}