#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <random>
using namespace std;

#define int long long

const int Mod = 998'244'353;
const int Mx = 1e6 + 10;
int Qes[Mx];
int P[Mx], Qs[Mx];
int Ans[Mx];
bool f2 = true, f4 = true;
int N, Q;

int to_P(int x, int p) {
    //cout << p << endl;
    if (p == 0) {
        return 1;
    }
    if (p == 1) {
        return x;
    }
    return ((__int128)to_P(x, p / 2) * to_P(x, p / 2) * to_P(x, p % 2)) % Mod;
}

void print() {
    for (int i = 1; i <= N; i++) {
        cout << P[i] << ' ';
    }
    cout << endl;
}

int find_sum() {
    int s = 0;
    for (int i = 1; i <= N; i++) {
        s += to_P(P[i], i);
        s %= Mod;
    }
    return s;
}

void cntF(int I) {
    int par = Qes[I];
    for (int i = 1; i <= N; i++) {
        if (par == 1) {
            Qs[i] = P[N - i + 1];
        }
        else if (par == 2) {
            Qs[i] = N - P[i] + 1;
        }
        else {
            Qs[P[i]] = i;
        }
    }
    for (int i = 1; i <= N; i++) {
        P[i] = Qs[i];
    }
    //print();
    Ans[I] = find_sum();
}

signed main() {
    cin >> N >> Q;
    for (int i = 1; i <= N; i++) {
        cin >> P[i];
        if (P[i] != i) {
            f4 = false;
        }
    }
    for (int i = 0; i < Q; i++) {
        cin >> Qes[i];
        if (i && Qes[i] != Qes[i-1]) {
            f2 = false;
        }
    }
    if (Q > 4 && N > 4 && f2) {
        cntF(0);
        cntF(1);
        for (int i = 2; i < Q; i++) {
            Ans[i] = Ans[i % 2];
        }
    }
    if (Q > 4 && N > 4 && f4) {
        //cout << "f4: ";
        bool rev = false;
        int cnt1, cnt2;
        cnt1 = find_sum();
        reverse(P + 1, P + N + 1);
        cnt2 = find_sum();
        reverse(P + 1, P + N + 1);
        for (int i = 0; i < Q; i++) {
            if (Qes[i] < 3) {
                rev ^= 1;
            }
            if (rev) {
                Ans[i] = cnt2;
            }
            else {
                Ans[i] = cnt1;
            }
        }
    }
    else {
        for (int I = 0; I < Q; I++) {
            cntF(I);
        }
    }
    for (int i = 0; i < Q; i++) {
        cout << Ans[i] << '\n';
    }
}

/*
5 5
1 5 2 3 4
2 2 2 2 2
*/

/*
10 6
1 5 2 3 4 6 9 8 7 10
3 3 3 3 3 3
*/

