#include <cassert>
#include <iostream>

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

using int128_t = __int128;
using uint128_t = unsigned __int128;

template<typename T>
T power(T x, T k) {
    T res(1);
    for (; k; k >>= 1) {
        if (k & 1) {
            res = res * x % mod;
        }
        x = x * x % mod;
    }
    return res;
}

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 + x2 * c2(s0 - 1) % mod * s1 + x3 * c3(s0)) % mod
            )
        );
    }
    data mul(int64_t x) const {
        auto x2 = x * x % mod;
        auto x3 = x2 * x % mod;
        return data(
            s0,
            static_cast<int>((s1 * x) % mod),
            static_cast<int>((s2 * x2) % mod),
            static_cast<int>((s3 * x3) % 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];
int64_t 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) {
            return;
        }
        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, int64_t prefix, int depth
) {
    /* if (!p) { */
    /*     p = new tree(prefix, depth); */
    /* } */
    if (l == _l && r == _r) {
        return p->v;
    }
    auto pl = prefix;
    auto pr = (prefix + a[depth]) % mod;
    p->push_down(pl, pr, depth + 1);
    auto mid = (l + r) >> 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,
    int64_t prefix,
    int depth,
    int64_t x
) {
    /* if (!p) { */
    /*     p = new tree(prefix, depth); */
    /* } */
    /* assert(p); */
    /* std::cerr << l << " " << r << " " << _l << " " << _r << " " << prefix << " " << depth */
    /*           << std::endl; */
    if (l == _l && r == _r) {
        p->v = p->v.add(x);
        p->lazy = static_cast<int>((p->lazy + x) % mod);
        return;
    }
    auto pl = prefix;
    auto pr = (prefix + a[depth]) % mod;
    /* puts("wow"); */
    p->push_down(pl, pr, depth + 1);
    auto mid = (l + r) >> 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("%lld", 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 t = s[n].add(a[n - 1]); */
    /*     fprintf(stderr, "t = %d %d %d %d\n", t.s0, t.s1, t.s2, t.s3); */
    /* } */
    /* { */
    /*     auto f = [&](int x) { */
    /*         int64_t res = 1; */
    /*         for (int i = 0; i < n; ++i) { */
    /*             if (x >> i & 1) { */
    /*                 res = res * a[i] % mod; */
    /*             } */
    /*         } */
    /*         return res; */
    /*     }; */
    /*     int64_t sum = 0; */
    /*     for (int i = 0; i < 1 << n; ++i) { */
    /*         for (int j = i + 1; j < 1 << n; ++j) { */
    /*             for (int k = j + 1; k < 1 << n; ++k) { */
    /*                 sum = (sum + f(i) + f(j) + f(k)) % mod; */
    /*             } */
    /*         } */
    /*     } */
    /*     fprintf(stderr, "sum = %lld\n", sum); */
    /*     for (int i = 0; i <= n; ++i) { */
    /*         fprintf(stderr, "s[%d] = %d %d %d %d\n", i, s[i].s0, s[i].s1, s[i].s2, s[i].s3); */
    /*     } */
    /* } */
    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;
}

answer.code: In function ‘int main()’:
answer.code:173:19: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
  173 |         scanf("%lld", a + i);
      |                ~~~^   ~~~~~
      |                   |     |
      |                   |     int64_t* {aka long int*}
      |                   long long int*
      |                %ld
answer.code:175:10: error: ‘reverse’ is not a member of ‘std’
  175 |     std::reverse(a, a + n);
      |          ^~~~~~~
answer.code:171:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  171 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
answer.code:173:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  173 |         scanf("%lld", a + i);
      |         ~~~~~^~~~~~~~~~~~~~~
answer.code:211:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  211 |         scanf("%d%s%s", &op, sl, sr);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
answer.code:219:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  219 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~