#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <random>
#include <ext/pb_ds/assoc_container.hpp>

#define all(a) a.begin(), a.end()

using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

mt19937_64 rnd(42);

template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

constexpr int mod = 998244353;

struct mint {
    int val = 0;

    mint() = default;

    mint(int const &x) {
        if (x >= mod) val = x - mod;
        else if (x < 0) val = x + mod;
        else val = x;
    }

    mint(ll const &x) : val(x % mod) {}

    mint operator+(mint const &n) const {
        return val + n.val;
    }

    mint operator-(mint const &n) const {
        return val - n.val;
    }

    mint operator*(mint const &n) const {
        return (ll) val * n.val;
    }

    bool operator<(mint const &n) const {
        return val < n.val;
    }

    bool operator==(mint const &n) const {
        return val == n.val;
    }

    bool operator!=(mint const &n) const {
        return val != n.val;
    }
};

mint fpow(mint a, ll n) {
    mint res = 1;
    while (n) {
        if (n & 1) {
            res = res * a;
        }
        a = a * a;
        n >>= 1;
    }
    return res;
}

mint operator/(mint const &a, mint const &b) {
    return a * fpow(b, mod - 2);
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    map<mint, map<int, mint>> g;
    mint k = (int) 1e5 + 7;
    mint hsh = 0;
    mint sum = 0;

    vector<mint> p(n + 1);
    p[0] = 1;
    for (int i = 1; i <= n; ++i) {
        p[i] = p[i - 1] * k;
    }

    for (int i = 0; i < n; ++i) {
        hsh = hsh + p[i] * a[i];
        sum = sum + fpow(a[i], i + 1);
    }
    g[hsh][0] = hsh;
    map<mint, mint> anses;
    map<mint, vector<int>> as;
    as[hsh] = a;
    anses[hsh] = sum;

    mint cur = hsh;
    int t;

    for (int i = 0; i < q; ++i) {
        cin >> t;
        if (g[cur].find(t) == g[cur].end()) {
            a = as[cur];
            if (t == 1) {
                for (int i = 0; i < n - 1 - i; ++i) {
                    swap(a[i], a[n - i - 1]);
                }
            } else if (t == 2) {
                for (int i = 0; i < n; ++i) {
                    a[i] = n + 1 - a[i];
                }
            } else {
                vector<int> a_(n);
                for (int i = 0; i < n; ++i) {
                    a_[a[i] - 1] = i + 1;
                }
                a = a_;
            }

            hsh = 0;
            sum = 0;
            for (int i = 0; i < n; ++i) {
                hsh = hsh + p[i] * a[i];
                sum = sum + fpow(a[i], i + 1);
            }

            g[cur][t] = hsh;
            g[hsh][0] = hsh;
            anses[hsh] = sum;
        }
        cur = g[cur][t];
        cout << anses[cur].val << ' ';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
}