#include<bits/stdc++.h>

using namespace std;

#define int long long

const int eps = 998244353;

struct deep{
    vector<int> wert;
    int summa;
    int a1 = -1;
    int a2 = -1;
    int a3 = -1;
};

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<vector<int>> pref(n + 1, vector<int> (30));
    for (int i = 1; i <= n; i++) {
        pref[i][0] = i;
        for (int j = 1; j < 30; j++) {
            pref[i][j] = pref[i][j - 1] * pref[i][j - 1];
            pref[i][j] %= eps;
        }
    }
    string now = "000000000000000000000000000000";
    vector<string> d(n + 1, now);
    for (int i = 1; i <= n; i++) {
        int h = i;
        int u = 0;
        int g = 1;
        while(h > 0) {
            if (h % (2 * g) == g) {
                d[i][u] = '1';
                h -= g;
            }
            g *= 2;
            u += 1;
        }
    }
    int summ = 0;
    for (int i = 0; i < n; i++) {
        int now1 = 1;
        for (int j = 0; j < 30; j++) {
            if (d[i + 1][j] == '1') {
                now1 *= pref[a[i]][j];
                now1 %= eps;
            }
        }
        summ += now1;
        summ %= eps;
    }
    vector<deep> e(4);
    e[0].wert = a;
    e[0].summa = summ;
    int v = 0;
    int ee = 1;
    for (int s = 0; s < q; s++) {
        int b;
        cin >> b;
        //cout << b << "----------" << endl;
        if (b == 1) {
            if (e[v].a1 != -1) {
                v = e[v].a1;
                cout << e[v].summa << " ";
                a = e[v].wert;
            }
            else {
                vector<int> c = a;
                reverse(c.begin(), c.end());
                a = c;
                int fl = -1;
                for (int j = 0; j < e.size(); j++) {
                    if (fl == -1 && e[j].wert == c) {
                        e[v].a1 = j;
                        fl = 1;
                        cout << e[j].summa << " ";
                        v = j;
                    }
                }
                if (fl == -1) {
                    summ = 0;
                    for (int i = 0; i < n; i++) {
                        int now1 = 1;
                        for (int j = 0; j < 30; j++) {
                            if (d[i + 1][j] == '1') {
                                now1 *= pref[c[i]][j];
                                now1 %= eps;
                            }
                        }
                        summ += now1;
                        summ %= eps;
                    }
                    cout << summ << " ";
                    e[v].a1 = ee;
                    e[ee].wert = c;
                    e[ee].summa = summ;
                    e[ee].a1 = v;
                    v = ee;
                    ee += 1;
                }
            }
        }
        if (b == 2) {
            if (e[v].a2 != -1) {
                v = e[v].a2;
                cout << e[v].summa << " ";
                 a = e[v].wert;
            }
            else {
                vector<int> c = a;
                for (int j = 0; j < n; j++) {
                    c[j] = n + 1 - c[j];
                    // cout << c[j] << " ";
                }
                a = c;
                int fl = -1;
                for (int j = 0; j < e.size(); j++) {
                    if (fl == -1 && e[j].wert == c) {
                        e[v].a2 = j;
                        fl = 1;
                        cout << e[j].summa << " ";
                        v = j;
                    }
                }
                if (fl == -1) {
                    summ = 0;
                    for (int i = 0; i < n; i++) {
                        int now1 = 1;
                        for (int j = 0; j < 30; j++) {
                            if (d[i + 1][j] == '1') {
                                now1 *= pref[c[i]][j];
                                now1 %= eps;
                            }
                        }
                        summ += now1;
                        summ %= eps;
                    }
                    cout << summ << " ";
                    e[v].a2 = ee;
                    e[ee].wert = c;
                    e[ee].summa = summ;
                    e[ee].a2 = v;
                    v = ee;
                    ee += 1;
                }
            }
        }
        if (b == 3) {
            if (e[v].a3 != -1) {
                v = e[v].a3;
                cout << e[v].summa << " ";
                 a = e[v].wert;
            }
            else {
                vector<int> c = a;
                for (int j = 0; j < n; j++) {
                    c[a[j] - 1] = j + 1;
                    // cout << c[j] << " ";
                }
                a = c;
                int fl = -1;
                for (int j = 0; j < e.size(); j++) {
                    if (fl == -1 && e[j].wert == c) {
                        e[v].a3 = j;
                        fl = 1;
                        cout << e[j].summa << " ";
                        v = j;
                    }
                }
                if (fl == -1) {
                    summ = 0;
                    for (int i = 0; i < n; i++) {
                        int now1 = 1;
                        for (int j = 0; j < 30; j++) {
                            if (d[i + 1][j] == '1') {
                                now1 *= pref[c[i]][j];
                                now1 %= eps;
                            }
                        }
                        summ += now1;
                        summ %= eps;
                    }
                    cout << summ << " ";
                    e[v].a3 = ee;
                    e[ee].wert = c;
                    e[ee].summa = summ;
                    e[ee].a3 = v;
                    v = ee;
                    ee += 1;
                }
            }
        }
    }
    /*cout << endl;
    for (int i = 0; i < e.size(); i++) {
        for (int j = 0; j < (e[i].wert).size(); j++) {
            cout << e[i].wert[j] << " ";
        }
        cout << endl;
        cout << e[i].summa << " " << e[i].a1 << " " << e[i].a2 << endl << "---------------" << endl;
    }
    */
}

signed main() {
    int t = 1;
    while(t--) {
        solve();
    }
}
