#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <fstream>
#define rep( i, l, r ) for (int i = l; i <= r; i++)
#define down( i, l, r ) for (int i = l; i >= r; i--)
const int DS = 5000000;
using namespace std;
int h[DS], l[DS], r[DS], n[DS], s[DS];
char key[DS];
bool rev[DS], same[DS];
int q, m, w, last;
char que[50];
int NewTree()
{
int a = last;
last = n[a];
h[a] = l[a] = r[a] = n[a] = s[a] = 0;
rev[a] = same[a] = false;
key[a] = '$';
return a;
}
void Calculate(int w)
{
s[w] = s[l[w]] + 1 + s[r[w]];
}
void InsertR(int w)
{
int zuo = s[w] / 2;
int you = s[w] - zuo - 1;
if (zuo > 0)
{
int a = l[w] = NewTree(); h[a] = w; s[a] = zuo;
InsertR(a);
}
key[w] = getchar();
while (key[w] < 32 || key[w] > 126) scanf("%c", &key[w]);
if (you > 0)
{
int a = r[w] = NewTree(); h[a] = w; s[a] = you;
InsertR(a);
}
Calculate(w);
}
void Insert(int m)
{
int a = l[r[l[0]]] = NewTree();
h[a] = r[l[0]];
s[a] = m;
InsertR(a);
Calculate(r[l[0]]);
Calculate(l[0]);
}
void DeleteR(int w)
{
if (l[w] != 0) DeleteR(l[w]);
if (r[w] != 0) DeleteR(r[w]);
n[w] = last;
last = w;
}
void Delete()
{
int a = l[r[l[0]]];
l[r[l[0]]] = 0;
DeleteR(a);
Calculate(r[l[0]]);
Calculate(l[0]);
}
int Find(int m)
{
int w = l[0];
while (m != s[l[w]]+1)
{
if (m < s[l[w]]+1) w = l[w];
else
{
m -= s[l[w]]+1;
w = r[w];
}
}
return w;
}
void RotateL(int w)
{
int o = h[w];
r[o] = l[w]; h[r[o]] = o;
l[w] = o; h[w] = h[o];
h[o] = w;
if (l[h[w]] == o) l[h[w]] = w; else r[h[w]] = w;
Calculate(o);
}
void RotateR(int w)
{
int o = h[w];
l[o] = r[w]; h[l[o]] = o;
r[w] = o; h[w] = h[o];
h[o] = w;
if (l[h[w]] == o) l[h[w]] = w; else r[h[w]] = w;
Calculate(o);
}
void Splay(int w)
{
while (h[w] != 0)
{
if (l[h[w]] == w) RotateR(w); else RotateL(w);
}
Calculate(w);
}
void FindAll(int b, int e)
{
Splay(Find(e));
Splay(Find(b));
}
void Mol(int w)
{
if (l[w] != 0) Mol(l[w]);
printf("%c", key[w]);
if (r[w] != 0) Mol(r[w]);
}
int main()
{
rep(i, 0, DS-1) n[i] = i+1; last = 0;
rep(i, 1, 3) q = NewTree();
l[0] = 1; h[1] = 0;
r[1] = 2; h[2] = 1;
s[1] = 2; s[2] = 1;
scanf("%d", &q);
w = 1;
while (q > 0)
{
q --;
scanf("%s", que);
if (que[0] == 'I')
{
scanf("%d", &m);
FindAll(w, w+1);
Insert(m);
}
else if (que[0] == 'M')
{
scanf("%d", &w); w ++;
}
else if (que[0] == 'D')
{
scanf("%d", &m);
FindAll(w, w+m+1);
Delete();
}
else if (que[0] == 'G')
{
scanf("%d", &m);
FindAll(w, w+m+1);
Mol(l[r[l[0]]]);
printf("\n");
}
else if (que[0] == 'P') w --;
else if (que[0] == 'N') w ++;
}
return 0;
}
I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGZzdHJlYW0+CgojZGVmaW5lIHJlcCggaSwgbCwgciApIGZvciAoaW50IGkgPSBsOyBpIDw9IHI7IGkrKykKI2RlZmluZSBkb3duKCBpLCBsLCByICkgZm9yIChpbnQgaSA9IGw7IGkgPj0gcjsgaS0tKQoKY29uc3QgaW50IERTID0gNTAwMDAwMDsKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBoW0RTXSwgbFtEU10sIHJbRFNdLCBuW0RTXSwgc1tEU107CmNoYXIga2V5W0RTXTsKYm9vbCByZXZbRFNdLCBzYW1lW0RTXTsKaW50IHEsIG0sIHcsIGxhc3Q7CmNoYXIgcXVlWzUwXTsKCmludCBOZXdUcmVlKCkKewoJaW50IGEgPSBsYXN0OwoJbGFzdCA9IG5bYV07CgloW2FdID0gbFthXSA9IHJbYV0gPSBuW2FdID0gc1thXSA9IDA7CglyZXZbYV0gPSBzYW1lW2FdID0gZmFsc2U7CglrZXlbYV0gPSAnJCc7CglyZXR1cm4gYTsKfQoKdm9pZCBDYWxjdWxhdGUoaW50IHcpCnsKCXNbd10gPSBzW2xbd11dICsgMSArIHNbclt3XV07Cn0KCnZvaWQgSW5zZXJ0UihpbnQgdykKewoJaW50IHp1byA9IHNbd10gLyAyOwoJaW50IHlvdSA9IHNbd10gLSB6dW8gLSAxOwoJaWYgKHp1byA+IDApCgl7CgkJaW50IGEgPSBsW3ddID0gTmV3VHJlZSgpOyBoW2FdID0gdzsgc1thXSA9IHp1bzsKCQlJbnNlcnRSKGEpOwoJfQoJa2V5W3ddID0gZ2V0Y2hhcigpOwoJd2hpbGUgKGtleVt3XSA8IDMyIHx8IGtleVt3XSA+IDEyNikgc2NhbmYoIiVjIiwgJmtleVt3XSk7CglpZiAoeW91ID4gMCkKCXsKCQlpbnQgYSA9IHJbd10gPSBOZXdUcmVlKCk7IGhbYV0gPSB3OyBzW2FdID0geW91OwoJCUluc2VydFIoYSk7Cgl9CglDYWxjdWxhdGUodyk7Cn0KCnZvaWQgSW5zZXJ0KGludCBtKQp7CglpbnQgYSA9IGxbcltsWzBdXV0gPSBOZXdUcmVlKCk7CgloW2FdID0gcltsWzBdXTsKCXNbYV0gPSBtOwoJSW5zZXJ0UihhKTsKCUNhbGN1bGF0ZShyW2xbMF1dKTsKCUNhbGN1bGF0ZShsWzBdKTsKfQoKdm9pZCBEZWxldGVSKGludCB3KQp7CglpZiAobFt3XSAhPSAwKSBEZWxldGVSKGxbd10pOwoJaWYgKHJbd10gIT0gMCkgRGVsZXRlUihyW3ddKTsKCW5bd10gPSBsYXN0OwoJbGFzdCA9IHc7Cn0KCnZvaWQgRGVsZXRlKCkKewoJaW50IGEgPSBsW3JbbFswXV1dOwoJbFtyW2xbMF1dXSA9IDA7CglEZWxldGVSKGEpOwoJQ2FsY3VsYXRlKHJbbFswXV0pOwoJQ2FsY3VsYXRlKGxbMF0pOwp9CgppbnQgRmluZChpbnQgbSkKewoJaW50IHcgPSBsWzBdOwoJd2hpbGUgKG0gIT0gc1tsW3ddXSsxKQoJewoJCWlmIChtIDwgc1tsW3ddXSsxKSB3ID0gbFt3XTsKCQllbHNlCgkJewoJCQltIC09IHNbbFt3XV0rMTsKCQkJdyA9IHJbd107CgkJfQoJfQoJcmV0dXJuIHc7Cn0KCnZvaWQgUm90YXRlTChpbnQgdykKewoJaW50IG8gPSBoW3ddOwoJcltvXSA9IGxbd107IGhbcltvXV0gPSBvOwoJbFt3XSA9IG87IGhbd10gPSBoW29dOyAKCWhbb10gPSB3OyAKCWlmIChsW2hbd11dID09IG8pIGxbaFt3XV0gPSB3OyBlbHNlIHJbaFt3XV0gPSB3OwoJQ2FsY3VsYXRlKG8pOwp9Cgp2b2lkIFJvdGF0ZVIoaW50IHcpCnsKCWludCBvID0gaFt3XTsKCWxbb10gPSByW3ddOyBoW2xbb11dID0gbzsKCXJbd10gPSBvOyBoW3ddID0gaFtvXTsgCgloW29dID0gdzsgCglpZiAobFtoW3ddXSA9PSBvKSBsW2hbd11dID0gdzsgZWxzZSByW2hbd11dID0gdzsKCUNhbGN1bGF0ZShvKTsKfQoKdm9pZCBTcGxheShpbnQgdykKewoJd2hpbGUgKGhbd10gIT0gMCkKCXsKCQlpZiAobFtoW3ddXSA9PSB3KSBSb3RhdGVSKHcpOyBlbHNlIFJvdGF0ZUwodyk7Cgl9CglDYWxjdWxhdGUodyk7Cn0KCnZvaWQgRmluZEFsbChpbnQgYiwgaW50IGUpCnsKCVNwbGF5KEZpbmQoZSkpOwoJU3BsYXkoRmluZChiKSk7Cn0KCnZvaWQgTW9sKGludCB3KQp7CglpZiAobFt3XSAhPSAwKSBNb2wobFt3XSk7CglwcmludGYoIiVjIiwga2V5W3ddKTsKCWlmIChyW3ddICE9IDApIE1vbChyW3ddKTsKfQoKaW50IG1haW4oKQp7CglyZXAoaSwgMCwgRFMtMSkgbltpXSA9IGkrMTsgbGFzdCA9IDA7CglyZXAoaSwgMSwgMykgcSA9IE5ld1RyZWUoKTsKCWxbMF0gPSAxOyBoWzFdID0gMDsKCXJbMV0gPSAyOyBoWzJdID0gMTsKCXNbMV0gPSAyOyBzWzJdID0gMTsKCXNjYW5mKCIlZCIsICZxKTsKCXcgPSAxOwoJd2hpbGUgKHEgPiAwKQoJewoJCXEgLS07CgkJc2NhbmYoIiVzIiwgcXVlKTsKCQlpZiAocXVlWzBdID09ICdJJykKCQl7CgkJCXNjYW5mKCIlZCIsICZtKTsKCQkJRmluZEFsbCh3LCB3KzEpOwoJCQlJbnNlcnQobSk7CgkJfQoJCWVsc2UgaWYgKHF1ZVswXSA9PSAnTScpIAoJCXsKCQkJc2NhbmYoIiVkIiwgJncpOyB3ICsrOwoJCX0KCQllbHNlIGlmIChxdWVbMF0gPT0gJ0QnKQoJCXsKCQkJc2NhbmYoIiVkIiwgJm0pOwoJCQlGaW5kQWxsKHcsIHcrbSsxKTsKCQkJRGVsZXRlKCk7CgkJfQoJCWVsc2UgaWYgKHF1ZVswXSA9PSAnRycpIAoJCXsKCQkJc2NhbmYoIiVkIiwgJm0pOwoJCQlGaW5kQWxsKHcsIHcrbSsxKTsKCQkJTW9sKGxbcltsWzBdXV0pOwoJCQlwcmludGYoIlxuIik7CgkJfQoJCWVsc2UgaWYgKHF1ZVswXSA9PSAnUCcpIHcgLS07CgkJZWxzZSBpZiAocXVlWzBdID09ICdOJykgdyArKzsKCX0KCXJldHVybiAwOwp9Cg==