#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = int(a); i < int(b); i++)
#define trav(a, x) for (auto& a : x)
#define per(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define all(x) x.begin(), x.end()
template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }
template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;
using ll = int64_t;
using vi = vc<int>;
using pii = pair<int, int>;
using uint = uint32_t;
using ull = uint64_t;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
template <class F>
struct ycr {
F f;
template <class T> explicit ycr(T&& f_) : f(forward<T>(f_)) {}
template <class... Args> decltype(auto) operator()(Args&&... args) {
return f(ref(*this), forward<Args>(args)...);
}
};
template <class F> decltype(auto) yc(F&& f) {
return ycr<decay_t<F>>(forward<F>(f));
}
template <class T> T pow(T a, ll b) {
assert(b >= 0);
T r = 1;
while (b) {
if (b & 1) r *= a;
a *= a;
b >>= 1;
}
return r;
}
template <uint mod> struct mint {
static constexpr uint m = mod;
const static mint g;
uint v;
mint() : v(0) {}
mint(ll a) { s(uint(a % m + m)); }
mint& s(uint a) { v = a < m ? a : a-m; return *this; }
mint operator- () const {
mint res;
res.v = v ? m-v : 0;
return res;
}
friend mint inv(const mint& n) { return pow(n, m-2); }
mint& operator += (const mint& o) { return s(v + o.v); }
mint& operator -= (const mint& o) { return s(v + m - o.v); }
mint& operator *= (const mint& o) { v = uint(ull(v) * o.v % m); return *this; }
mint& operator /= (const mint& o) { return *this *= inv(o); }
friend mint operator + (const mint& a, const mint& b) { return mint(a) += b; }
friend mint operator - (const mint& a, const mint& b) { return mint(a) -= b; }
friend mint operator * (const mint& a, const mint& b) { return mint(a) *= b; }
friend mint operator / (const mint& a, const mint& b) { return mint(a) /= b; }
};
constexpr uint mod = 998244353;
using num = mint<mod>;
template<> const num num::g = num(3);
const num i6 = inv(num(6));
struct node_t {
array<num, 4> sums;
num lazy = 0;
node_t() : sums({}) {}
node_t(const array<num, 4>& a) : sums(a) {}
void add(num a) {
num a2 = a * a;
num a3 = a2 * a;
sums[3] += 3 * sums[2] * a + 3 * sums[1] * a2 + sums[0] * a3;
sums[2] += 2 * sums[1] * a + sums[0] * a2;
sums[1] += a * sums[0];
lazy += a;
}
static node_t merge(const node_t& l, const node_t& r) {
node_t res;
for (int z = 0; z < 4; z++) {
res[z] = l[z] + r[z];
}
return res;
}
void push(node_t& l, node_t& r) {
if (lazy.v != 0) {
l.add(lazy);
r.add(lazy);
lazy.v = 0;
}
}
num& operator [] (int i) {
return sums[i];
}
num operator [] (int i) const {
return sums[i];
}
};
#include <cassert>
#include <array>
#include <ostream>
// Copied from https://github.com/ecnerwala/cp-book/blob/master/src/seg_tree.hpp
namespace seg_tree {
// Floor of log_2(a); index of highest 1-bit
inline int log_2(int a) {
return a ? (8 * sizeof(a)) - 1 - __builtin_clz(a) : -1;
}
inline int next_pow_2(int a) {
assert(a > 0);
return 1 << log_2(2*a-1);
}
struct point {
int a;
point() : a(0) {}
explicit point(int a_) : a(a_) { assert(a >= -1); }
explicit operator bool () { return bool(a); }
// This is useful so you can directly do array indices
/* implicit */ operator int() const { return a; }
point c(bool z) const {
return point((a<<1)|z);
}
point operator [] (bool z) const {
return c(z);
}
point p() const {
return point(a>>1);
}
friend std::ostream& operator << (std::ostream& o, const point& p) { return o << int(p); }
template <typename F> void for_each(F f) const {
for (int v = a; v > 0; v >>= 1) {
f(point(v));
}
}
template <typename F> void for_parents_down(F f) const {
// strictly greater than 0
for (int L = log_2(a); L > 0; L--) {
f(point(a >> L));
}
}
template <typename F> void for_parents_up(F f) const {
for (int v = a >> 1; v > 0; v >>= 1) {
f(point(v));
}
}
point& operator ++ () { ++a; return *this; }
point operator ++ (int) { return point(a++); }
point& operator -- () { --a; return *this; }
point operator -- (int) { return point(a--); }
};
struct range {
int a, b;
range() : a(1), b(1) {}
range(int a_, int b_) : a(a_), b(b_) {
assert(1 <= a && a <= b && b <= 2 * a);
}
explicit range(std::array<int, 2> r) : range(r[0], r[1]) {}
explicit operator std::array<int, 2>() const {
return {a,b};
}
const int& operator[] (bool z) const {
return z ? b : a;
}
friend std::ostream& operator << (std::ostream& o, const range& r) { return o << "[" << r.a << ".." << r.b << ")"; }
// Iterate over the range from outside-in.
// Calls f(point a)
template <typename F> void for_each(F f) const {
for (int x = a, y = b; x < y; x >>= 1, y >>= 1) {
if (x & 1) f(point(x++));
if (y & 1) f(point(--y));
}
}
// Iterate over the range from outside-in.
// Calls f(point a, bool is_right)
template <typename F> void for_each_with_side(F f) const {
for (int x = a, y = b; x < y; x >>= 1, y >>= 1) {
if (x & 1) f(point(x++), false);
if (y & 1) f(point(--y), true);
}
}
// Iterate over the range from left to right.
// Calls f(point)
template <typename F> void for_each_l_to_r(F f) const {
int anc_depth = log_2((a-1) ^ b);
int anc_msk = (1 << anc_depth) - 1;
for (int v = (-a) & anc_msk; v; v &= v-1) {
int i = __builtin_ctz(v);
f(point(((a-1) >> i) + 1));
}
for (int v = b & anc_msk; v; ) {
int i = log_2(v);
f(point((b >> i) - 1));
v ^= (1 << i);
}
}
// Iterate over the range from right to left.
// Calls f(point)
template <typename F> void for_each_r_to_l(F f) const {
int anc_depth = log_2((a-1) ^ b);
int anc_msk = (1 << anc_depth) - 1;
for (int v = b & anc_msk; v; v &= v-1) {
int i = __builtin_ctz(v);
f(point((b >> i) - 1));
}
for (int v = (-a) & anc_msk; v; ) {
int i = log_2(v);
f(point(((a-1) >> i) + 1));
v ^= (1 << i);
}
}
template <typename F> void for_parents_down(F f) const {
int x = a, y = b;
if ((x ^ y) > x) { x <<= 1, std::swap(x, y); }
int dx = __builtin_ctz(x);
int dy = __builtin_ctz(y);
int anc_depth = log_2((x-1) ^ y);
for (int i = log_2(x); i > dx; i--) {
f(point(x >> i));
}
for (int i = anc_depth; i > dy; i--) {
f(point(y >> i));
}
}
template <typename F> void for_parents_up(F f) const {
int x = a, y = b;
if ((x ^ y) > x) { x <<= 1, std::swap(x, y); }
int dx = __builtin_ctz(x);
int dy = __builtin_ctz(y);
int anc_depth = log_2((x-1) ^ y);
for (int i = dx+1; i <= anc_depth; i++) {
f(point(x >> i));
}
for (int v = y >> (dy+1); v; v >>= 1) {
f(point(v));
}
}
};
struct in_order_layout {
// Alias them in for convenience
using point = seg_tree::point;
using range = seg_tree::range;
int N, S;
in_order_layout() : N(0), S(0) {}
in_order_layout(int N_) : N(N_), S(N ? next_pow_2(N) : 0) {}
point get_point(int a) const {
assert(0 <= a && a < N);
a += S;
return point(a >= 2 * N ? a - N : a);
}
range get_range(int a, int b) const {
assert(0 <= a && a <= b && b <= N);
if (N == 0) return range();
a += S, b += S;
return range((a >= 2 * N ? 2*(a-N) : a), (b >= 2 * N ? 2*(b-N) : b));
}
range get_range(std::array<int, 2> p) const {
return get_range(p[0], p[1]);
}
int get_leaf_index(point pt) const {
int a = int(pt);
assert(N <= a && a < 2 * N);
return (a < S ? a + N : a) - S;
}
std::array<int, 2> get_node_bounds(point pt) const {
int a = int(pt);
assert(1 <= a && a < 2 * N);
int l = __builtin_clz(a) - __builtin_clz(2*N-1);
int x = a << l, y = (a+1) << l;
assert(S <= x && x < y && y <= 2*S);
return {(x >= 2 * N ? (x>>1) + N : x) - S, (y >= 2 * N ? (y>>1) + N : y) - S};
}
int get_node_split(point pt) const {
int a = int(pt);
assert(1 <= a && a < N);
int l = __builtin_clz(2*a+1) - __builtin_clz(2*N-1);
int x = (2*a+1) << l;
assert(S <= x && x < 2*S);
return (x >= 2 * N ? (x>>1) + N : x) - S;
}
int get_node_size(point pt) const {
auto bounds = get_node_bounds(pt);
return bounds[1] - bounds[0];
}
};
struct circular_layout {
// Alias them in for convenience
using point = seg_tree::point;
using range = seg_tree::range;
int N;
circular_layout() : N(0) {}
circular_layout(int N_) : N(N_) {}
point get_point(int a) const {
assert(0 <= a && a < N);
return point(N + a);
}
range get_range(int a, int b) const {
assert(0 <= a && a <= b && b <= N);
if (N == 0) return range();
return range(N + a, N + b);
}
range get_range(std::array<int, 2> p) const {
return get_range(p[0], p[1]);
}
int get_leaf_index(point pt) const {
int a = int(pt);
assert(N <= a && a < 2 * N);
return a - N;
}
// Returns {x,y} so that 0 <= x < N and 1 <= y <= N
// If the point is non-wrapping, then 0 <= x < y <= N
std::array<int, 2> get_node_bounds(point pt) const {
int a = int(pt);
assert(1 <= a && a < 2 * N);
int l = __builtin_clz(a) - __builtin_clz(2*N-1);
int S = next_pow_2(N);
int x = a << l, y = (a+1) << l;
assert(S <= x && x < y && y <= 2*S);
return {(x >= 2 * N ? x >> 1 : x) - N, (y > 2 * N ? y >> 1 : y) - N};
}
// Returns the split point of the node, such that 1 <= s <= N.
int get_node_split(point pt) const {
int a = int(pt);
assert(1 <= a && a < N);
return get_node_bounds(pt.c(0))[1];
}
int get_node_size(point pt) const {
auto bounds = get_node_bounds(pt);
int r = bounds[1] - bounds[0];
return r > 0 ? r : r + N;
}
};
} // namespace seg_tree
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(20);
int N, Q;
cin >> N >> Q;
vc<num> A(N);
for (int i = 0; i < N; i++) {
cin >> A[i].v;
}
N++;
using i128 = __int128_t;
auto to_int = [&](string s) -> i128 {
i128 res = 0;
for (char c : s) {
res *= 2;
if (c == '1') res++;
}
return res;
};
vc<i128> L(Q), R(Q);
vc<int> X(Q);
vc<i128> vals;
for (int q = 0; q < Q; q++) {
int op;
cin >> op;
string sl, sr;
cin >> sl >> sr;
L[q] = to_int(sl);
R[q] = to_int(sr);
R[q]++;
vals.push_back(L[q]);
vals.push_back(R[q]);
if (op == 1) {
cin >> X[q];
} else if (op == 2) {
X[q] = -1;
} else assert(false);
}
sort(begin(vals), end(vals));
vals.erase(unique(begin(vals), end(vals)), end(vals));
auto lookup = [&](i128 v) -> int {
return int(lower_bound(begin(vals), end(vals), v) - begin(vals));
};
vvc<num> choose(4, vc<num>(4));
for (int i = 0; i <= 3; i++) {
choose[i][0] = 1;
for (int j = 1; j <= i; j++) {
choose[i][j] = choose[i-1][j-1] + choose[i-1][j];
}
}
assert(choose[3][2].v == 3);
assert(choose[3][1].v == 3);
assert(choose[2][1].v == 2);
int V = sz(vals);
vc<array<num, 4>> psums(V);
for (int i = 0; i < V; i++) {
auto v = vals[i];
vvc<num> dp(2, vc<num>(4));
dp[0][0] = 1;
for (int k = N-1; k >= 0; k--) {
int cur_bit = int((v >> k) & 1);
vvc<num> ndp(2, vc<num>(4));
for (int le = 0; le < 2; le++) {
for (int bit = 0; bit < 2; bit++) {
if (!le && bit > cur_bit) continue;
int new_le = (le || (bit < cur_bit));
for (int c = 0; c <= 3; c++) {
num d = dp[le][c];
if (bit == 0) {
ndp[new_le][c] += d;
} else {
num p = 1;
for (int nc = c; nc <= 3; nc++, p *= A[k]) {
ndp[new_le][nc] += d * p * choose[nc][c];
}
}
}
}
}
dp = std::move(ndp);
}
//cerr << "v = " << uint(v % mod) << endl;
for (int c = 0; c <= 3; c++) {
psums[i][c] = dp[1][c];
}
//cerr << "0 = " << psums[i][0].v << endl;
assert(psums[i][0].v == uint(v % mod));
}
vector<node_t> seg(2 * (V-1));
seg_tree::in_order_layout layout(V-1);
for (int i = 0; i+1 < V; i++) {
array<num, 4> diff;
for (int c = 0; c <= 3; c++) {
diff[c] = psums[i+1][c] - psums[i][c];
}
auto a = layout.get_point(i);
seg[a] = node_t(diff);
}
for (seg_tree::point a(layout.N - 1); a > 0; a--) {
seg[a] = node_t::merge(seg[a.c(0)], seg[a.c(1)]);
}
//auto sq = [&](num a) -> num { return a * a; };
auto cb = [&](num a) -> num { return a * a * a; };
for (int q = 0; q < Q; q++) {
int l = lookup(L[q]);
int r = lookup(R[q]);
int x = X[q];
int op;
if (x >= 0) {
op = 1;
} else {
op = 2;
}
auto rng = layout.get_range(l, r);
rng.for_parents_down([&](auto p) {
seg[p].push(seg[p.c(0)], seg[p.c(1)]);
});
if (op == 1) {
rng.for_each_l_to_r([&](auto a) {
seg[a].add(x);
});
rng.for_parents_up([&](auto p) {
seg[p] = node_t::merge(seg[p.c(0)], seg[p.c(1)]);
});
} else if (op == 2) {
array<num, 4> p = {};
rng.for_each_l_to_r([&](auto a) {
p[1] += seg[a][1];
p[2] += seg[a][2];
p[3] += seg[a][3];
});
num res = cb(p[1]) - 3 * p[1] * p[2] + 2 * p[3];
res *= i6;
cout << res.v << '\n';
} else assert(false);
}
return 0;
}