//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[5][5];
    mat operator * (const mat &b) const {
        mat c;
        for(int i = 0; i < 5; ++ i){
            for(int j = 0; j < 5; ++ j){
                c.a[i][j] = a[i][0] * b.a[0][j]
                          + a[i][1] * b.a[1][j]
                          + a[i][2] * b.a[2][j]
                          + a[i][3] * b.a[3][j]
                          + a[i][4] * b.a[4][j];
            }
        }
        return c;
    }
} ini;
mat ma(ll x){
    mat k = ini;
    k.a[1][2] = k.a[4][0] = x;
    return k;
}
mat mb(ll x){
    mat k = ini;
    k.a[0][2] = k.a[4][1] = x;
    return k;
}
mat lsh(){
    mat k = ini;
    k.a[2][3] = 1;
    return k;
}
struct node{
    ll x, y, xy, all, cnt;
    bool flg = 0;
    mat tag;
    void mdf(mat val){
        ll tx = x, ty = y, txy = xy, tall = all;
        x = tx * val.a[0][0] + ty * val.a[1][0] + txy * val.a[2][0] + tall * val.a[3][0] + cnt * val.a[4][0];
        y = tx * val.a[0][1] + ty * val.a[1][1] + txy * val.a[2][1] + tall * val.a[3][1] + cnt * val.a[4][1];
        xy = tx * val.a[0][2] + ty * val.a[1][2] + txy * val.a[2][2] + tall * val.a[3][2] + cnt * val.a[4][2];
        all = tx * val.a[0][3] + ty * val.a[1][3] + txy * val.a[2][3] + tall * val.a[3][3] + cnt * val.a[4][3];
    }
} 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;
    for(int i = 0; i < 5; ++ i){
        for(int j = 0; j < 5; ++ j){
            t[p].tag.a[i][j] = (i == j);
        }
    }
}
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;
}
void build(int p, int l, int r){
    t[p].cnt = r - l + 1;
    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;
    // T = 0; n = 250000;
    for(int i = 0; i < 5; ++ i){
        for(int j = 0; j < 5; ++ j){
            ini.a[i][j] = (i == j);
        }
    }
    for(int i = 1; i <= n; ++ i){
        cin >> a[i];
        // a[i] = rand() % n + 1;
    }
    for(int i = 1; i <= n; ++ i){
        cin >> b[i];
        // b[i] = rand() % n + 1;
    }
    cin >> Q;
    // Q = 250000;
    for(int i = 1; i <= Q; ++ i){
        int l, r;
        cin >> l >> r;
        // l = 1, r = i;
        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;
}