#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2")
#pragma GCC optimize("Ofast,unroll-loops")
//#define int long long
using namespace std;
using ll = long long;
using ld = long double;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
/*ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}
vector<vector<int>> g;

void dfs(int u, int c, vector<char>& used, vector<int>& color) {
	used[u] = 1;
	color[u] = c;
	for (int v : g[u]) {
		if (!used[v]) {
			dfs(v, c, used, color);
		}
	}
}*/
vector<int> a, newa, cur, countn;
deque<int> wait;
void change(int i) {
	int copy = a[i];
	a[i] = a[i + 1];
	a[i + 1] = copy;

	newa[0] = cur[0];
	int goal = a[0], count = 1; deque<int> wait(0);
	for (int i = 1; i < sz(a); ++i) {
		if (!wait.empty()) {
			if (a[wait.front()] != goal) {
				newa[count] = wait.front() + 1;
				goal = a[wait.front()];
				wait.pop_front();
				count++;
			}
		}
		if (a[i] != goal) {
			goal = a[i];
			newa[count] = i + 1;
			++count;
		}
		else {
			wait.push_back(i);
		}
	}
	while (!wait.empty()) {
		newa[count] = wait.front() + 1;
		wait.pop_front();
		++count;
	}
	/*for (int elem : newa) {
		cout << elem << " ";
	}*/
	for (int i = 0; i < sz(a); ++i) {
		countn[newa[i] - 1] = i;
	}
	swap(newa, cur);
	/*cout << "\n";
	for (int i = 0; i < n; ++i) {
		cout << cur[i] << " ";
	}
	cout << "\n";*/
}
int one() {
	int ans = 0;
	int n = sz(a);
	newa.resize(0);
	newa.resize(n);
	for (int i = 0; i < n; ++i) {
		newa[i] = a[n - 1 - i];
		//cout << newa[i] << " ";
		ans += (int)pow(newa[i], i+1);
	}
	/*cout << "\n";
	for (int i = 0; i < n; ++i) {
		cout << newa[i] << " ";
	}
	cout << "\n";*/
	swap(a, newa);
	return ans;
}
int two() {
	int ans = 0;
	int n = sz(a);
	newa.resize(0);
	newa.resize(n);
	for (int i = 0; i < n; ++i) {
		newa[i] = n - a[i] + 1;
		//cout << newa[i] << " ";
		ans += (int)pow(newa[i], i + 1);
	}
	//cout << "\n";
	swap(a, newa);
	return ans;
}
int sri() {
	int ans = 0;
	int n = sz(a);
	newa.resize(0);
	newa.resize(n);
	for (int i = 0; i < n; ++i) {
		newa[a[i]-1] = i+1;
	}
	for (int i = 0; i < n; ++i) {
		//cout << newa[i] << " ";
		ans += (int)pow(newa[i], i + 1);
	}
	//cout << "\n";
	swap(a, newa);
	return ans;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	a.resize(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (int i = 0; i < q; ++i) {
		int qi;
		cin >> qi;
		if (qi == 1) {
			cout << one() << " ";
		} else if (qi == 2) {
			cout << two() << " ";
		} else if (qi == 3) {
			cout << sri() << " ";
		}
		/*cout << "Current a:  ";
		for (int i = 0; i < n; ++i) {
			cout << a[i] << " ";
		}
		cout << "\n";*/
	}
}