#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = __uint128_t;
using uc = __uint128_t;
using ull =__uint128_t;
using ul = __uint128_t;
using i128 = __int128_t;
using u128 = __uint128_t;

ll MOD = 998244353LL;
ull P1 = 7692758373ULL;
ull P2 = 8694758251ULL;
ull MD1 = 8769375815ULL;
ull MD2 = 976947525ULL;

inline ll binpow(ll a, ll e) {
    ll res = 1;

    while (e) {
        if (e & 1) res = res * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }

    return res;
}

struct hasher {
    size_t operator()(const pair<pair<ull, ull>, int>& p) const {
        return hs(p.second) ^ hs((ull)p.first.first << 1) ^ hs((ull)p.first.second << 2);
    }

    hash<int> hs;
};

struct pair_hasher {
    size_t operator()(const pair<ull, ull>& p) const {
        return hs(p.first) ^ (hs(p.second) << 1);
    }

    hash<ull> hs;
};


inline void solve(ostringstream& os) {
    int n, q;
    cin >> n >> q;

    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    auto print = [&os](vector<ll>& a) -> void {
        for (ll an : a) os << an << ' ';
        os << '\n';
    };

    auto count = [&]() -> ll {
        ll res = 0;
        for (ll i = 0; i < n; ++i) {
            res = (res + binpow(a[i], i + 1)) % MOD;
        }
        return res;
    };

    auto get_hash = [&](vector<ll>& ref) -> pair<ull, ull> {
        ull res1 = 0;
        ull res2 = 0;
        hash<ull> hs;
        for (ull el : ref) {
            res1 = (res1 * P1 + hs(el)) % MD1;
            res2 = (res2 * P2 + hs(el)) % MD2;

        }
        return {res1, res2};
    };


    vector<int> queues(q);
    vector<int> cnt(4);
    for (int i = 0; i < q; ++i) {
        int type;
        cin >> type;
        cnt[type]++;

        queues[i] = type;
    }


    unordered_map<pair<pair<ull, ull>, int>, pair<pair<ull, ull>, ll>, hasher> mp;
    unordered_map<pair<ull, ull>, vector<ll>, pair_hasher> store;
    auto cur_hash = get_hash(a);
    store.insert({cur_hash, a});
    auto restore = [&]() -> void {
        a = store[cur_hash];
    };

    for (int type : queues) {
        auto iter = mp.find({cur_hash, type});
        if (iter != mp.end()) {
            cur_hash = iter->second.first;
            os << iter->second.second << ' ';
            continue;
        }

        restore();

        if (type == 1) {
            reverse(a.begin(), a.end());
            auto hs = get_hash(a);
            ll res = count();

            mp.insert({{cur_hash, type}, {hs, res}});
            store.insert({hs, a});

            cur_hash = hs;
            os << res << ' ';
        }

        else if (type == 2) {
            for (int j = 0; j < n; ++j) {
                a[j] = n - a[j] + 1;
            }

            auto hs = get_hash(a);
            ll res = count();

            mp.insert({{cur_hash, type}, {hs, res}});
            store.insert({hs, a});


            cur_hash = hs;
            os << res << ' ';
        }

        else {
            vector<ll> new_a(n);
            for (int j = 0; j < n; ++j) {
                new_a[a[j] - 1] = j + 1;
            }
            a = new_a;

            auto hs = get_hash(a);
            ll res = count();

            mp.insert({{cur_hash, type}, {hs, res}});
            store.insert({hs, a});


            cur_hash = hs;
            os << res << ' ';
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ostringstream os;

    solve(os);

    cout << os.str();
    // exit(0);
}