#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <chrono>
#include <ctime>
#include <random>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
#define rep(n) for (int rep_i = 0; rep_i < n; rep_i++)
#define cin(v) for (auto& e : v) cin >> e;
#define cout(v) for (auto e : v) cout << e << " "; cout << endl;
using ll = long long;
using ull = unsigned long long;
using db = double;
using i32 = int32_t;
using vi = vector <int>;
using vll = vector <ll>;
using pii = pair <int, int>;
using pll = pair <ll, ll>;
#define sq(x) ((x) * (x))
mt19937 rng(time(0));
int rand(int l, int r) {
	return (rng() % (r - l + 1)) + l;
}
void fastw() {
	ios_base::sync_with_stdio(0); cin.tie(0);
}

void solve();

signed main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	fastw();
	solve();
}

const int md = 998244353;

int binpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) {
			res = (res * a) % md;
		}
		a = (a * a) % md;
		b >>= 1;
	}

	return res;
}

void solve() {
	//int n, q;
	//cin >> n >> q;
	//vector <int> a(n);
	//cin(a);

	//rep(q) {
	//	int t, x; cin >> t >> x;
	//	if (t == 1) {
	//		swap(a[x - 1], a[x]);
	//	}
	//	else {
	//		vector <int> cols(n + 1);
	//		x--;
	//		if (x == 0) {
	//			cout << 1 << endl;
	//			continue;
	//		}

	//		for (int i = 0; i < x; i++) {
	//			cols[a[i]]++;
	//		}
	//		int nd = x / 2 + 1;
	//		int mx = 0;
	//		int mxc = 1;
	//		for (int c = 1; c <= n; c++) {
	//			//mx = max(mx, a[c]);
	//			if (cols[c] > mx) {
	//				mx = cols[c];
	//				mxc = c;
	//			}
	//		}
	//		if (mx > nd) {
	//			int ost = x - mx;
	//			if (mxc != a[x]) {
	//				cout << ost * 2 + 2 << endl;
	//			}
	//			else {
	//				              
	//			}

	//		}
	//		else {
	//			if (a[x - 1] == a[x]) {
	//				bool fl = 0;
	//				for (int i = x + 1; i < n; i++) {
	//					if (a[i] != a[x]) fl = 1;
	//				}
	//				if (fl) {
	//					cout << x + 2 << endl;
	//				}
	//				else {
	//					cout << x + 1 << endl;
	//				}
	//			}
	//			else {
	//				cout << x + 1 << endl;
	//			}
	//		}
	//	}
	//}

	int n, q; cin >> n >> q;
	vector <int> p(n); cin(p);
	vector <int> b(q); cin(b);
	vector <int> orig = p;
	auto get = [&](const vector<int>& A) {
		int r = 0;
		for (int i = 0; i < n; i++) {
			r += binpow(A[i], i + 1);
			r %= md;
		}
		return r;
	};

	auto _2 = [&](vector <int>& A) {
		for (int i = 0; i < n; i++) {
			A[i] = n - A[i] + 1;
		}
	};

	if (n <= 1000 && q <= 1000) {
		for (auto qr : b) {
			int r = 0;
			if (qr == 1) {
				reverse(all(p));
			}
			else if (qr == 2) {
				for (int i = 0; i < n; i++) {
					p[i] = n - p[i] + 1;
				}
			}
			else {
				vector <int> nw(n);
				for (int i = 0; i < n; i++) {
					nw[p[i] - 1] = i + 1;
				}
				p = nw;
			}
			for (int i = 0; i < n; i++) {
				r += binpow(p[i], i + 1);
				r %= md;
			}
			cout << r << " ";
		}
		cout << endl;
		return;
	}

	if (*max_element(all(b)) == *min_element(all(b))) {
		int t = b[0];
		int st = 0;

		for (int i = 0; i < n; i++) {
			st += binpow(p[i], i + 1);
			st %= md;
		}

		int r = 0;
		if (t == 1) {
			reverse(all(p));
		}
		else if (t == 2) {
			for (int i = 0; i < n; i++) {
				p[i] = n - p[i] + 1;
			}
		}
		else {
			vector <int> nw(n);
			for (int i = 0; i < n; i++) {
				nw[p[i] - 1] = i + 1;
			}
			p = nw;
		}

		for (int i = 0; i < n; i++) {
			r += binpow(p[i], i + 1);
			r %= md;
		}

		int fl = 0;
		rep(q) {
			if (fl) {
				cout << st << " ";
			}
			else {
				cout << r << " ";
			}
			fl ^= 1;
		}
		return;
	}

	if (*max_element(all(b)) <= 2) {
		p = orig;
		reverse(all(p));
		int fir = get(p);
		//cout << fir << endl;
		vector <int> al = { fir };
		_2(p);
		int cur = get(p);
		int fl = 0;
		while (cur != fir) {
			al.push_back(cur);
			if (fl) {
				_2(p);
			}
			else {
				reverse(all(p));
			}
			cur = get(p);
			fl ^= 1;
		}
		
		p = orig;
		_2(p);
		fir = get(p);
		vector <int> al2 = { fir };
		reverse(all(p));
		cur = get(p);
		fl = 0;
		while (cur != fir) {
			al2.push_back(cur);
			if (fl) {
				reverse(all(p));
			}
			else {
				_2(p);
			}

			cur = get(p);
			fl ^= 1;
		}

		vector <int> ans(q);
		/*cout << endl;
		cout(al);
		cout(al2);
		cout << endl;*/
		int sus = 1;
		// if (b[0] == 2) sus = 2;
		int last_1 = -1, last_2 = -1;
		int FIRST = get(orig);
		bool ok = 0, ok2 = 0, ok3 = 0;
		int F = 0;
		int S = 0;
		for (int i = 0; i < q; i++) {
			int qr = b[i];

			if (ok) {
				if (sus == 1) sus = 2;
				else sus = 1;
			}

			int j = i;
			int kol = 0;
			while (j < q && b[i] == b[j]) {
				kol++; j++;
			}
			j--;
			int st = 0, st2 = 0;
			if (i == 0) {
				if (b[0] == 1) st = al[0];
				else st = al2[0];
				st2 = FIRST;
			}
			else {
				if (sus == 1) {
					st = find(all(al), ans[i - 1]) - al.begin();
					st++; st %= al.size();
					st = al[st];
				}
				else {
					st = find(all(al2), ans[i - 1]) - al2.begin();
					st++; st %= al2.size();
					st = al2[st];
				}
				st2 = ans[i - 1];
			}
			int fl = 1;
			for (int p = i; p <= j; p++) {
				if (fl) {
					ans[p] = st;
				}
				else {
					ans[p] = st2;
				}
				fl ^= 1;
			}
			

			i = j;

			if (kol & 1 ^ 1) {
				ok = 1;
			}
			else {
				ok = 0;
			}


			
		}
		for (auto e : ans) {
			cout << e << " ";
		}
		cout << endl;
		return;
	}
	//p = orig;
	int fir = get(p);
	reverse(all(p));
	int sec = get(p);
	reverse(all(p));
	int cur = fir;
	for (int i = 0; i < q; i++) {
		int qr = b[i];
		if (qr == 3) {
			cout << cur << " ";
		}
		else {
			if (cur == fir) cur = sec;
			else cur = fir;

			cout << cur << " ";
		}
	}
	cout << endl;
	// 3225 215 1175 303 3225 215
}