#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
using namespace std;

typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;

template <typename _T>
inline void read(_T &f) {
    f = 0; _T fu = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); }
    while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
    f *= fu;
}

template <typename T>
void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x < 10) putchar(x + 48);
    else print(x / 10), putchar(x % 10 + 48);
}

template <typename T>
void print(T x, char t) {
    print(x); putchar(t);
}

typedef __int128 i128;

const int md = 998244353;

inline int add(int x, int y) {
    if (x + y >= md) return x + y - md;
    return x + y;
}

inline void addx(int &x, int y) {
    x += y;
    if (x >= md) x -= md;
}

inline int sub(int x, int y) {
    if (x < y) return x - y + md;
    return x - y;
}

inline void subx(int &x, int y) {
    x -= y;
    if (x < 0) x += md;
}

inline int mul(int x, int y) { return 1ull * x * y % md; }

inline int fpow(int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = mul(ans, x);
        y >>= 1; x = mul(x, x);
    }
    return ans;
}

const int N = 2e7 + 5;

struct atom {
    int val[4], len;
};

atom w[N], base[100];
int lc[N], rc[N], tag[N];
int sum[5][1 << 20], pre[1 << 20], a[100]; char c[200];
int n, q, root, tot;

inline int lowbit(int x) { return x & -x; }

inline int getsum(i128 x) {
    int ans = 0;
    for (int i = 0; i < 5; i++) {
        ans = add(ans, sum[i][x & 1048575]);
        x >>= 20;
    }
    return ans;
}

int ifac[4];
int C(i128 n, int m) {
    if (n < m) return 0;
    int ans = ifac[m];
    for (int i = 1; i <= m; i++) ans = mul(ans, (n - i + 1) % md);
    return ans;
}

atom addatom(atom a, int b) {
    if (!b) return a;
    atom ans;
    memset(ans.val, 0, sizeof(ans.val)); ans.len = a.len;
    for (int i = 0; i <= 3; i++) {
        for (int j = 0; j <= 3; j++) {
            addx(ans.val[i + j], mul(a.val[i], mul(fpow(b, j), C(a.len - i, j))));
        }
    }
    return ans;
}

atom getatom(int bit, i128 state) {
    int tmp = getsum(state & (((i128)1 << 100) - ((i128)1 << bit)));
    if (bit == 0) {
        atom ans;
        ans.val[0] = 1;
        ans.val[1] = tmp;
        ans.val[2] = ans.val[3] = 0;
        return ans;
    }
    atom ans = base[bit - 1];
    return addatom(ans, tmp);
}

atom merge(atom a, atom b) {
    atom ans;
    memset(ans.val, 0, sizeof(ans.val)); ans.len = add(a.len, b.len);
    for (int i = 0; i <= 3; i++) {
        for (int j = 0; j <= 3 - i; j++) {
            addx(ans.val[i + j], mul(a.val[i], b.val[j]));
        }
    }
    return ans;
}

void newNode(int &u, i128 l, i128 r, int bit) {
    u = ++tot;
    w[u] = getatom(bit, l);
}

void add(int u, i128 L, i128 R, i128 l, i128 r, int x, int bit) {
    if (l <= L && R <= r) {
        w[u] = addatom(w[u], x);
        tag[u] = add(tag[u], x);
        return;
    }
    i128 mid = (L + R) >> 1;
    if (!lc[u]) newNode(lc[u], L, mid, bit - 1);
    if (!rc[u]) newNode(rc[u], mid + 1, R, bit - 1);
    if (mid >= l) add(lc[u], L, mid, l, r, x, bit - 1);
    if (mid + 1 <= r) add(rc[u], mid + 1, R, l, r, x, bit - 1);
    w[u] = addatom(merge(w[lc[u]], w[rc[u]]), tag[u]);
}

atom query(int u, i128 L, i128 R, i128 l, i128 r, int bit) {
    if (l <= L && R <= r) return w[u];
    i128 mid = (L + R) >> 1;
    if (!lc[u]) newNode(lc[u], L, mid, bit - 1);
    if (!rc[u]) newNode(rc[u], mid + 1, R, bit - 1);
    atom ans; memset(ans.val, 0, sizeof(ans.val)); ans.val[0] = 1; ans.len = 0;
    if (mid >= l) ans = query(lc[u], L, mid, l, r, bit - 1);
    if (mid + 1 <= r) ans = merge(ans, query(rc[u], mid + 1, R, l, r, bit - 1));
    return addatom(ans, tag[u]);
}

int main() {
    ifac[0] = 1; ifac[1] = 1; ifac[2] = fpow(2, md - 2); ifac[3] = fpow(6, md - 2);
    read(n); read(q);
    for (int i = 0; i < n; i++) read(a[i]), a[i] %= md;
    n = 100;
    for (int i = 0; i < 20; i++) pre[1 << i] = i;
    for (int i = 0; i < 5; i++) {
        for (int j = 1; j < (1 << 20); j++) {
            sum[i][j] = sum[i][j ^ lowbit(j)] + a[i * 20 + pre[lowbit(j)]];
        }
    }
    base[0].val[0] = 1;
    base[0].val[1] = a[0];
    base[0].len = 2;
    for (int i = 1; i < 100; i++) {
        for (int l = 0; l <= 3; l++) {
            for (int r = 0; r <= 3 - l; r++) {
                for (int x = 0; x <= 3 - l - r; x++) {
                    addx(base[i].val[l + r + x], mul(base[i - 1].val[l], mul(base[i - 1].val[r], mul(fpow(a[i], x), C(((i128)1 << i) - r, x)))));
                }
            }
        }
        base[i].len = mul(base[i - 1].len, 2);
    }
    newNode(root, 0, 0, 100);
    while (q--) {
        int opt; read(opt);
        i128 l = 0, r = 0;
        scanf("%s", c); int len = strlen(c);
        for (int i = 0; i < len; i++) {
            l = l * 2 + (c[i] - '0');
        }
        scanf("%s", c);
        for (int i = 0; i < len; i++) {
            r = r * 2 + (c[i] - '0');
        }
        if (opt == 1) {
            int x; read(x);
            add(root, 0, ((i128)1 << 100) - 1, l, r, x, 100);
        } else {
            atom ans = query(root, 0, ((i128)1 << 100) - 1, l, r, 100);
            print(ans.val[3], '\n');
        }
    }
    return 0;
}