#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>
using namespace std;
struct Dumb {
vector<int> elements;
void ins(int k, int e) {
k--;
assert(0 <= k && k <= (int)elements.size());
vector<int> newElements;
for (int i = 0; i < k; i++) newElements.push_back(elements[i]);
newElements.push_back(e);
for (int i = k; i < (int)elements.size(); i++) newElements.push_back(elements[i]);
elements = newElements;
}
int get(int k) {
k--;
assert(0 <= k && k < (int)elements.size());
return elements[k];
}
void rev(int l, int r) {
l--;
r--;
assert(0 <= l && l <= r && r < (int)elements.size());
reverse(elements.begin() + l, elements.begin() + r + 1);
}
void del(int l, int r) {
l--;
r--;
assert(0 <= l && l <= r && r < (int)elements.size());
vector<int> newElements;
for (int i = 0; i < l; i++) newElements.push_back(elements[i]);
for (int i = r + 1; i < (int)elements.size(); i++) newElements.push_back(elements[i]);
elements = newElements;
}
};
struct MetaData {
int index;
int len;
};
struct Smart {
vector<bool> rev;
vector<vector<int>> Data;
vector<MetaData> metaData;
const int S = 3;
int sz = 0;
void checkMetaData() {
assert((int)rev.size() == (int)Data.size());
// only when debugging
int sum = 0;
for (auto& it : metaData) {
assert(0 <= it.index && it.index < (int)Data.size());
assert((int)Data[it.index].size() == it.len);
assert(it.len >= 1);
sum += it.len;
}
assert(sum == sz);
sum = 0;
for (int i = 0; i < (int)Data.size(); i++) {
sum += (int)Data[i].size();
}
assert(sum == sz);
}
void unpack(int index) {
assert(0 <= index && index < (int)Data.size());
assert((int)rev.size() == (int)Data.size());
if (rev[index]) {
rev[index] = 0;
reverse(Data[index].begin(), Data[index].end());
}
}
int placeData(vector<int>& v) {
assert(!v.empty());
for (int i = 0; i < (int)Data.size(); i++) {
if (Data[i].empty()) {
Data[i] = v;
rev[i] = 0;
return i;
}
}
Data.push_back(v);
rev.push_back(0);
return (int)Data.size() - 1;
}
void split(int k) {
vector<MetaData> newMetaData;
// splits between k and k + 1
if (k + 1 == sz) return;
assert(0 <= k && k + 1 < sz);
int sum = 0;
for (int i = 0; i < (int)metaData.size(); i++) {
if (sum + metaData[i].len - 1 == k) return;
if (k <= sum + metaData[i].len - 2) {
assert(sum <= k && k <= sum + metaData[i].len - 2);
unpack(metaData[i].index);
vector<int> bck;
for (int p = k + 1; p <= sum + metaData[i].len - 1; p++) {
bck.push_back(Data[metaData[i].index][p - sum]);
}
for (int p = k + 1; p <= sum + metaData[i].len - 1; p++) {
Data[metaData[i].index].pop_back();
}
assert(!Data[metaData[i].index].empty());
assert(!bck.empty());
//cout << "heyooo\n";
int pos = placeData(bck);
//cout << "my man\n";
assert((int)bck.size() == (int)Data[pos].size());
newMetaData.push_back({ metaData[i].index, (int)Data[metaData[i].index].size() });
newMetaData.push_back({ pos, (int)bck.size() });
for (int j = i + 1; j < (int)metaData.size(); j++) {
newMetaData.push_back(metaData[j]);
}
metaData = newMetaData;
if (0) {
cout << "kek lmao : \n";
for (int i = 0; i < (int)Data.size(); i++) {
cout << "dim = " << (int)Data[i].size() << "\n";
}
}
// exit(0);
return;
}
sum += metaData[i].len;
newMetaData.push_back(metaData[i]);
}
assert(0);
}
void balance() {
vector<MetaData> newMetaData;
for (int i = 0; i + 1 < (int)metaData.size(); i++) {
int p1 = metaData[i].index;
int p2 = metaData[i + 1].index;
if ((int)Data[p1].size() + (int)Data[p2].size() < 2 * S) {
assert(p1 != p2);
newMetaData.clear();
for (int j = 0; j < i; j++) newMetaData.push_back(metaData[j]);
unpack(p1);
unpack(p2);
assert(!Data[p1].empty());
for (auto& x : Data[p2]) {
Data[p1].push_back(x);
}
newMetaData.push_back({ p1, (int)Data[p1].size() });
Data[p2].clear();
for (int j = i + 2; j < (int)metaData.size(); j++) newMetaData.push_back(metaData[j]);
metaData = newMetaData;
//cout << "\t\t\t\t\t\t\t\t::::::::::::::::::: " << (int)metaData.size() << " " << metaData[0].len << "\n";
balance();
return;
}
}
for (int i = 0; i < (int)metaData.size(); i++) {
int p = metaData[i].index;
if ((int)Data[p].size() >= 2 * S) {
assert(0);
int dim1 = S;
int dim2 = (int)Data[p].size() - dim1;
assert(S <= dim1 && dim1 < 2 * S);
assert(S <= dim2 && dim2 < 2 * S);
unpack(p);
newMetaData.clear();
for (int j = 0; j < i; j++) newMetaData.push_back(metaData[j]);
vector<int> nw;
for (int i = dim1; i < (int)Data[p].size(); i++) {
nw.push_back(Data[p][i]);
}
for (int i = dim1; i < (int)Data[p].size(); i++) {
Data[p].pop_back();
}
assert((int)Data[p].size() == dim1);
assert((int)nw.size() == dim2);
newMetaData.push_back({ p, (int)Data[p].size() });
int new_pos = placeData(nw);
newMetaData.push_back({ new_pos, (int)Data[new_pos].size() });
for (int j = i + 1; j < (int)metaData.size(); j++) newMetaData.push_back(metaData[j]);
metaData = newMetaData;
balance();
return;
}
}
}
void ins(int k, int e) {
vector<MetaData> newMetaData;
k--;
//cout << "k = " << k << "\n";
assert(0 <= k && k <= sz);
if (k == 0) {
newMetaData.clear();
vector<int> v = { e };
int p = placeData(v);
newMetaData.push_back({ p, 1 });
for (int j = 0; j < (int)metaData.size(); j++) newMetaData.push_back(metaData[j]);
metaData = newMetaData;
}
else {
newMetaData.clear();
split(k - 1);
vector<int> v = { e };
int Until = -1;
{
int sum = 0;
for (int i = 0; i < (int)metaData.size(); i++) {
sum += (int)Data[metaData[i].index].size();
if (sum == k) {
Until = i;
break;
}
}
assert(Until != -1);
}
int p = placeData(v);
for (int j = 0; j <= Until; j++) newMetaData.push_back(metaData[j]);
newMetaData.push_back({ p, 1 });
for (int j = Until + 1; j < (int)metaData.size(); j++) newMetaData.push_back(metaData[j]);
metaData = newMetaData;
//{
// cout << " : \n";
// for (int j = 0; j < (int)Data.size(); j++) {
// cout << "dim = " << (int)Data[j].size() << "\n";
// }
// cout << " : ";
// for (int i = 0; i < (int)metaData.size(); i++) {
// cout << metaData[i].len << " ";
// }
// cout << "\n";
//}
}
sz++;
//cout << "init check\n";
checkMetaData();
balance();
//cout << "done first\n";
/*if (k == 1) {
cout << " : \n";
for (int j = 0; j < (int)Data.size(); j++) {
cout << "dim = " << (int)Data[j].size() << "\n";
}
cout << " : ";
cout << "the size is " << (int)metaData.size() << " " << metaData[0].len << "\n";
checkMetaData();
exit(0);
exit(0);
for (int i = 0; i < (int)metaData.size(); i++) {
cout << metaData[i].len << " ";
}
cout << "\n";
exit(0);
}*/
//cout << "start second\n";
checkMetaData();
//cout << "done second\n";
}
int get(int p) {
p--;
assert(0 <= p && p < sz);
int sum = 0;
for (int i = 0; i < (int)metaData.size(); i++) {
if (p <= sum + metaData[i].len - 1) {
assert(sum <= p && p <= sum + metaData[i].len - 1);
unpack(metaData[i].index);
return Data[metaData[i].index][p - sum];
}
sum += metaData[i].len;
}
assert(0);
}
void print() {
checkMetaData();
//cout << " ---> ";
for (int i = 0; i < (int)metaData.size(); i++) {
int p = metaData[i].index;
if (!rev[p]) {
for (int j = 0; j < (int)metaData[i].len; j++) {
cout << Data[p][j] << " ";
}
}
else {
for (int j = (int)metaData[i].len - 1; j >= 0; j--) {
cout << Data[p][j] << " ";
}
}
// cout << " | ";
}
cout << "\n";
}
void del(int l, int r) {
checkMetaData();
l--;
r--;
assert(0 <= l && l <= r && r < sz);
if (l >= 1) {
split(l - 1);
}
split(r);
// find where r is
int pr = -1;
{
int sum = 0;
for (int i = 0; i < (int)metaData.size(); i++) {
if (r == sum + metaData[i].len - 1) {
pr = i;
break;
}
sum += metaData[i].len;
}
assert(pr != -1);
}
int pl = -1;
if (l > 0) {
int sum = 0;
for (int i = 0; i < (int)metaData.size(); i++) {
if (l - 1 == sum + metaData[i].len - 1) {
pl = i;
break;
}
sum += metaData[i].len;
}
assert(pl != -1);
}
assert((l == 0) == (pl == -1));
pl++;
assert(pl <= pr);
sz -= (r - l + 1);
vector<MetaData> newMetaData;
for (int j = 0; j < pl; j++) newMetaData.push_back(metaData[j]);
for (int j = pl; j <= pr; j++) {
int p = metaData[j].index;
Data[p].clear();
}
for (int j = pr + 1; j < (int)metaData.size(); j++) newMetaData.push_back(metaData[j]);
metaData = newMetaData;
checkMetaData();
balance();
return;
}
void rv(int l, int r) {
checkMetaData();
l--;
r--;
assert(0 <= l && l <= r && r < sz);
if (l >= 1) {
split(l - 1);
}
split(r);
// find where r is
int pr = -1;
{
int sum = 0;
for (int i = 0; i < (int)metaData.size(); i++) {
if (r == sum + metaData[i].len - 1) {
pr = i;
break;
}
sum += metaData[i].len;
}
assert(pr != -1);
}
int pl = -1;
if (l > 0) {
int sum = 0;
for (int i = 0; i < (int)metaData.size(); i++) {
if (l - 1 == sum + metaData[i].len - 1) {
pl = i;
break;
}
sum += metaData[i].len;
}
assert(pl != -1);
}
assert((l == 0) == (pl == -1));
pl++;
assert(pl <= pr);
vector<MetaData> newMetaData;
for (int j = 0; j < pl; j++) newMetaData.push_back(metaData[j]);
for (int j = pr; j >= pl; j--) {
newMetaData.push_back(metaData[j]);
rev[metaData[j].index] = !rev[metaData[j].index];
}
for (int j = pr + 1; j < (int)metaData.size(); j++) newMetaData.push_back(metaData[j]);
metaData = newMetaData;
checkMetaData();
balance();
return;
}
};
mt19937 rng(228);
int getrng(int l, int r) {
assert(l <= r);
int sol = rng() % (r - l + 1) + l;
assert(l <= sol && sol <= r);
return sol;
}
signed main() {
#ifdef INFOARENA
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("secv8.in", "r", stdin);
freopen("secv8.out", "w", stdout);
#else
FILE* stream;
freopen_s(&stream, "input.txt", "r", stdin);
#endif
//if (1) {
// Smart sm;
// sm.ins(1, 77);
// sm.ins(2, 100);
// sm.ins(3, 200);
// sm.print();
// sm.del(2, 2);
// sm.print();
// exit(0);
//}
if (0) {
Dumb d;
Smart sm;
sm.ins(1, 77); sm.print();
sm.ins(1, 3); sm.print();
sm.ins(2, 66); sm.print();
sm.ins(1, 77777); sm.print();
sm.ins(3, 5555); sm.print();
sm.ins(2, 4); sm.print();
exit(0);
}
if (0) {
for (long long _ = 1; 1; _++) {
Dumb d;
Smart sm;
int n = 0;
for (int i = 1; n <= 20 && i <= 100; i++) {
int tp = rng() % 3;
if (tp == 0 && n >= 1) {
int l = getrng(1, n);
int r = getrng(l, n);
d.del(l, r);
sm.del(l, r);
n -= (r - l + 1);
}
if (tp == 2 && n >= 1) {
int l = getrng(1, n);
int r = getrng(l, n);
d.rev(l, r);
sm.rv(l, r);
n -= (r - l + 1);
}
if (tp == 1) {
int p = getrng(1, n + 1);
int x = getrng(1, 100);
d.ins(p, x);
sm.ins(p, x);
n++;
}
for (int j = 1; j <= n; j++) {
assert(d.get(j) == sm.get(j));
}
}
if (_ % ((int)1e3) == 0) {
cout << "done " << _ << "\n";
}
}
exit(0);
}
Smart sm;
int q, _;
cin >> q >> _;
for (int iq = 1; iq <= q; iq++) {
string s;
cin >> s;
if (s == "I") {
int k, e;
cin >> k >> e;
sm.ins(k, e);
continue;
}
if (s == "A") {
int k;
cin >> k;
cout << sm.get(k) << "\n";
continue;
}
if (s == "R") {
int l, r;
cin >> l >> r;
sm.rv(l, r);
continue;
}
if (s == "D") {
int l, r;
cin >> l >> r;
sm.del(l, r);
continue;
}
assert(0);
}
sm.print();
return 0;
}