#include <bits/stdc++.h>

using namespace std;

long long MOD = 998244353;

long long binary_pow(long long x, long long y){
    if (y == 0){
        return 1;
    }

    long long tmp = binary_pow(x, y/2);

    if (y % 2 == 0){
        return tmp*tmp%MOD;
    } else {
        return tmp*tmp%MOD*x%MOD;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, q;

    cin >> n >> q;

    vector<long long> lst_els(n+1, 0);

    for (int i = 1; i <= n; ++i){
        cin >> lst_els[i];
    }
    
    if (n <= 1000 && q <= 1000){
        for (int i = 0; i < q; ++i){
            int type;
            cin >> type;
            vector<long long> new_lst(n+1, 0);

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

            long long ans = 0;

            for (int j = 1; j <= n; ++j){
                ans = (ans+binary_pow(new_lst[j], j))%MOD;
            }

            cout << ans << " ";
            swap(lst_els, new_lst);
            new_lst.clear();
        }
    } else {
        long long change1 = 0;
        long long change2 = 0;
        long long change3 = 0;
        long long ans = 0;

        vector<long long> new1(n+1, 0);
        vector<long long> new2(n+1, 0);
        vector<long long> new3(n+1, 0);

        for (int j = 1; j <= n; ++j){
            new1[j] = lst_els[n-j+1];
            new2[j] = n-lst_els[j]+1;
            new3[lst_els[j]] = j;
        }

        for (int j = 1; j <= n; ++j){
            ans = (ans+binary_pow(lst_els[j], j))%MOD;
            change1 = (change1+binary_pow(new1[j], j))%MOD;
            change2 = (change2+binary_pow(new2[j], j))%MOD;
            change3 = (change3+binary_pow(new3[j], j))%MOD;
        }

        int cnt1 = 0;
        int cnt2 = 0;
        int cnt3 = 0;

        for (int i = 0; i < q; ++i){
            int type;
            cin >> type;

            if (type == 1){
                cnt1++;
                if (cnt1%2 == 0){
                    cout << ans << "\n";
                } else {
                    cout << change1 << "\n";
                }
            } else if (type == 2){
                cnt2++;
                if (cnt2%2 == 0){
                    cout << ans << "\n";
                } else {
                    cout << change2 << "\n";
                }
            } else {
                cnt3++;
                if (cnt3 % 2 == 0){
                    cout << ans << "\n";
                } else {
                    cout << change3 << "\n";
                }
            }
        }
    }
    

}