#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>

constexpr int mod = 998244353;
constexpr int M = 105;

using int128_t = __int128;
using uint128_t = unsigned __int128;

constexpr int64_t c3(int64_t n) {
    return static_cast<int64_t>((int128_t(n) * (n - 1) * (n - 2) / 6 % mod));
}

constexpr int64_t c2(int64_t n) {
    return static_cast<int64_t>(n * (n - 1) / 2 % mod);
}

struct data {
    int s0, s1, s2, s3;
    explicit data(int s0 = 0, int s1 = 0, int s2 = 0, int s3 = 0)
        : s0(s0), s1(s1), s2(s2), s3(s3) {}
    data add(int64_t x) const {
        auto x2 = x * x % mod;
        auto x3 = x2 * x % mod;
        return data(
            s0,
            static_cast<int>((s1 + s0 * x) % mod),
            static_cast<int>((s2 + x * (s0 - 1) % mod * s1 + x2 * c2(s0)) % mod),
            static_cast<int>(
                (s3 + x * (s0 - 2) * s2 % mod + x2 * c2(s0 - 1) % mod * s1 % mod + x3 * c3(s0) % mod
                )
                % mod
            )
        );
    }
};

data merge(const data &l, const data &r) {
    return data(
        (l.s0 + r.s0) % mod,
        (l.s1 + r.s1) % mod,
        static_cast<int>((l.s2 + r.s2 + (int64_t) l.s1 * r.s1) % mod),
        static_cast<int>((l.s3 + r.s3 + (int64_t) l.s1 * r.s2 + (int64_t) l.s2 * r.s1) % mod)
    );
}
data s[M];
int a[M];
int n;


struct tree {
    data v{};
    tree *ls, *rs;
    int lazy;
    void push_up() {
        v = merge(ls->v, rs->v);
    }
    tree(data v, tree *ls, tree *rs) : v(v), ls(ls), rs(rs), lazy(0) {}
    tree(int64_t prefix, int depth) : v(s[depth].add(prefix)), ls(nullptr), rs(nullptr), lazy(0){};
    void push_down(int64_t pl, int64_t pr, int depth) {
        if (!ls) {
            ls = new tree(pl, depth);
        }
        if (!rs) {
            rs = new tree(pr, depth);
        }
        if (lazy) {
            ls->v = ls->v.add(lazy);
            ls->lazy = (ls->lazy + lazy) % mod;
            rs->v = rs->v.add(lazy);
            rs->lazy = (rs->lazy + lazy) % mod;
            lazy = 0;
        }
    }
};

auto query(tree *&p, uint128_t l, uint128_t r, uint128_t _l, uint128_t _r, int prefix, int depth) {
    assert(p);
    if (l == _l && r == _r) {
        return p->v;
    }
    auto pl = prefix;
    auto pr = (prefix + a[depth]) % mod;
    auto mid = (l + r) >> 1;
    p->push_down(pl, pr, depth + 1);
    if (_r <= mid) {
        return query(p->ls, l, mid, _l, _r, pl, depth + 1);
    }
    if (_l > mid) {
        return query(p->rs, mid + 1, r, _l, _r, pr, depth + 1);
    }
    return merge(
        query(p->ls, l, mid, _l, mid, pl, depth + 1),
        query(p->rs, mid + 1, r, mid + 1, _r, pr, depth + 1)
    );
}

std::ostream &operator<<(std::ostream &os, uint128_t x) {
    if (x <= 9) {
        os << (int) x;
        return os;
    }
    os << (x / 10) << (int) (x % 10);
    return os;
}

void update(
    tree *&p, uint128_t l, uint128_t r, uint128_t _l, uint128_t _r, int prefix, int depth, int x
) {
    assert(p);
    if (l == _l && r == _r) {
        p->v = p->v.add(x);
        p->lazy = (p->lazy + x) % mod;
        return;
    }
    auto pl = prefix;
    auto pr = (prefix + a[depth]) % mod;
    auto mid = (l + r) >> 1;
    p->push_down(pl, pr, depth + 1);
    if (_r <= mid) {
        update(p->ls, l, mid, _l, _r, pl, depth + 1, x);
    } else if (mid < _l) {
        update(p->rs, mid + 1, r, _l, _r, pr, depth + 1, x);
    } else {
        update(p->ls, l, mid, _l, mid, pl, depth + 1, x);
        update(p->rs, mid + 1, r, mid + 1, _r, pr, depth + 1, x);
    }
    p->push_up();
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; ++i) {
        scanf("%d", a + i);
    }
    std::reverse(a, a + n);
    s[n] = data(1, 0);
    for (int i = n - 1; i >= 0; --i) {
        s[i] = merge(s[i + 1].add(a[i]), s[i + 1]);
    }
    auto root = new tree(0, 0);
    while (q--) {
        int op;
        char sl[200], sr[200];
        scanf("%d%s%s", &op, sl, sr);
        uint128_t l = 0, r = 0;
        for (int i = 0; i < n; ++i) {
            l = l << 1 | sl[i] - '0';
            r = r << 1 | sr[i] - '0';
        }
        if (op == 1) {
            int x;
            scanf("%d", &x);
            update(root, 0, ((uint128_t) 1 << n) - 1, l, r, 0, 0, x);
        } else {
            printf("%d\n", (query(root, 0, ((uint128_t) 1 << n) - 1, l, r, 0, 0).s3 + mod) % mod);
        }
    }
    return 0;
}