#include #include using namespace std; const int LOG = 30; const int ALL = (1 << LOG) - 1; const long long MOD = 998244353; struct S{ array A; S(){ A[0] = 0; A[1] = ALL; } S(int x, int y){ A[0] = x; A[1] = y; } }; S op(S L, S R){ S ans; ans.A[0] = (ALL ^ L.A[0]) & R.A[0] | L.A[0] & R.A[1]; ans.A[1] = (ALL ^ L.A[1]) & R.A[0] | L.A[1] & R.A[1]; return ans; } S e(){ return S(); } int main(){ int N, Q; cin >> N >> Q; vector M(N); for (int i = 0; i < N; i++){ cin >> M[i]; M[i]++; } vector C(Q); vector L(Q), R(Q), X(Q); for (int i = 0; i < Q; i++){ cin >> C[i] >> L[i] >> R[i] >> X[i]; L[i]--; } vector> add(N + 1), sub(N + 1); for (int i = 0; i < Q; i++){ add[L[i]].push_back(i); sub[R[i]].push_back(i); } atcoder::segtree ST(Q); vector res(N); for (int i = 0; i < N; i++){ for (int j : add[i]){ if (C[j] == 'o'){ ST.set(j, S(X[j], ALL)); } if (C[j] == 'x'){ ST.set(j, S(X[j], ALL ^ X[j])); } } for (int j : sub[i]){ ST.set(j, S()); } res[i] = ST.all_prod(); } vector> B(LOG + 1, vector(N, 0)); for (int i = 0; i < N; i++){ vector>> dp(LOG + 1, vector>(2, vector(LOG + 1, 0))); dp[LOG][0][0] = 1; for (int j = LOG - 1; j >= 0; j--){ for (int k = 0; k < 2; k++){ for (int l = 0; l <= LOG - 1 - j; l++){ for (int m = 0; m < 2; m++){ if (!((M[i] >> j & 1) == 0 && k == 0 && m == 1)){ int k2 = k; if ((M[i] >> j & 1) == 1 && m == 0){ k2 = 1; } int m2 = res[i].A[m] >> j & 1; dp[j][k2][l + m2] += dp[j + 1][k][l]; } } } } } for (int j = 0; j <= LOG; j++){ B[j][i] = dp[0][1][j] % MOD; } } for (int i = 0; i < N; i++){ for (int j = 0; j < LOG; j++){ B[j + 1][i] += B[j][i]; B[j + 1][i] %= MOD; } } long long t = 1; for (int i = 0; i < N; i++){ t *= M[i]; t %= MOD; } long long ans = 0; for (int i = 0; i <= LOG; i++){ long long prod = 1; for (int j = 0; j < N; j++){ prod *= B[i][j]; prod %= MOD; } ans += t - prod; } ans %= MOD; cout << ans << endl; }