// 抽象数据结构，好文明！
#include <bits/stdc++.h>

using namespace std;

#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl

using u64 = unsigned long long;

const int N = 2.5e5 + 10;

int read() {
  int x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
  return x * f;
}

struct M {
  u64 cx, cy, mxy, mx, my, m;
  M() : cx(), cy(), mxy(), mx(), my(), m() {}
  M(u64 a, u64 b, u64 c, u64 d, u64 e, u64 f) : cx(a), cy(b), mxy(c), mx(d), my(e), m(f) {}
  friend M operator * (M a, M b) {
    if (a.cx && a.cy) {
      a.m += b.mxy * a.cx * a.cy + b.mx * a.cy + b.my * a.cx + b.m;
    }
    else if (a.cx) {
      a.my += b.mxy * a.cx + b.my;
      a.m += b.mx * a.cx + b.m;
    }
    else if (a.cy) {
      a.mx += b.mxy * a.cy + b.my;
      a.m += b.my * a.cy + b.m;
    }
    else {
      a.mxy += b.mxy;
      a.mx += b.mx;
      a.my += b.my;
      a.m += b.m;
    }
    if (b.cx) a.cx = b.cx;
    if (b.cy) a.cy = b.cy;
    return a;
  }
} ;

struct D {
  u64 sxy, sx, sy, s, len;
  D() : sxy(), sx(), sy(), s(), len() {}
  D(u64 a, u64 b, u64 c, u64 d, u64 e) : sxy(a), sx(b), sy(c), s(d), len(e) {}
  friend D operator + (D a, D b) {
    return D(a.sxy + b.sxy, a.sx + b.sx, a.sy + b.sy, a.s + b.s, a.len + b.len);
  }
  friend D operator * (D a, M b) {
    a.s += a.sxy * b.mxy + a.sx * b.mx + a.sy * b.my + a.len * b.m;
    if (b.cx && b.cy) {
      a.sxy = b.cx * b.cy * a.len;
      a.sx = b.cx * a.len;
      a.sy = b.cy * a.len;
    }
    else if (b.cx) {
      a.sxy = b.cx * a.sy;
      a.sx = b.cx * a.len;
    }
    else if (b.cy) {
      a.sxy = b.cy * a.sx;
      a.sy = b.cy * a.len;
    }
    return a;
  }
} ;

int tc, n, m, p[N], q[N], stp[N], stq[N], tp, tq;
vector <pair <int, int>> qry[N];
u64 ans[N];

#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)

D dat[N << 2];
M laz[N << 2];

void down(int u, M k) {
  dat[u] = dat[u] * k;
  laz[u] = laz[u] * k;
}

void pushdown(int u) {
  down(ls, laz[u]), down(rs, laz[u]);
  laz[u] = M();
}

void maintain(int u) {
  dat[u] = dat[ls] + dat[rs];
}

void build(int u = 1, int l = 1, int r = n) {
  if (l == r) return dat[u].len = 1, void();
  build(ls, l, mid), build(rs, mid + 1, r);
  maintain(u);
}

void modify(int ml, int mr, M k, int u = 1, int l = 1, int r = n) {
  if (ml <= l && r <= mr) return down(u, k), void();
  pushdown(u);
  if (ml <= mid) modify(ml, mr, k, ls, l, mid);
  if (mr > mid) modify(ml, mr, k, rs, mid + 1, r);
  maintain(u);
}

D query(int ql, int qr, int u = 1, int l = 1, int r = n) {
  if (ql <= l && r <= qr) return dat[u];
  pushdown(u);
  D res = D();
  if (ql <= mid) res = res + query(ql, qr, ls, l, mid);
  if (qr > mid) res = res + query(ql, qr, rs, mid + 1, r);
  return res;
}

#undef ls
#undef rs
#undef mid

int main() {
  tc = read(), n = read();
  rep(i, 1, n) p[i] = read();
  rep(i, 1, n) q[i] = read();
  m = read();
  rep(i, 1, m) {
    int l = read(), r = read();
    qry[r].emplace_back(make_pair(l, i));
  }
  build();
  rep(i, 1, n) {
    while (tp && p[stp[tp]] < p[i]) --tp;
    modify(stp[tp] + 1, i, M(p[i], 0, 0, 0, 0, 0));
    stp[++tp] = i;
    while (tq && q[stq[tq]] < q[i]) --tq;
    modify(stq[tq] + 1, i, M(0, q[i], 0, 0, 0, 0));
    stq[++tq] = i;
    modify(1, i, M(0, 0, 1, 0, 0, 0));
    for (auto [l, id] : qry[i]) ans[id] = query(l, i).s;
  }
  rep(i, 1, m) printf("%llu\n", ans[i]);
  return 0;
}