#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define per(i, x, y) for (int i = x; i >= y; i--)
#define pb push_back
#define pii pair<int, int>
#define mkp make_pair
#define fi first
#define se second
using namespace std;

typedef unsigned long long ull;
int T, n, Q;

namespace bao1 {
const int N = 3e3 + 10;
ull a[N], b[N], mxa[N][N], mxb[N][N], v[N][N], s[N][N];
void solve() {
  rep(i, 1, n) {
    scanf("%llu", &a[i]);
  }
  rep(i, 1, n) {
    scanf("%llu", &b[i]);
  }
  rep(i, 1, n) {
    mxa[i][i] = a[i];
    rep(j, i + 1, n) {
      mxa[i][j] = max(mxa[i][j - 1], a[j]);
    }
  }
  rep(i, 1, n) {
    mxb[i][i] = b[i];
    rep(j, i + 1, n) {
      mxb[i][j] = max(mxb[i][j - 1], b[j]);
    }
  }
  rep(l, 1, n) {
    rep(r, l, n) {
      v[l][r] = mxa[l][r] * mxb[l][r];
      // printf("v[%d, %d] = %llu\n", l, r, v[l][r]);
    }
  }
  rep(l, 1, n) {
    rep(r, 1, n) {
      s[l][r] = s[l][r - 1] + s[l - 1][r] - s[l - 1][r - 1] + v[l][r];
    }
  }
  scanf("%d", &Q);
  while (Q--) {
    int l, r; scanf("%d%d", &l, &r);
    printf("%llu\n", s[r][r] - s[l - 1][r] - s[r][l - 1] + s[l - 1][l - 1]);
  }
}
}

namespace bao2 {
#define ls (x << 1)
#define rs (x << 1 | 1)
const int N = 2.5e5 + 10;
ull a[N], b[N];
ull sa[N << 2], sb[N << 2], sum[N << 2], tag_a[N << 2], tag_b[N << 2];

void upd(int x) {
  sa[x] = sa[x << 1] + sa[x << 1 | 1];
  sb[x] = sb[x << 1] + sb[x << 1 | 1];
  sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
void psd(int x, int l, int r) {
  int mid = (l + r) >> 1;
  if (tag_a[x]) {
    tag_a[ls] = tag_a[rs] = tag_a[x];
    sa[ls] = tag_a[x] * (mid - l + 1);
    sa[rs] = tag_a[x] * (r - mid);
    sum[ls] = tag_a[x] * sb[ls];
    sum[rs] = tag_a[x] * sb[rs];
    tag_a[x] = 0;
  }
  if (tag_b[x]) {
    tag_b[ls] = tag_b[rs] = tag_b[x];
    sb[ls] = tag_b[x] * (mid - l + 1);
    sb[rs] = tag_b[x] * (r - mid);
    sum[ls] = tag_b[x] * sa[ls];
    sum[rs] = tag_b[x] * sa[rs];
    tag_b[x] = 0;
  }
}
void cover_a(int x, int l, int r, int lx, int rx, ull v) {
  if (lx <= l && r <= rx) {
    sa[x] = 1ull * v * (r - l + 1);
    sum[x] = sb[x] * v;
    tag_a[x] = v;
    return;
  }
  int mid = (l + r) >> 1;
  psd(x, l, r);
  if (lx <= mid) cover_a(x << 1, l, mid, lx, rx, v);
  if (rx > mid) cover_a(x << 1 | 1, mid + 1, r, lx, rx, v);
  upd(x);
}
void cover_b(int x, int l, int r, int lx, int rx, ull v) {
  if (lx <= l && r <= rx) {
    sb[x] = 1ull * v * (r - l + 1);
    sum[x] = sa[x] * v;
    tag_b[x] = v;
    return;
  }
  int mid = (l + r) >> 1;
  psd(x, l, r);
  if (lx <= mid) cover_b(x << 1, l, mid, lx, rx, v);
  if (rx > mid) cover_b(x << 1 | 1, mid + 1, r, lx, rx, v);
  upd(x);
}
ull qry(int x, int l, int r, int lx, int rx) {
  if (lx <= l && r <= rx) return sum[x];
  int mid = (l + r) >> 1;
  psd(x, l, r);
  if (lx > mid) return qry(rs, mid + 1, r, lx, rx);
  if (rx <= mid) return qry(ls, l, mid, lx, rx);
  return qry(ls, l, mid, lx, rx) + qry(rs, mid + 1, r, lx, rx);
}
int sta[N], tpa;
int stb[N], tpb;
void solve() {
  rep(i, 1, n) {
    scanf("%llu", &a[i]);
  }
  rep(i, 1, n) {
    scanf("%llu", &b[i]);
  }
  scanf("%d", &Q);
  while (Q--) {
    int l, r; scanf("%d%d", &l, &r);
    ull ans = 0;
    tpa = tpb = 0;
    rep(i, l, r) {
      while (tpa && a[sta[tpa]] <= a[i]) --tpa;
      cover_a(1, 1, n, max(sta[tpa] + 1, l), i, a[i]);
      sta[++tpa] = i;

      while (tpb && b[stb[tpb]] <= b[i]) --tpb;
      cover_b(1, 1, n, max(stb[tpb] + 1, l), i, b[i]);
      stb[++tpb] = i;
      
      ans += qry(1, 1, n, l, i);
    }
    printf("%llu\n", ans);
  }
}
}

int main() {
  freopen("match.in", "r", stdin);
  freopen("match.out", "w", stdout);

  scanf("%d%d", &T, &n);
  if (T <= 5) {
    bao1::solve();
    return 0;
  }
  bao2::solve();
  return 0;
}
