#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("O3,unroll_loops")
//#pragma GCC target("avx2")

#define int long long
using namespace  std;
using namespace __gnu_pbds;
int const INF = 1e18;

//tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//----------------------------------------------------------------------------------------

int const maxn = 1e6;
int const LG = 23;
int const mod = 998244353;

int binpow(int a, int b) {
    int res = 1;
    while (b != 0) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, qq;
    cin >> n >> qq;


    vector<int> p(n);
    for (auto  &i: p) cin >> i;
    vector<int> where(n + 1, -1);
    for (int i = 0; i < n; i++) {
        where[p[i]] = i;
    }
    vector<vector<int>> ans(2, vector<int> (2, 0));
    for (int i = 1; i <= n; i++) {
        ans[0][0] = (ans[0][0] + binpow(p[i - 1], i)) % mod;
        ans[1][0] = (ans[1][0] + binpow(p[i - 1], n - i + 1)) % mod;
    }
    for (int i = 0; i < n; i++) {
        int pobri = n - p[i] + 1;
        int obri = where[pobri];
        if (obri == i) {
            ans[0][1] = (ans[0][1] + binpow(p[i], i + 1)) % mod;
            ans[1][1] = (ans[1][1] + binpow(p[i], n - i)) % mod;
        }
        else if (obri > i) {
            ans[0][1] = (ans[0][1] + binpow(pobri, i + 1)) % mod;
            ans[0][1] = (ans[0][1] + binpow(p[i], obri + 1)) % mod;
            ans[1][1] = (ans[1][1] + binpow(pobri, n - i)) % mod;
            ans[1][1] = (ans[1][1] + binpow(p[i], n - obri)) % mod;
        }
    }

    int anss1 = ans[0][0];
    int anss2 = 0;
    vector<int> q(n);
    for (int i = 0; i < n; i++) {
        q[p[i] - 1] = i + 1;
    }
    for (int i = 0; i < n; i++) {
        anss2 = (anss2 + binpow(q[i], i + 1)) % mod;
    }
    int n1 = 0;
    int n2 = 0;
    int type = 0;
    int k = 0;
    while (qq--) {
        int t;
        cin >> t;
        if (t == 3) type = 1;
        if (type) {
            if (!k) cout << anss2 << " ";
            else cout << anss1 << " ";
            k = 1 - k;
            continue;
        }

        if (t == 1) {
            n1 = 1 - n1;
        }
        else if (t == 2) {
            n2 = 1 - n2;
        }
        cout << ans[n1][n2] << " ";
    }

    return 0;
}
