#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>

constexpr long long MD = 998244353;

long long fastpow(long long a, long long p) {
    long long res = 1;
    while (p) {
        if (p & 1) {
            res = (res * a) % MD;
        }
        a = (a * a) % MD;
        p >>= 1;
    }
    return res;
}

long long reservedans[4];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n, q;
    std::cin >> n >> q;
    std::vector<int> p(n);
    for (int i = 0; i < n; i++) std::cin >> p[i];
    long long ans = 0, revans = 0;
    int prevop = -1;
    {
        std::vector<int> cp = p;
        for (int i = 0; i < n; i++) {
            reservedans[0] = (reservedans[0] + fastpow(cp[i], i + 1)) % MD;
        }
        std::reverse(cp.begin(), cp.end());

        for (int i = 0; i < n; i++) {
            reservedans[1] = (reservedans[1] + fastpow(cp[i], i + 1)) % MD;
        }
        std::reverse(cp.begin(), cp.end());
        for (int i = 0; i < n; i++) cp[i] = n - cp[i] + 1;
        for (int i = 0; i < n; i++) {
            reservedans[2] = (reservedans[2] + fastpow(cp[i], i + 1)) % MD;
        }
        std::reverse(cp.begin(), cp.end());
        for (int i = 0; i < n; i++) {
            reservedans[3] = (reservedans[3] + fastpow(cp[i], i + 1)) % MD;
        }
    }
    std::vector<int> qv(q);
    bool flag = true;
    for (int i = 0; i < q; i++) {
        std::cin >> qv[i];
        if (qv[i] == 3) flag = false;
    }
    if (flag) {
        int b1 = 0, b2 = 0;
        for (int b : qv) {
            if (b == 1) b1++;
            if (b == 2) b2++;
            std::cout << reservedans[(b2 % 2) * 2 + (b1 % 2)] << '\n';
        }
    } else {
        for (int b : qv) {
            if (prevop == b) {
                std::cout << revans << '\n';
                std::swap(revans, ans);
            } else if (b == 1) {
                ans = revans = 0;
                std::reverse(p.begin(), p.end());
                for (int i = 0; i < n; i++) {
                    ans = (ans + fastpow(p[i], i + 1)) % MD;
                    revans = (revans + fastpow(p[i], n - i)) % MD;
                }
                std::cout << ans << ' ';
                prevop = b;
            } else if (b == 2) {
                ans = revans = 0;
                for (int i = 0; i < n; i++) {
                    revans = (revans + fastpow(p[i], i + 1)) % MD;
                    p[i] = n - p[i] + 1;
                    ans = (ans + fastpow(p[i], i + 1)) % MD;
                }
                std::cout << ans << ' ';
                prevop = b;
            } else {
                ans = revans = 0;
                std::vector<int> temp(n);
                for (int i = 0; i < n; i++) {
                    temp[p[i] - 1] = i + 1;
                    revans = (revans + fastpow(p[i], i + 1)) % MD;
                }
                p = std::move(temp);
                for (int i = 0; i < n; i++) {
                    ans = (ans + fastpow(p[i], i + 1)) % MD;
                }
                std::cout << ans << ' ';
                prevop = b;
            }
        }
    }
}
