#pragma GCC optimize("O3, unroll-loops")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

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

const int inf = 1e9L;
const int mod = 998244353;
const int maxn = 1e5;

ll mod_bin_pow(ll x, ll pow) {
    if (!pow) return 1;
    ll ans = mod_bin_pow(x, pow / 2);
    ans = (ans * ans) % mod;
    if (pow & 1) ans = (ans * x) % mod;
    return ans;
}

void relox(vector<int>& p, vector<int> v1) {
    if (p.size() < v1.size()) return;
    bool f = true;
    for (int j = 0; j < v1.size(); j++) {
        f = f && (p[j + ll(p.size()) - ll(v1.size())] == v1[j]);
    }
    if (f) {
        for (int j = 0; j < v1.size(); ++j) p.pop_back();
    }
}
void relox1(vector<int>& p, int cnt) {
    int n = p.size();
    if (p.size() < 2 * cnt) return;
    bool f = true;
    for (int i = n - 2 * cnt; i < n - cnt; ++i) {
        f = f && (p[i] == p[i + cnt]);
    }
    if (f) {
        for (int i = 0; i < 2 * cnt; ++i) p.pop_back();
    }
}
void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) cin >> p[i];
    ll ans1 = 0, ans2 = 0;
    for (int i = 0; i < n; ++i) {
        ans1 += mod_bin_pow(p[i], i + 1);
        ans1 %= mod;
    }
    map<vector<int>, int> mp;
    set<vector<int>> was;
    vector<int> ans(q + 1);
    vector<int> par(q + 1, -1);
    vector<int> types(q + 1, 0);
    vector<int> stack;
    ans[0] = ans1;
    mp[{}] = ans1;
    was.insert({});
    auto start = p;
    for (int _ = 1; _ <= q; ++_) {
        cin >> types[_];
        int type = types[_];
        if (!stack.empty() && stack.back() == type) stack.pop_back();
        else stack.emplace_back(type);
        for (int i = 1; i < 6; i++) {
            relox1(p, i);
        }
        if (stack.size() >= 4 && false) {
            vector<int> v1 = {1, 2, 1, 2}, v2 = {2, 1, 2, 1};
            relox(stack, v1); relox(stack, v2);
            v1 = {1, 3, 1, 3};
            v2 = {3, 1, 3, 1};
            relox(stack, v1); relox(stack, v2);
            v1 = {2, 3, 2, 3};
            v2 = {3, 2, 3, 2};
            relox(stack, v1); relox(stack, v2);
            if (stack.size() >= 6) {
                v1 = {1, 2, 3, 1, 2, 3};
                v2 = {3, 2, 1, 3, 2, 1};
                relox(stack, v1); relox(stack, v2);
                v1 = {1, 3, 2, 1, 3, 2};
                v2 = {2, 3, 1, 2, 3, 1};
                relox(stack, v1); relox(stack, v2);
                v1 = {2, 1, 3, 2, 1, 3};
                v2 = {3, 1, 2, 3, 1, 2};
                relox(stack, v1); relox(stack, v2);
            }
        }
        if (_ == 1) {
            if (type == 1) {
                reverse(all(p));
            }else if (type == 2) {
                vector<int> newp(n);
                for (int i = 0; i < n; ++i) {
                    newp[i] = n - p[i] + 1;
                }
                p = newp;
            }else {
                vector<int> newp(n);
                for (int i = 0; i < n; i++) {
                    newp[p[i] - 1] = i + 1;
                }
                p = newp;
            }
            ans2 = 0;
            for (int i = 0; i < n; ++i) {
                ans2 += mod_bin_pow(p[i], i + 1);
                ans2 %= mod;
            }
            ans[_] = ans2;
        }else {
            if (!was.count(stack)) {
                auto pp = start;
                for (auto typex: stack) {
                    if (typex == 1) {
                        reverse(all(pp));
                    }else if (typex == 2) {
                        vector<int> newp(n);
                        for (int i = 0; i < n; ++i) {
                            newp[i] = n - pp[i] + 1;
                        }
                        pp = newp;
                    }else {
                        vector<int> newp(n);
                        for (int i = 0; i < n; i++) {
                            newp[pp[i] - 1] = i + 1;
                        }
                        pp = newp;
                    }
                }
                ll ansx = 0;
                for (int i = 0; i < n; ++i) {
                    ansx += mod_bin_pow(pp[i], i + 1);
                    ansx %= mod;
                }
                was.insert(stack);
                mp[stack] = ansx;
                ans[_] = ansx;
            }else {
                ans[_] = mp[stack];
            }
        }
    }
    for (int _ = 1; _ <= q; ++_) {
        cout << ans[_] << " ";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
}