#include <bits/stdc++.h>

using u64 = uint64_t;

class seq {
  int n;
  std::vector<int> lg;
  std::vector<u64> p;
  std::vector<std::vector<int>> st;
  std::vector<int> lp, rp;
  std::vector<u64> lsub, rsub, suml, sumli, sumr, sumri;

  int max(int x, int y) const {
    return p[x] < p[y] ? y : x;
  }

  u64 init(int l, int r) {
    if (l > r) {
      return 0;
    }
    for (int i = l; i <= r; ++i) {
      lp[i] = l - 1;
      rp[i] = r + 1;
    }
    int mid = range_max(l, r);
    lsub[mid] = init(l, mid - 1);
    rsub[mid] = init(mid + 1, r);
    return lsub[mid] + rsub[mid] + p[mid] * (mid - l + 1) * (r - mid + 1);
  }

public:
  seq(const std::vector<u64> &a) : n(a.size()), lg(n + 1), p(a) {
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) {
      lg[i] = lg[i >> 1] + 1;
    }
    st.assign(lg[n] + 1, std::vector<int>(n));
    for (int i = 0; i < n; ++i) {
      st[0][i] = i;
    }
    for (int i = 0; i < lg[n]; ++i) {
      for (int j = 0; j + (1 << (i + 1)) <= n; ++j) {
        st[i + 1][j] = max(st[i][j], st[i][j + (1 << i)]);
      }
    }
    lp.resize(n);
    rp.resize(n);
    lsub.resize(n);
    rsub.resize(n);
    suml.resize(n);
    sumli.resize(n);
    sumr.resize(n);
    sumri.resize(n);
    init(0, n - 1);
    for (int i = 0; i < n; ++i) {
      if (lp[i] != -1) {
        suml[i] = suml[lp[i]];
        sumli[i] = sumli[lp[i]];
      }
      suml[i] += p[i] * (i - lp[i]);
      sumli[i] += p[i] * (i - lp[i]) * i + lsub[i];
    }
    for (int i = n - 1; i >= 0; --i) {
      if (rp[i] != -1) {
        sumr[i] = sumr[rp[i]];
        sumri[i] = sumri[rp[i]];
      }
      sumr[i] += p[i] * (rp[i] - i);
      sumri[i] += p[i] * (rp[i] - i) * i + rsub[i];
    }
  }

  int range_max(int l, int r) const {
    ++r;
    int t = lg[r - l];
    return max(st[t][l], st[t][r - (1 << t)]);
  }

  u64 query(int l, int r) const {
    if (l > r) {
      return 0;
    }
    int mid = range_max(l, r);
    return (suml[r] - suml[mid]) * (r + 1) - (sumli[r] - sumli[mid]) +
           (sumri[l] - sumri[mid]) - (sumr[l] - sumr[mid]) * (l - 1) +
           p[mid] * (mid - l + 1) * (r - mid + 1);
  }
};

int main() {
  std::ifstream fin("match.in");
  std::ofstream fout("match.out");

  int id, n;
  fin >> id >> n;
  std::vector<u64> a(n);
  for (int i = 0; i < n; ++i) {
    fin >> a[i];
  }
  std::vector<u64> b(n);
  for (int i = 0; i < n; ++i) {
    fin >> b[i];
  }
  seq B(b);

  std::vector<int> sta;
  std::vector<int> lp(n, -1), rp(n, n);
  for (int i = 0; i < n; ++i) {
    while (!sta.empty() && a[sta.back()] < a[i]) {
      rp[sta.back()] = i;
      sta.pop_back();
    }
    if (!sta.empty()) {
      lp[i] = sta.back();
    }
    sta.push_back(i);
  }
  std::vector<int> ord(n);
  std::iota(ord.begin(), ord.end(), 0);
  std::sort(ord.begin(), ord.end(), [&](int i, int j) {
    return a[i] < a[j];
  });
  std::vector<u64> bq(n);
  std::vector<u64> sub(n);
  for (int i = 0; i < n; ++i) {
    bq[i] = B.query(lp[i] + 1, rp[i] - 1);
    sub[i] = bq[i] * a[i];
  }
  std::vector<u64> lsub(n), rsub(n);
  for (int i : ord) {
    sub[i] += lsub[i] + rsub[i];
    int fa = lp[i] != -1 && (rp[i] == n || a[lp[i]] < a[rp[i]]) ? lp[i] : rp[i];
    if (fa == n) {
      continue;
    }
    sub[fa] -= bq[i] * a[fa];
    if (fa < i) {
      rsub[fa] = sub[i];
    } else {
      lsub[fa] = sub[i];
    }
  }

  int q;
  fin >> q;
  while (q--) {
    int l, r;
    fin >> l >> r;
    --l, --r;
    u64 ans = 0;
    u64 sl = 0;
    int p = l;
    while (rp[p] <= r) {
      ans -= (sl + rsub[p]) * a[p];
      sl = B.query(l, rp[p] - 1);
      ans += sl * a[p];
      p = rp[p];
    }
    u64 sr = 0;
    p = r;
    while (lp[p] >= l) {
      ans -= (sr + lsub[p]) * a[p];
      sr = B.query(lp[p] + 1, r);
      ans += sr * a[p];
      p = lp[p];
    }
    ans -= (sl + sr) * a[p];
    ans += B.query(l, r) * a[p];
    fout << ans << "\n";
  }
}
