#include <bits/stdc++.h>

#define Deb std::cerr
#define Delin Deb << "[Debug] at Line " << __LINE__
#define Debug Delin << " : "
#define Deline Delin << std::endl

namespace Mod {

template <typename Type, Type P, typename MulType>
class ModInt {
   public:
    Type x;
    using Self = ModInt<Type, P, MulType>;
    ModInt(int a = 0) : x(a) {}
    explicit operator Type() { return x; }
    friend inline Self operator+(Self a, Self b) { return (a.x += b.x) >= P ? a.x - P : a.x; }
    friend inline Self operator-(Self a, Self b) { return (a.x -= b.x) < 0 ? a.x + P : a.x; }
    friend inline Self operator*(Self a, Self b) { return MulType(a.x) * b.x % P; }
    friend inline Self &operator+=(Self &a, Self b) { return (a.x += b.x) >= P ? a.x -= P, a : a; }
    friend inline Self &operator-=(Self &a, Self b) { return (a.x -= b.x) < 0 ? a.x += P, a : a; }
    friend inline Self &operator*=(Self &a, Self b) { return a = MulType(a.x) * b.x % P; }
    template <typename ExpType>
    inline Self Pow(ExpType Exp) {
        Self Base(*this), Ans(1);
        while (Exp) {
            if (Exp & 1) Ans *= Base;
            Base *= Base, Exp >>= 1;
        }
        return Ans;
    }
    inline Self Inv() { return Pow(P - 2); }
};

};

using int64 = long long;
using uint64 = unsigned long long;
using int128 = __int128;

using MInt1 = Mod::ModInt<int, 998244353, long long>;
using MInt2 = Mod::ModInt<int, 1000000007, long long>;
using MInt3 = Mod::ModInt<int, 1000000009, long long>;

struct MInt {
    MInt1 a1;
    MInt2 a2;
    MInt3 a3;
    MInt(int a = 0) : a1(a), a2(a), a3(a) {}
    MInt(MInt1 x, MInt2 y, MInt3 z) : a1(x), a2(y), a3(z) {}
    explicit operator int() { return int(a1); }
    friend inline MInt operator+(MInt a, MInt b) { return MInt(a.a1 + b.a1, a.a2 + b.a2, a.a3 + b.a3); }
    friend inline MInt operator-(MInt a, MInt b) { return MInt(a.a1 - b.a1, a.a2 - b.a2, a.a3 - b.a3); }
    friend inline MInt operator*(MInt a, MInt b) { return MInt(a.a1 * b.a1, a.a2 * b.a2, a.a3 * b.a3); }
    friend inline MInt &operator+=(MInt &a, MInt b) { return a.a1 += b.a1, a.a2 += b.a2, a.a3 += b.a3, a; }
    friend inline MInt &operator-=(MInt &a, MInt b) { return a.a1 -= b.a1, a.a2 -= b.a2, a.a3 -= b.a3, a; }
    friend inline MInt &operator*=(MInt &a, MInt b) { return a.a1 *= b.a1, a.a2 *= b.a2, a.a3 *= b.a3, a; }
    inline MInt Inv() { return MInt(a1.Inv(), a2.Inv(), a3.Inv()); }
};

const int N = 250005;
const int M = 524288;
const int N1 = 3005;

int LTime[M], FTime[M];
MInt LSum[M], LVal[M], TagS[M], TagV[M];

inline MInt GetVal(int u, int c) {
    return LSum[u] + (c - LTime[u] + 1) * LVal[u];
}

inline void Mul(int u, MInt v, int c) {
    // Debug << u << " = " << LTime[u] << ' ' << FTime[u] <<
    // ' ' << int(LSum[u]) << ' ' << int(LVal[u]) << ' ' << int(TagS[u]) << ' ' << int(TagV[u]) << std::endl;
    // Debug << "Mul(" << u << ", " << int(v) << ", " << c << ")" << std::endl;
    LSum[u] += LVal[u] * (c - LTime[u]);
    TagS[u] += TagV[u] * (c - LTime[u]);
    LVal[u] *= v;
    TagV[u] *= v;
    LTime[u] = c;
    // Debug << u << " = " << LTime[u] << ' ' << FTime[u] <<
    // ' ' << int(LSum[u]) << ' ' << int(LVal[u]) << ' ' << int(TagS[u]) << ' ' << int(TagV[u]) << std::endl;
}

inline void PushDown(int u, int v, int c) {
    LSum[v] += LVal[v] * (FTime[u] - LTime[v]) + TagS[u] * LVal[v];
    TagS[v] += TagV[v] * (FTime[u] - LTime[v]) + TagS[u] * TagV[v];
    LVal[v] *= TagV[u];
    TagV[v] *= TagV[u];
    LTime[v] = LTime[u];
}

inline void PushDown(int u, int c) {
    PushDown(u, u << 1, c);
    PushDown(u, u << 1 | 1, c);
    FTime[u] = c, TagV[u] = 1, TagS[u] = 0;
}

inline void PushUp(int u, int c) {
    LSum[u] = GetVal(u << 1, c) + GetVal(u << 1 | 1, c);
    FTime[u] = c + 1, TagV[u] = 1, TagS[u] = 0;
    LTime[u] = c + 1, LVal[u] = LVal[u << 1] + LVal[u << 1 | 1];
}

inline void Init(int u, int l, int r) {
    if (l == r) return void((LVal[u] = 1, TagV[u] = 1));
    int Mid = l + r >> 1;
    Init(u << 1, l, Mid);
    Init(u << 1 | 1, Mid + 1, r);
    PushUp(u, 0);
}

inline void Update(int u, int l, int r, int L, int R, MInt v, int c) {
    if (l >= L && r <= R) return void(Mul(u, v, c));
    int Mid = l + r >> 1;
    PushDown(u, c);
    if (L <= Mid) Update(u << 1, l, Mid, L, R, v, c);
    if (R > Mid) Update(u << 1 | 1, Mid + 1, r, L, R, v, c);
    PushUp(u, c);
}

inline MInt Query(int u, int l, int r, int L, int R, int c) {
    if (l >= L && r <= R) return GetVal(u, c);
    int Mid = l + r >> 1;
    MInt Ans(0);
    PushDown(u, c);
    if (L <= Mid) Ans += Query(u << 1, l, Mid, L, R, c);
    if (R > Mid) Ans += Query(u << 1 | 1, Mid + 1, r, L, R, c);
    return Ans;
}

inline void QDebug(int u, int l, int r) {
    // Debug << u << " [" << l << ", " << r << "] = " << LTime[u] << ' ' << FTime[u] <<
    // ' ' << int(LSum[u]) << ' ' << int(LVal[u]) << ' ' << int(TagS[u]) << ' ' << int(TagV[u]) << std::endl;
    if (l == r) return;
    int Mid = l + r >> 1;
    QDebug(u << 1, l, Mid);
    QDebug(u << 1 | 1, Mid + 1, r);
}

int Max[M];

inline int GetMax(int x, int y, int *a) { return a[x] > a[y] ? x : y; }

inline void ABuild(int u, int l, int r, int *a) {
    if (l == r) return void(Max[u] = l);
    int Mid = l + r >> 1;
    ABuild(u << 1, l, Mid, a);
    ABuild(u << 1 | 1, Mid + 1, r, a);
    Max[u] = GetMax(Max[u << 1], Max[u << 1 | 1], a);
}

inline int AQuery(int u, int l, int r, int L, int R, int *a) {
    if (l >= L && r <= R) return Max[u];
    int Mid = l + r >> 1, Ans = 0;
    if (L <= Mid) Ans = GetMax(Ans, AQuery(u << 1, l, Mid, L, R, a), a);
    if (R > Mid) Ans = GetMax(Ans, AQuery(u << 1 | 1, Mid + 1, r, L, R, a), a);
    return Ans;
}

int T, n, q;
int a[N], b[N];
__int128 R[N1][N1];

MInt Ans[N];

using Tuple = std::tuple<int, int, int, int, MInt, int>;

std::vector<Tuple> Opers;

inline void Solve(int l, int r, int *a) {
    if (l > r) return;
    int o = AQuery(1, 1, n, l, r, a);
    for (int i = l; i <= o; ++i) {
        for (int j = o; j <= r; ++j) R[i][j] *= a[o];
    }
    // Debug << "Square [" << l << ", " << o << "] [" << o << ", " << r << "] * " << a[o] << std::endl;
    // Opers.emplace_back(o, 1, l, o, MInt(a[o]), 0);
    // Opers.emplace_back(r + 1, 1, l, o, MInt(a[o]).Inv(), 0);
    Solve(l, o - 1, a), Solve(o + 1, r, a);
}

int main() {
    freopen("match.in", "r", stdin);
    freopen("match.out", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    std::cin >> T >> n;
    for (int i = 1; i <= n; ++i) std::cin >> a[i];
    for (int i = 1; i <= n; ++i) std::cin >> b[i];
    memset(R, 0, sizeof(R));
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) R[i][j] = 1;
    }
    ABuild(1, 1, n, a), Solve(1, n, a);
    ABuild(1, 1, n, b), Solve(1, n, b);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) R[i][j] += R[i][j - 1];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) R[i][j] += R[i - 1][j];
    }
    std::cin >> q;
    for (int i = 1, l, r; i <= q; ++i) {
        std::cin >> l >> r, --l;
        std::cout << uint64((R[r][r] - R[l][r] - R[r][l] + R[l][l]) & UINT64_MAX) << '\n';
        // Ans[i] -= int64(r - l) * (r - l + 1) / 2;
        // Opers.emplace_back(l - 1, 2, l, r, MInt(0) - 1, i);
        // Opers.emplace_back(r, 2, l, r, 1, i);
    }
    // std::sort(Opers.begin(), Opers.end(), [](Tuple a, Tuple b) {
    //     return std::get<0>(a) == std::get<0>(b) ? std::get<1>(a) < std::get<1>(b)
    //                                             : std::get<0>(a) < std::get<0>(b);
    // });
    // Init(1, 1, n);
    // for (auto [c, o, l, r, v, Id] : Opers) {
    //     // Debug << "Oper: Type" << o << " Time#" << c << " [" << l << ", " << r << "] Mul " << int(v.a1) << " #" << Id << std::endl;
    //     if (o == 1) {
    //         Update(1, 1, n, l, r, v, c);
    //     } else {
    //         MInt Tmp = Query(1, 1, n, l, r, c);
    //         Ans[Id] += v * Tmp;
    //         // Debug << "return " << int(Tmp) << std::endl;
    //     }
    //     QDebug(1, 1, n);
    // }
    // for (int i = 1; i <= q; ++i) std::cout << int(Ans[i].a1) << '\n';
    return 0;
}
