#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz(x) (int)(x.size())

constexpr int N = 1e7;
constexpr int inf = 1e18;
constexpr int mod = 998244353;

int mul(int a, int b) {
    return a * b % mod;
}

int sum(int a, int b) {
    if (a + b >= mod) {
        return a + b - mod;
    }
    return a + b;
}

int binpow(int a, int b) {
    if (b == 0) {
        return 1;
    }
    if (b % 2 == 1) {
        return mul(binpow(a, b - 1), a);
    }
    int s = binpow(a, b / 2);
    return mul(s, s);
}

int solve(vector<int> &a) {
    int s = 0;
    for (int i = 0; i < sz(a); i++) {
        s = sum(s, binpow(a[i], i + 1));
    }
    return s;
}

signed main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    int s = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s = sum(s, binpow(a[i], i + 1));
    }
    vector<int> op1, op2, op3;
    vector<vector<int>> mp;
    vector<int> ans;
    mp.push_back(a);
    ans.push_back(s);
    op1.push_back(-1);
    op2.push_back(-1);
    op3.push_back(-1);
    map<vector<int>, int> idx;
    idx[a] = 0;
    int i = 0;
    vector<int> b;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            if (op1[i] == -1) {
                b.resize(n);
                for (int j = 0; j < n; j++) {
                    b[j] = mp[i][n - j - 1];
                }
                if (idx.find(b) != idx.end()) {
                    op1[i] = idx[b];
                } else {
                    idx[b] = sz(mp);
                    op1[i] = sz(mp);
                    op1.push_back(-1);
                    op2.push_back(-1);
                    op3.push_back(-1);
                    mp.push_back(b);
                    ans.push_back(solve(b));
                }
            }
            i = op1[i];
            cout << ans[i] << endl;
        } else if (op == 2) {
            if (op2[i] == -1) {
                b.resize(n);
                for (int j = 0; j < n; j++) {
                    b[j] = n - mp[i][j] + 1;
                }
                if (idx.find(b) != idx.end()) {
                    op2[i] = idx[b];
                } else {
                    op2[i] = sz(mp);
                    idx[b] = sz(mp);
                    op1.push_back(-1);
                    op2.push_back(-1);
                    op3.push_back(-1);
                    mp.push_back(b);
                    ans.push_back(solve(b));
                }
            }
            i = op2[i];
            cout << ans[i] << endl;
        } else {
            if (op3[i] == -1) {
                b.resize(n);
                for (int j = 0; j < n; j++) {
                    b[mp[i][j] - 1] = j + 1;
                }
                if (idx.find(b) != idx.end()) {
                    op3[i] = idx[b];
                } else {
                    idx[b] = sz(mp);
                    op3[i] = sz(mp);
                    op1.push_back(-1);
                    op2.push_back(-1);
                    op3.push_back(-1);
                    mp.push_back(b);
                    ans.push_back(solve(b));
                }
            }
            i = op3[i];
            cout << ans[i] << endl;
        }
    }
    return 0;
}
