$Splay$
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;
const int N = 80010, INF = 2e9;
struct node {
int s[2], p;
int val;
int size;
void init(int _val, int _p) { s[0] = s[1] = 0, p = _p, val = _val, size = 1; }
} tr[N];
int root, idx;
// dic[i]表示值为i的结点对应的结点编号
int dic[N];
int n, m;
int a[N];
void pushup(int u)
{
tr[u].size = tr[tr[u].s[0]].size + tr[tr[u].s[1]].size + 1;
}
void rotate(int x)
{
int y = tr[x].p, z = tr[y].p;
int k = tr[y].s[1] == x;
tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y, tr[y].p = x;
pushup(y), pushup(x);
}
void splay(int x, int k)
{
while(tr[x].p != k)
{
int y = tr[x].p, z = tr[y].p;
if(z != k)
if((tr[z].s[1] == y) == (tr[y].s[1] == x)) rotate(y);
else rotate(x);
rotate(x);
}
if(!k) root = x;
}
int build(int l, int r, int p)
{
int u = ++ idx;
int mid = l + r >> 1;
tr[u].init(a[mid], p);
dic[a[mid]] = u;
if(l < mid) tr[u].s[0] = build(l, mid - 1, u);
if(r > mid) tr[u].s[1] = build(mid + 1, r, u);
pushup(u);
return u;
}
int get_k(int k)
{
int u = root;
while(u)
{
if(tr[tr[u].s[0]].size >= k) u = tr[u].s[0];
else if(tr[tr[u].s[0]].size + 1 == k) return u;
else k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
}
return -1;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
root = build(1, n, 0);
while(m --)
{
char op[10];
scanf("%s", op);
if(strcmp(op, "Top") == 0)
{
// 将编号为s的书对应的结点旋转到根,将左子树接到根节点的后继上,注意从根结点的后继 到 根结点上链路的pushup
int s;
scanf("%d", &s);
int u = dic[s];
splay(u, 0);
int l = tr[u].s[0], r = tr[u].s[1];
if(l == 0) continue;
if(r == 0)
{
tr[u].s[1] = l, tr[u].s[0] = 0;
}
else
{
while(tr[r].s[0]) r = tr[r].s[0];
tr[r].s[0] = l, tr[l].p = r;
tr[u].s[0] = 0;
// int p = l;
// while(p) pushup(p), p = tr[p].p;
splay(l, 0); // splay替代链上的pushup
}
}
else if(strcmp(op, "Bottom") == 0)
{
// 与 Top 操作同理
int s;
scanf("%d", &s);
int u = dic[s];
splay(u, 0);
int l = tr[u].s[0], r = tr[u].s[1];
if(r == 0) continue;
if(l == 0)
{
tr[u].s[0] = r, tr[u].s[1] = 0;
}
else
{
while(tr[l].s[1]) l = tr[l].s[1];
tr[l].s[1] = r, tr[r].p = l;
tr[u].s[1] = 0;
// int p = r;
// while(p) pushup(p), p = tr[p].p;
splay(r, 0); // splay替代链上的pushup
}
}
else if(strcmp(op, "Insert") == 0)
{
// 交换相邻结点的书编号,以及对应结点的编号
int s;
char t[10];
scanf("%d%s", &s, t);
if(t[0] == '0') continue;
else if(t[0] == '1')
{
int u = dic[s];
splay(u, 0);
int r = tr[u].s[1];
if(r == 0) continue;
while(tr[r].s[0]) r = tr[r].s[0];
swap(tr[r].val, tr[u].val);
swap(dic[tr[r].val], dic[tr[u].val]);
splay(r, 0);
}
else
{
int u = dic[s];
splay(u, 0);
int l = tr[u].s[0];
if(l == 0) continue;
while(tr[l].s[1]) l = tr[l].s[1];
swap(tr[l].val, tr[u].val);
swap(dic[tr[l].val], dic[tr[u].val]);
splay(l, 0);
}
}
else if(strcmp(op, "Ask") == 0)
{
// 将编号对应位置旋转到根,输出左子树大小
int s;
scanf("%d", &s);
int u = dic[s];
splay(u, 0);
printf("%d\n", tr[tr[u].s[0]].size);
}
else if(strcmp(op, "Query") == 0)
{
// 输出第k大位置的编号
int s;
scanf("%d", &s);
int u = get_k(s);
printf("%d\n", tr[u].val);
splay(u, 0);
}
}
return 0;
}