#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <random>
#include <cmath>

using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("avx2")

#define int long long
#define all(a) a.begin(),a.end()
#define endl '\n'
#define pii pair<int, int>
#define pb emplace_back
typedef long double ld;

int const N = 2e5, INF = 2e9;
int mod = 998244353, mod2 = 1e9 + 9;
int P = 1e9 + 7;

int add(int a, int b) {
	return (a + b) % mod2;
}

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

int sub(int a, int b) {
	a -= b;
	if (a < 0) a += mod2;
	return a;
}

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

struct go {
	int b1 = -1, b2 = -1, b3 = -1;
};

unordered_map<int, go> h; // 
unordered_map<int, int> res; // val of hash

int n = 5;

void rec(vector<int> a, int depth = 0) {
	int val = 0;
	for (int i = 0; i < n; ++i) {
		val = (val + binpow(a[i], i + 1)) % mod;
	}
	int hsha = a[0];
	for (int i = 0; i < n; ++i) {
		hsha = add(mul(hsha, P), a[i]);
	}
	res[hsha] = val;
	if (depth == 8) return;
	
	// 1st op
	auto b = a;
	reverse(all(b));
	int hshb = b[0];
	for (int i = 0; i < n; ++i) {
		hshb = add(mul(hshb, P), b[i]);
	}
	if (h[hsha].b1 == -1) {
		h[hsha].b1 = hshb;
		rec(b, depth + 1);
	}
	
	//2nd op

	vector<int> c(n);
	for (int i = 0; i < n; ++i) {
		c[i] = n - a[i] + 1;
	}
	int hshc = c[0];
	for (int i = 0; i < n; ++i) {
		hshc = add(mul(hshc, P), c[i]);
	}
	if (h[hsha].b2 == -1) {
		h[hsha].b2 = hshc;
		rec(c, depth + 1);
	}
	
	//3rd op
	vector<int> d(n);
	
	for (int i = 0; i < n; ++i) {
		d[a[i] - 1] = i + 1;
	}
	int hshd = d[0];
	for (int i = 0; i < n; ++i) {
		hshd = add(mul(hshd, P), d[i]);
	}
	if (h[hsha].b3 == -1) {
		h[hsha].b3 = hshd;
		rec(d, depth + 1);
	}
}


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

	//vector<int> t = { 1, 2, 3, 4, 5 };
	//rec(t);

	int q; cin >> n >> q;

	vector<int> a(n);
	for (int& i : a) cin >> i;
	rec(a);

	int hsha = a[0];
	for (int i = 0; i < n; ++i) {
		hsha = add(mul(hsha, P), a[i]);
	}
	vector<int> ans;
	for (int i = 0; i < q; ++i) {
		int t; cin >> t;
		if (t == 1) {
			hsha = h[hsha].b1;
		}
		if (t == 2) {
			hsha = h[hsha].b2;
		}
		if (t == 3) {
			hsha = h[hsha].b3;
		}
		ans.pb(res[hsha]);
	}

	for (int i : ans) {
		cout << i << ' ';
	}

	return 0;
}