#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <climits>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <vector>
#pragma GCC optimize("Ofast")
using namespace std;
using ll = long long;
using ld = long double;
const ll maxn = 5'000, mod = 998'244'353;
ll pv[maxn][maxn];
ll pp(ll val, ll pp1) {
	ll ans = 1;
	ll start = val;
	while (pp1 != 1) {
		if (pp1 % 2 == 1) {
			ans = (ans * start) % mod;
			pp1--;
		}
		else {
			start = (start * start) % mod;
			pp1 /= 2;
		}
	}
	ans = (ans * start) % mod;
	return ans;
}
ll calc(vector<ll>& a) {
	ll ans = 0;
	for (int i = 0; i < a.size(); ++i) {
		ll cur = pp(a[i], i + 1);
		ans = (ans + cur) % mod;
	}
	return ans;
}
bool f = 0;
map<vector<ll>, vector<vector<ll>>> cur;
void rec(vector<ll> a, vector<ll> cmds) {
	if (cur.find(a) != cur.end()) {
		cur[a].push_back(cmds);
		return;
	}
	cur[a].push_back(cmds);
	if (cmds.size() > 10) {
		f = 1;
		return;
	}
	cmds.push_back(1);
	reverse(a.begin(), a.end());
	rec(a, cmds);
	reverse(a.begin(), a.end());
	cmds.pop_back();
	vector<ll> b(a.size());
	for (int i = 0; i < a.size(); ++i) {
		b[i] = a.size() - a[i] + 1;
	}
	swap(a, b);
	cmds.push_back(2);
	rec(a, cmds);
	for (int i = 0; i < a.size(); ++i) {
		b[i] = a.size() - a[i] + 1;
	}
	swap(a, b);
	cmds.pop_back();

	cmds.push_back(3);
	for (int i = 0; i < a.size(); ++i) {
		b[a[i] - 1] = i + 1;
	}
	swap(a, b);

	rec(a, cmds);
}


int main() {
	cin.tie(0)->sync_with_stdio(false);
	ll n, q; cin >> n >> q;
	vector<ll> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i];
	/*int cmd; cin >> cmd;
	ll ans2 = calc(a);
	ll ans1;
	if (cmd == 1) {
		reverse(a.begin(), a.end());
		ans1 = calc(a);
	}
	else if (cmd == 2) {
		vector<ll> b(n);
		for (int i = 0; i < n; ++i) {
			b[i] = n - a[i] + 1;
		}
		swap(a, b);
		ans1 = calc(a);
	}
	else {
		vector<ll> b(n);
		for (int i = 0; i < n; ++i) {
			b[a[i] - 1] = i + 1;
		}
		swap(a, b);
		ans1 = calc(a);
	}
	for (int i = 0; i < q; ++i) {
		if (i % 2 == 0) {
			cout << ans1;
		}
		else {
			cout << ans2;
		}
		cout << ' ';
	}
	return 0;
	rec(a, {});
	int qq = 0;
	for (int i = 0; i < q; ++i) {
		int cmd; cin >> cmd;
		if (cmd == 1) {
			reverse(a.begin(), a.end());
		}
		else if (cmd == 2) {
			vector<ll> b(n);
			for (int i = 0; i < n; ++i) {
				b[i] = n - a[i] + 1;
			}
			swap(a, b);
		}
		else {
			vector<ll> b(n);
			for (int i = 0; i < n; ++i) {
				b[a[i]-1] = i+1;
			}
			swap(a, b);
		}
		for (int i = 0; i < n; ++i) {
			cout << a[i] << ' ';
		}
		cout << endl;
	}
	return 0;*/
	if (n <= 1000 && q <= 1000) {
		for (int i = 0; i < q; ++i) {
			int cmd; cin >> cmd;
			if (cmd == 1) {
				reverse(a.begin(), a.end());
			}
			else if (cmd == 2) {
				vector<ll> b(n);
				for (int i = 0; i < n; ++i) {
					b[i] = n - a[i] + 1;
				}
				swap(a, b);
			}
			else {
				vector<ll> b(n);
				for (int i = 0; i < n; ++i) {
					b[a[i] - 1] = i + 1;
				}
				swap(a, b);
			}
			cout << calc(a) << '\n';
		}
		return 0;
	}
	map<vector<ll>, ll> cc;
	ll ans = calc(a);
	cc[{0, 0, 0}] = ans;
	if (1) {
		reverse(a.begin(), a.end());
		ans = calc(a);
		cc[{1, 0, 0}] = ans;
		reverse(a.begin(), a.end());
	}
	if (1) {
		vector<ll> b(n);
		for (int i = 0; i < n; ++i) {
			b[i] = n - a[i] + 1;
		}
		swap(a, b);
		ans = calc(a);
		cc[{0, 1, 0}] = ans;
		reverse(a.begin(), a.end());
		ans = calc(a);
		cc[{1, 1, 0}] = ans;


		reverse(a.begin(), a.end());
		for (int i = 0; i < n; ++i) {
			b[i] = n - a[i] + 1;
		}
		swap(a, b);
	}

	vector<ll> b(n);
	for (int i = 0; i < n; ++i) {
		b[a[i] - 1] = i + 1;
	}
	swap(a, b);
	ans = calc(a);
	cc[{0, 0, 1}] = ans;
	if (1) {
		reverse(a.begin(), a.end());
		ans = calc(a);
		cc[{1, 0, 1}] = ans;
		reverse(a.begin(), a.end());
	}
	if (1) {
		vector<ll> b(n);
		for (int i = 0; i < n; ++i) {
			b[i] = n - a[i] + 1;
		}
		swap(a, b);
		ans = calc(a);
		cc[{0, 1, 1}] = ans;
		reverse(a.begin(), a.end());
		ans = calc(a);
		cc[{1, 1, 1}] = ans;


		reverse(a.begin(), a.end());
		for (int i = 0; i < n; ++i) {
			b[i] = n - a[i] + 1;
		}
		swap(a, b);
	}




	ll p1 = 0, p2 = 0, p3 = 0;
	for (int i = 0; i < q; ++i) {
		int cmd; cin >> cmd;
		if (cmd == 1) {
			p1 = (p1 + 1) % 2;
		}
		else if (cmd == 2) {
			p2 = (p2 + 1) % 2;
		}
		else {
			p3 = (p3 + 1) % 2;
		}
		vector<ll> cur = { p1, p2, p3 };
		cout << cc[cur] << '\n';
	}
}
