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

using namespace std;

#define int long long
using ld = long double;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

int mod = 998244353;

int binpow(int x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 0) {
        return binpow(x*x%mod, n/2);
    }
    return binpow(x*x%mod, n/2) * x % mod;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector <int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    vector <int> b(q);
    for (int i = 0; i < q; i++) {
        cin >> b[i];
    }
    if (n <= 1000 && q <= 1000) {
        vector <vector <int>> pows(n+1, vector <int> (n+1, 1));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                pows[i][j] = pows[i][j-1] * i % mod;
            }
        }
        for (int i = 0; i < q; i++) {
            int a = b[i];
            int ans = 0;
            if (a == 1) {
                reverse(v.begin(), v.end());
            }
            if (a == 2) {
                for (int j = 0; j < n; j++) {
                    v[j] = n - v[j] + 1;
                }
            }
            if (a == 3) {
                vector <int> v1(n);
                for (int j = 0; j < n; j++) {
                    v1[v[j]-1] = j+1;
                }
                v = v1;
            }
            for (int j = 0; j < n; j++) {
                ans += pows[v[j]][j+1];
                ans %= mod;
            }
            cout << ans << '\n';
        }
        return 0;
    }
    bool b1 = 1;
    for (int i = 1; i < q; i++) {
        if (b[i] != b[i-1]) {
            b1 = 0;
        }
    }
    if (b1) {
        while (1);
        int ans1 = 0;
        int ans2 = 0;
        for (int i = 0; i < n; i++) {
            ans1 += binpow(v[i], i+1);
        }
        int a = b[0];
        if (a == 1) {
            reverse(v.begin(), v.end());
        }
        if (a == 2) {
            for (int j = 0; j < n; j++) {
                v[j] = n - v[j] + 1;
            }
        }
        if (a == 3) {
            vector <int> v1(n);
            for (int j = 0; j < n; j++) {
                v1[v[j]-1] = j+1;
            }
            v = v1;
        }
        for (int i = 0; i < n; i++) {
            ans2 += binpow(v[i], i+1);
        }
        for (int i = 0; i < q; i++) {
            if (i % 2 == 0) {
                cout << ans2;
            } else {
                cout << ans1;
            }
            cout << '\n';
        }
        return 0;
    }
    int ans0 = 0;
    int ans1 = 0;
    int ans2 = 0;
    int ans12 = 0;
    for (int i = 0; i < n; i++) {
        ans0 += binpow(v[i], i+1);
    }
    reverse(v.begin(), v.end());
    for (int i = 0; i < n; i++) {
        ans1 += binpow(v[i], i+1);
    }
    for (int j = 0; j < n; j++) {
        v[j] = n - v[j] + 1;
    }
}
