#include<algorithm>
#include <iostream>
#include<set>
#include<map>
#include<unordered_map>
#include<math.h>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<iomanip>
#include<random>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

using ll = long long;
using ld = long double;
#define all(x) x.begin(), x.end()

ll inf = 1e18, mod = 998244353, n;
vector<ll> v, ans, x;

ll binpow(ll a, ll k) {
    ll res = 1;
    while (k) {
        if (k & 1) res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}

ll get_ans(ll pos, ll r) {
    if (ans[r * n + pos] != -1) return ans[r * n + pos];
    ll res = 0, k = pos + 1;
    if (r == 0) {
        for (int i = x[1]; i < n; ++i) {
            res = (res + binpow(v[i], k)) % mod;
            ++k;
            if (k > n) k = 1;
        }
        for (int i = 0; i < x[1]; ++i) {
            res = (res + binpow(v[i], k)) % mod;
            ++k;
            if (k > n) k = 1;
        }
    }
    else {
        for (int i = x[1]; i < n; ++i) {
            res = (res + binpow(v[i], k)) % mod;
            --k;
            if (k < 1) k = n;
        }
        for (int i = 0; i < x[1]; ++i) {
            res = (res + binpow(v[i], k)) % mod;
            --k;
            if (k < 1) k = n;
        }
    }
    ans[r * n + pos] = res;
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll q, pos, r = 0, psn, k, m, c, c1, ps, ps2, c3, c2;
    cin >> n >> q;
    v.resize(n);
    x.resize(n+1);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
        x[v[i]] = i;
        if (v[i] == n) psn = i;
        if (v[i] == n - 1) ps = i;
        if (v[i] == 2) ps2 = i;
        if (v[i] == 1) pos = i;
    }
    ans.resize(2 * n, -1);
    while (q--) {
        cin >> k;
        if (k == 1) {
            pos = n - pos - 1;
            psn = n - psn - 1;
            ps2 = n - ps2 - 1;
            ps = n - ps - 1;
        }
        else if (k == 2) {
            swap(pos, psn);
            swap(ps, ps2);
        }
        else {
            if (r == 0) {
                c = (n - pos + x[1]) % n;
                c1 = (2 * n - 1 - psn + x[n]) % n;
                c2 = (n + 1 - ps2 + x[2]) % n;
                c3 = (2 * n - 2 - ps + x[n - 1]) % n;
            }
            else {
                c = (pos + x[1]) % n;
                c1 = (psn + x[n]+1) % n;
                c2 = (ps2 + x[2] - 1 + n) % n;
                c3 = (ps + x[n - 1] + 2) % n;
            }
            m = v[c];
            pos = m - 1;
            psn = v[c1] - 1;
            ps2 = v[c2] - 1;
            ps = v[c3] - 1;
            //cout << ps2 << ' ' << ps << '\n';
        }
        if ((pos - psn + n) % n == (x[1] - x[n] + n) % n && (pos - ps + n) % n == (x[1] - x[n - 1] + n) % n) r = 0;
        else r = 1;
        cout << get_ans(pos, r) << ' ';
    }
}

