#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;
#define sz(x) (int)(x.size())
#define all(x) x.begin(), x.end()
//#define endl "\n"

template<class T>
istream& operator >> (istream& in, pair<T, T>& a) {
    in >> a.first >> a.second;
    return in;
}
template<class T>
istream& operator >> (istream& in, vector<T>& a) {
    for (T& x : a){
        in >> x;
    }
    return in;
}
template<class T>
ostream& operator << (ostream& out, pair<T, T> a) {
    out << a.first << " " << a.second << " ";
    return out;
}
template<class T>
ostream& operator << (ostream& out, vector<T> a) {
    for (auto& x : a) {
        out << x << " ";
    }
    return out;
}
#define debug(x) cout << (#x) << ": " << (x) << endl

constexpr int mod = 998244353;
int n;

int binpow(int a, int x) {
    int res = 1;
    while (x > 0) {
        if (x % 2 == 1) {
            res *= a;
            res %= mod;
        }
        x /= 2;
        a *= a;
        a %= mod;
    }
    return res;
}

int calc(vi& a, vector<vi>& pp) {
    int res = 0;
    for (int i = 0; i < n; i++) {
        res += pp[a[i]][i + 1];
        if (res >= mod) {
            res -= mod;
        }
    }
    return res;
}
int calc(vi& a) {
    int res = 0;
    for (int i = 0; i < n; i++) {
        res += binpow(a[i], i + 1);
        if (res >= mod) {
            res -= mod;
        }
    }
    return res;
}

vi brute(int q, vi a, vi& qq) {
    //set<int> st;
    vector<vi> pp(n + 1, vi(n + 1));
    for (int x = 1; x <= n; x++) {
        pp[x][0] = 1;
        for (int pw = 1; pw <= n; pw++) {
            pp[x][pw] = pp[x][pw - 1] * x % mod;
        }
    }
    vi b(n);
    vi ans(q);
    for (int qu = 0; qu < q; qu++) {
        if (qq[qu] == 1) {
            reverse(all(a));
        }
        if (qq[qu] == 2) {
            for (int i = 0; i < n; i++) {
                a[i] = n - a[i] + 1;
            }
        }
        if (qq[qu] == 3) {
            for (int i = 0; i < n; i++) {
                b[a[i] - 1] = i + 1;
            }
            swap(a, b);
        }
        // debug(a);
        // debug(calc(a, pp));
        ans[qu] = calc(a);
        //debug(st.size());
    }
    return ans;
}

vi solve2(int q, vi a, vi& qq) {
    vi ans(q);
    int val0 = calc(a), val1 = 0;

    if (qq[0] == 1) {
        reverse(all(a));
    }
    if (qq[0] == 2) {
        for (int i = 0; i < n; i++) {
            a[i] = n - a[i] + 1;
        }
    }
    if (qq[0] == 3) {
        vi b(n);
        for (int i = 0; i < n; i++) {
            b[a[i] - 1] = i + 1;
        }
        swap(a, b);
    }
    val1 = calc(a);

    for (int qu = 1; qu <= q; qu++) {
        if (qu % 2 == 0) {
            ans[qu - 1] = val0;
        }
        else {
            ans[qu - 1] = val1;
        }
    }
    return ans;
}


void solve() {
    int q; cin >> n >> q;
    vi a(n); cin >> a;

    // set<int> st;
    //
    // vector<vi> pp(n + 1, vi(n + 1));
    // for (int x = 1; x <= n; x++) {
    //     pp[x][0] = 1;
    //     for (int pw = 1; pw <= n; pw++) {
    //         pp[x][pw] = pp[x][pw - 1] * x % mod;
    //     }
    // }
    // vi b(n);
    // vi ans(q);
    // for (int qu = 0; qu < q; qu++) {
    //     int t; cin >> t;
    //     if (t == 1) {
    //         reverse(all(a));
    //     }
    //     if (t == 2) {
    //         for (int i = 0; i < n; i++) {
    //             a[i] = n - a[i] + 1;
    //         }
    //     }
    //     if (t == 3) {
    //         for (int i = 0; i < n; i++) {
    //             b[a[i] - 1] = i + 1;
    //         }
    //         swap(a, b);
    //     }
    //     debug(a);
    //     debug(calc(a));
    //     ans[qu] = calc(a);
    //     st.insert(ans[qu]);
    //     int cnt = (int)st.size();
    //     debug(cnt);
    // }
    //



    vi qq(q); cin >> qq;
    bool flag2 = *min_element(all(qq)) == *max_element(all(qq));
    if (flag2) {
        cout << solve2(q, a, qq) << endl;
        return;
    }

    if (n <= 1000 && q <= 1000) {
        cout << brute(q, a, qq) << endl;
        return;
    }


}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}
