#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,popcnt")
#pragma GCC target("tune=native")

using namespace std;

#define int long long
#define sz(x) (int)x.size()
#define eb emplace_back
#define vi vector<int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define vvi vector<vi>
#define vpi vector<pair<int, int> >
#define pi pair<int, int>
#define vvvi vector<vvi>

void solve() {
    int n, q; cin >> n >> q;
    vi a(n);
    set<int> st;
    for (int &x : a) {
        cin >> x;
        st.insert(x);
    }
    vi b(all(st));
    for (int &x : a) x = lower_bound(all(b), x) - b.begin();
    vi cnt(sz(b), 0), c(n, 0);
    for (int i = 0; i < n; ++i) {
        cnt[a[i]]++;
        c[i] = cnt[a[i]];
    }
    map<int, int> mp;
    mp[a[0] * (int)1e7 + c[0]] = 1;
    if (sz(b) == 1) {
        for (int i = 1; i < n; ++i) mp[a[i] * (int)1e7 + c[i]] = i + 1;
    } else {
        vi v1(sz(b), -1);
        int l = 0, r = 1;
        cnt[a[0]]--;
        vi cnt1(sz(b), 1);
        cnt1[a[0]]++;
        vi v;
        v.reserve(n);
        v.eb(a[0]);
        for (int i = 1; i < n; ++i) {
            if (!cnt[r]) {
                if (r == sz(b) - 1) r = l;
                else r++;
            }
            if (!cnt[l]) {
                l = r;
                if (r == sz(b) - 1) r = l;
                else r++;
            }
            if (v[sz(v) - 1] == l) {
                if (v1[r] == -1) v1[r] = i + 1;
                v.eb(r);
                mp[r * (int)1e7 + cnt1[r]] = i + 1;
                cnt1[r]++;
                cnt[r]--;
            } else {
                if (v1[l] == -1) v1[l] = i + 1;
                v.eb(l);
                mp[l * (int)1e7 + cnt1[l]] = i + 1;
                cnt1[l]++;
                cnt[l]--;
            }
        }
    }
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x; cin >> x;
            swap(a[x], a[x - 1]);
            mp[a[0] * (int)1e7 + c[0]] = 1;
            if (sz(b) == 1) {
                for (int i = 1; i < n; ++i) mp[a[i] * (int)1e7 + c[i]] = i + 1;
            } else {
                vi v1(sz(b), -1);
                int l = 0, r = 1;
                cnt[a[0]]--;
                vi cnt1(sz(b), 1);
                cnt1[a[0]]++;
                vi v;
                v.reserve(n);
                v.eb(a[0]);
                for (int i = 1; i < n; ++i) {
                    if (!cnt[r]) {
                        if (r == sz(b) - 1) r = l;
                        else r++;
                    }
                    if (!cnt[l]) {
                        l = r;
                        if (r == sz(b) - 1) r = l;
                        else r++;
                    }
                    if (v[sz(v) - 1] == l) {
                        if (v1[r] == -1) v1[r] = i + 1;
                        v.eb(r);
                        mp[r * (int)1e7 + cnt1[r]] = i + 1;
                        cnt1[r]++;
                        cnt[r]--;
                    } else {
                        if (v1[l] == -1) v1[l] = i + 1;
                        v.eb(l);
                        mp[l * (int)1e7 + cnt1[l]] = i + 1;
                        cnt1[l]++;
                        cnt[l]--;
                    }
                }
            }
        } else {
            int x; cin >> x;
            --x;
            //cout << a[x] << ' ' << c[x] << endl;
            cout << mp[a[x] * (int)1e7 + c[x]] << endl;
        }
    }
}

int mod = 998244353;

int binpow(int b, int p) {
    if (!p) return 1;
    if (p == 1) return b;
    if (p & 1) return b * binpow(b, p - 1) % mod;
    int t = binpow(b, p / 2);
    return t * t % mod;
}

int calc(const vi &v) {
    int ans = 0;
    for (int i = 0; i < sz(v); ++i) ans = (ans + binpow(v[i], i + 1)) % mod;
    return ans;
}

void solve_c() {
    int n, q; cin >> n >> q;
    if (n * q <= (int)1e7) {
        vi a(n);
        for (int &x : a) cin >> x;
        while (q--) {
            int x; cin >> x;
            if (x == 1) reverse(all(a));
            if (x == 2) {
                for (int &y : a) y = n - y + 1;
            }
            if (x == 3) {
                vi b(n);
                for (int w = 0; w < n; ++w) {
                    b[a[w] - 1] = w + 1;
                }
                swap(a, b);
            }
            cout << calc(a) << ' ';
        }
        cout << endl;
        return;
    }
    vi a(n);
    for (int &x : a) cin >> x;
    vi v(8);
    int x = 0;
    for (int i = 0; i < n; ++i) {
        x = (x + binpow(a[i], i + 1)) % mod;
    }
    v[0] = x;
    x = 0;
    for (int i = 0; i < n; ++i) {
        x = (x + binpow(a[i], n - i)) % mod;
    }
    v[1] = x;
    x = 0;
    for (int i = 0; i < n; ++i) {
        x = (x + binpow(n - a[i] + 1, i + 1)) % mod;
    }
    v[2] = x;
    x = 0;
    for (int i = 0; i < n; ++i) {
        x = (x + binpow(n - a[i] + 1, n - i)) % mod;
    }
    v[3] = x;
    x = 0;
    for (int i = 0; i < n; ++i) {
        x = (x + binpow(i + 1, a[i])) % mod;
    }
    v[4] = x;
    x = 0;
    for (int i = 0; i < n; ++i) {
        x = (x + binpow(i + 1, n - a[i] + 1)) % mod;
    }
    v[5] = x;
    x = 0;
    for (int i = 0; i < n; ++i) {
        x = (x + binpow(n - i, a[i])) % mod;
    }
    v[6] = x;
    x = 0;
    for (int i = 0; i < n; ++i) {
        x = (x + binpow(n - i, n - a[i] + 1)) % mod;
    }
    v[7] = x;
    int c1 = 0, c2 = 0, c3 = 0;
    while (q--) {
        int y; cin >> y;
        if (y == 3) {
            c3 ^= 1;
            swap(c1, c2);
        }
        if (y == 1) c1 ^= 1;
        if (y == 2) c2 ^= 1;
        cout << v[c3 * 4 + c2 * 2 + c1] << ' ';
    }
    cout << endl;
}

signed main() {
    freopen("C:/work/untitled1/input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--) solve_c();
}