#include <bits/stdc++.h>
using namespace std;

const int N = 8e4 + 5;
int n, m, ab[3 * N], ba[3 * N], c[3 * N], mn;
inline int lbt(int x) {
	return x & (-x);
}
inline void update(int i, int k) {
	for (; i <= mn; i += lbt(i)) c[i] += k;
}
inline int getsum(int i) {
	int ans = 0;
	for (; i > 0; i -= lbt(i)) ans += c[i];
	return ans;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	int l = n + 1, r = 2 * n;
	mn = 3 * n + 5;
	for (int i = 1; i <= n; ++i) {
		cin >> ab[i + l - 1];
		ba[ab[i + l - 1]] = i + l - 1;
		update(i + l - 1, 1);
	}
	while (m--) {
		string op;
		int x, y;
		cin >> op >> x;
		if (op == "Top") {
			ab[--l] = x;
			ab[ba[x]] = 0;
			update(ba[x], -1);
			ba[x] = l;
			update(l, 1);
		} else if (op == "Bottom") {
			ab[++r] = x;
			ab[ba[x]] = 0;
			update(ba[x], -1);
			ba[x] = r;
			update(r, 1);
		} else if (op == "Insert") {
			cin >> y;
			int tmp = y, nx = ba[x] + y;
			while (ab[ba[x] + y] == 0) {
				y += tmp;
				nx = ba[x] + y;
			}
			int tmp2 = ab[nx];
			swap(ab[nx], ab[ba[x]]);
			swap(ba[tmp2], ba[x]);
			
		} else if (op == "Ask") {
			cout << getsum(ba[x] - 1) << endl;
		} else {
			int left = l, right = r;
			while (left < right) {
				int mid = (left + right) >> 1;
				if (getsum(mid) >= x) {
					right = mid;
				} else {
					left = mid + 1;
				}
			}
			cout << ab[left] << endl;
		}
	}
	return 0;
}