#include <iostream>
#include <vector>
#include <algorithm>

#define int long long

using namespace std;
const int MOD = 998244353;

int mul(int a, int b) {
    return (long long)a * b % MOD;
}

int bin_pow(int a, int n) {
    if (n == 0) return 1;
    if (n == 1) return a;
    if (n % 2 == 0) {
        int ax = bin_pow(a, n / 2);
        return mul(ax, ax);
    } else {
        return mul(a, bin_pow(a, n - 1));
    }
}

int add(int a, int b) {
    if (a + b >= MOD) return a - MOD + b;
    return a + b;
}

int get(int n, vector<int> &a) {
    int cur = 0;
    for (int i = 0; i < n; i++) {
        cur = add(cur, bin_pow(a[i], i + 1));
    }
    return cur;
}

void solve(int n, int q, vector<int> &a, vector<int> &b) {
    if (b[0] == 1) {
        int cur1 = get(n, a);
        reverse(a.begin(), a.end());
        int cur2 = get(n, a);
        for (int i = 0; i < n; i++) {
            if (i % 2 == 1) cout << cur1 << " ";
            else cout << cur2 << " ";
        }
        cout << endl;
    }
    if (b[0] == 2) {
        int cur1 = get(n, a);
        for (int i = 0; i < n; i++) a[i] = n + 1 - a[i];
        int cur2 = get(n, a);
        for (int i = 0; i < n; i++) {
            if (i % 2 == 1) cout << cur1 << " ";
            else cout << cur2 << " ";
        }
        cout << endl;
    }
    if (b[0] == 3) {
        int cur1 = get(n, a);
        vector<int> c(n);
        for (int i = 0; i < n; i++) c[a[i] - 1] = i + 1;
        int cur2 = get(n, c);
        for (int i = 0; i < n; i++) {
            if (i % 2 == 1) cout << cur1 << " ";
            else cout << cur2 << " ";
        }
        cout << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> b(n);
    bool f2 = true;
    int last = -1;
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        if (last == -1) last = b[i];
        else f2 &= (last == b[i]);
    }
    if (f2) {
        solve(n, q, a, b);
        return 0;
    }
    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            reverse(a.begin(), a.end());
        }
        if (t == 2) {
            for (int i = 0; i < n; i++) {
                a[i] = n + 1 - a[i];
            }
        }
        if (t == 3) {
            vector<int> b(n);
            for (int i = 0; i < n; i++) {
                b[a[i] - 1] = i + 1;
            }
            a = b;
        }
        cout << get(n, a) << endl;
    }
    cout << endl;
    return 0;
}
