#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pll=pair<ll,ll>;
using dbl=double;
dbl const PI=acos(-1.0);
ll const mod=998244353;
void gg(){
    cout<<1<<endl;
}
ll bit(ll x,ll i){
    return((x>>i)&1);
}
ll binpow(ll a,ll b){
    ll x=1;
    for(ll i=0;i<40;i++){
        if(bit(b,i)){
            x*=a;
            x%=mod;
        }
        a=(a*a)%mod;
    }
    return x;
}
ll f(vector<ll>& a,ll n){
    ll ans=0;
    for(ll i=1;i<=n;i++){
        ans=(ans+binpow(a[i],i))%mod;
    }
    return ans;
}

void solve(){
    ll n,q;
    cin>>n>>q;
    vector<ll> a(n+1);
    for(ll i=1;i<=n;i++){
        cin>>a[i];
    }
    ll cnt=1,num=1;
    vector<vector<ll>> nxt(2*q+3,vector<ll>(4,-1));
    vector<ll> ans(2*q+3);
    vector<vector<ll>> ar(2*q+3);
    map<ll,vector<ll>> val;
    ar[1]=a;
    ans[1]=f(a,n);
    val[ans[1]].push_back(1);
    while(q--){
        ll tp;
        cin>>tp;
        if(nxt[num][tp]==-1){
            cnt++;
            a=ar[num];
            vector<ll> b(n+1);
            for(ll i=1;i<=n;i++){
                if(tp==1){
                    b[i]=a[n-i+1];
                }
                else if(tp==2){
                    b[i]=n-a[i]+1;
                }
                else{
                    b[a[i]]=i;
                }
            }
            ll cur=cnt;
            ll x=f(b,n);
            for(ll i:val[x]){
                if(val[x].size()==1){
                    cur=i;
                    break;
                }
                if(ar[i]==b){
                    cur=i;
                    break;
                }
            }
            ans[cur]=x;
            nxt[num][tp]=cur;
            val[x].push_back(cur);
            ar[cur]=b;
        }
        num=nxt[num][tp];
        cout<<ans[num]<<'\n';
        /*for(ll i=1;i<=n;i++){
            cout<<ar[num][i]<<' ';
        }
        cout<<'\n';*/
    }
}

int main()
{
    ll tqqq=1;
    //cin>>tqqq;
    while(tqqq--){
        solve();
        cout<<'\n';
    }

    return 0;
}
