#include "iostream"
#include "vector"
#include "algorithm"

using ll = long long;

const int mod = 119 << 23 | 1;

int add(int a, int b){
    return a + b - mod * (a + b >= mod);
}

int mul(int a, int b){
    return (int)((ll) a * b % mod);
}

int bin_pow(int a, int b){
    int res =1 ;
    while(b){
if(b & 1){
    res = mul(res, a);
}
a = mul(a, a);
b >>= 1;
    }

return res;
}

bool check(const std::vector<int> &a){
for(int i = 0; i < (int)a.size(); ++i){
    if(a[i] != i){
        return false;
    }
}
return true;
}

signed main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n), b(q);
    for(auto &i : a){
        std::cin >> i;
        --i;
    }
    for(auto &i : b){
        std::cin >> i;
    }
    if(check(a)){
        bool norm = true;
        int ans1 = 0, ans2 = 0;
        for(int i = 0; i < n; ++i){
            ans1 = add(ans1, bin_pow(i + 1, i + 1));
            ans2 = add(ans2, bin_pow(n - i, i + 1));
        }
        for(int i =0; i < q; ++i){
            if(b[i] == 1){
                if(norm){
                    norm = false;
                }else{
                    norm = true;
                }
            }else if(b[i] == 2){
                if(norm){
                    norm = false;
                }else{
                    norm = true;
                }
            }else{
                if(norm){
                    norm = true;
                }else{
                    norm = false;
                }
            }
            if(norm){
                std::cout << ans1 << ' ';
            }else{
                std::cout << ans2 << ' ';
            }
        }
        std::cout << '\n';
        return 0;
    }
    if(*std::max_element(b.begin(), b.end()) <= 2){
        std::vector<std::vector<int>> ans(2);
        for(int i = 0; i < n; ++i){
            ans[0][0] = add(ans[0][0], bin_pow(a[i] + 1, i + 1));
            ans[0][1] = add(ans[0][1], bin_pow(a[n - i - 1] + 1, i + 1));
            ans[1][0] = add(ans[1][0], bin_pow(n - a[i], i + 1));
            ans[1][1] = add(ans[1][1], bin_pow(n - a[n - i - 1], i + 1));
        }
        int cnt_rev = 0, cnt_change = 0;
        for(int i = 0;i < n; ++i){
            if(b[i] == 1){
                ++cnt_rev;
            }else{
                ++cnt_change;
            }
            std::cout << ans[cnt_change][cnt_rev] << ' ';
        }
        return 0;
    }
    if(n * q <= 1000000){
        for(int it = 0; it < q; ++it){
            if(b[it] == 1){
                std::reverse(a.begin(), a.end());
            } else if(b[it] == 2) {
                for(int i =0; i < n; ++i){
                    a[i] = n - 1 - a[i];
                }
            } else{
                std::vector<int> q(n);
                for(int i = 0;i < n; ++i){
                    q[a[i]] = i;
                }
                a = q;
            }
            int ans = 0;
            for (int i= 0; i < n; ++i){
                ans = add(ans, bin_pow(a[i] + 1, i + 1));
            }
            std::cout << ans << ' ';
        }
        return 0;
    }
    return 0;
}