#include <bits/stdc++.h>

using i64 = long long;

constexpr int inf = 1e9;

struct Node {
    Node *l, *r;
    int v = inf;
};
void modify(Node *&u, int l, int r, int p, int x) {
    if (!u) {
        u = new Node{};
    }
    u->v = x;
    if (r - l == 1) {
        return;
    }
    int m = (l + r) / 2;
    if (p < m) {
        modify(u->l, l, m, p, x);
    } else {
        modify(u->r, m, r, p, x);
    }
}
int query(Node *u, int l, int r, int ql, int qr) {
    if (!u || r <= ql || qr <= l) {
        return inf;
    }
    if (ql <= l && r <= qr) {
        return u->v;
    }
    int m = (l + r) / 2;
    return std::min(query(u->l, l, m, ql, qr), query(u->r, m, r, ql, qr));
}

void solve() {
    int n, q;
    std::cin >> n >> q;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    std::vector<int> b(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> b[i];
    }

    std::vector<std::vector<std::pair<int, int>>> qry(n);
    for (int i = 0; i < q; ++i) {
        int l, r;
        std::cin >> l >> r;
        --l;
        qry[l].emplace_back(r, i);
    }

    std::vector<int> s(n);
    for (int i = n - 2; i >= 0; --i) {
        s[i] = s[i + 1] + b[i + 1];
    }

    std::vector<int> ans(q);
    for (int bit = 0; bit < 29; ++bit) {
        int fst = n;
        Node *root = nullptr;
        int m = 2 << bit;
        for (int l = n - 1; l >= 0; --l) {
            modify(root, 0, m, -s[l] & (m - 1), l);
            int x = (a[l] + s[l]) & (m - 1);
            fst = std::min({
                fst,
                query(root, 0, m, m / 2 - x, m - x),
                query(root, 0, m, m / 2 - x + m, m)
            });

            for (auto [r, id] : qry[l]) {
                if (fst < r) {
                    ans[id] += 1 << bit;
                }
            }
        }
    }

    constexpr int P = 998244353, B = 233;

    int res = 0, coef = 1;
    for (int i = 0; i < q; ++i) {
        coef = 1ll * coef * B % P;
        res = (res + 1ll * ans[i] * coef) % P;
    }
    std::cout << res << "\n";
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}