#include <bits/stdc++.h>
#include<map>
using namespace std;
// int temp[1000000];f
map<int, int> nemE ;
bool updateBIT(int BITree[], int n, int index, int val)
{
bool upd = false;
index = index + 1;
while (index <= n)
{
upd = true;
BITree[index] += val;
index += index & (-index);
}
return upd;
}
int *constructBITree(int arr[], int n)
{
int *BITree = new int[n+1];
for (int i=1; i<=n; i++)
BITree[i] = 0;
for (int i=0; i<n; i++)
updateBIT(BITree, n, i, arr[i]);
return BITree;
}
int getSum(int BITree[], int index)
{
int sum = 0;
index = index + 1;
while (index>0)
{
sum += BITree[index];
index -= index & (-index);
}
return sum;
}
bool update(int BITree[], int l, int r, int n, int val)
{
return updateBIT(BITree, n, l, val);
// updateBIT(BITree, n, r+1, -val);
}
void printtree(int BITree[], int n){
for(int i=0;i<=n;i++)
cout<<BITree[i]<<" ";
cout<<"\n";
}
int main()
{
int t = 1;
while(t-->0){
nemE.clear();
map<int,int>::key_compare mycomp = nemE.key_comp();
// memset(temp, -1, sizeof temp);
int n,u;
cin>>n>>u;
int arr[n], val[n];
for(int i=0;i<n;i++){
cin>>val[i];
arr[i] =0;
}
// int *BITree = constructBITree(val, n);
int BITree[n+1];
memset(BITree, 0, sizeof BITree);
int strt = 0, end = n-1;
for(int i=0;i<u;i++){
// printtree(BITree, n);
int cs ;
cin>>cs;
if(cs==1){
int k,x;
cin>>k>>x;
if(!(end<(k-1))){
if(strt==k-1)
strt++;
update(BITree, k-1, n, n, 1);
end++;
}
bool upd = true;
for (map<int,int>::iterator it=nemE.upper_bound(k-1);
it!=nemE.end(); ++it){
upd = false;
cout<<"updated"<<endl;
int ta = it->first, tb = it->second;
nemE.erase(it);
nemE.insert(make_pair(ta+1, it->second));
}
if(upd)
nemE.insert(make_pair(k-1, x));
// cout<<"map = ";
// for(map<int,int>::iterator it=nemE.begin();it!=nemE.end(); ++it)
// cout<<it->first<<"-->"<<it->second<<" ";
// cout<<endl;
}
else
if(cs==2){
int k;
cin>>k;
if((k-1)<=end)
end--;
if(strt<=k-1){
update(BITree, k-1, n, n, -1);
}
else{
update(BITree, 0, n, n, -1);
strt--;
}
for (map<int,int>::iterator it=nemE.upper_bound(k-1);
it!=nemE.end(); it++){
// cout<<it->first<<" "<<it->second<<endl;
int ta = it->first, tb = it->second;
nemE.erase(it);
nemE.insert(make_pair(ta-1, tb));
}
std::map<int,int>::iterator it;
it = nemE.find(k-1);
if (it != nemE.end())
nemE.erase (it);
}
else
if(cs==3){
int k;
cin>>k;
if(nemE.count(k-1)==1){
cout<<nemE.at(k-1)<<"\n";
}
else{
int po = getSum(BITree, k+1);
// cout<<k<<" "<<po<<endl;
cout<<val[k-po-1]<<"\n";
}
}
// printtree(BITree, n);
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlPG1hcD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIGludCB0ZW1wWzEwMDAwMDBdO2YKbWFwPGludCwgaW50PiBuZW1FIDsKCmJvb2wgdXBkYXRlQklUKGludCBCSVRyZWVbXSwgaW50IG4sIGludCBpbmRleCwgaW50IHZhbCkKewoJYm9vbCB1cGQgPSBmYWxzZTsKICAgIGluZGV4ID0gaW5kZXggKyAxOwogICAgd2hpbGUgKGluZGV4IDw9IG4pCiAgICB7CiAgICAJdXBkID0gdHJ1ZTsKICAgICAgICBCSVRyZWVbaW5kZXhdICs9IHZhbDsKICAgICAgICBpbmRleCArPSBpbmRleCAmICgtaW5kZXgpOwogICAgfQogICAgcmV0dXJuIHVwZDsKfQogCmludCAqY29uc3RydWN0QklUcmVlKGludCBhcnJbXSwgaW50IG4pCnsKICAgIGludCAqQklUcmVlID0gbmV3IGludFtuKzFdOwogICAgZm9yIChpbnQgaT0xOyBpPD1uOyBpKyspCiAgICAgICAgQklUcmVlW2ldID0gMDsKIAogICAgZm9yIChpbnQgaT0wOyBpPG47IGkrKykKICAgICAgICB1cGRhdGVCSVQoQklUcmVlLCBuLCBpLCBhcnJbaV0pOwogCiAgICByZXR1cm4gQklUcmVlOwp9CiAKaW50IGdldFN1bShpbnQgQklUcmVlW10sIGludCBpbmRleCkKewogICAgaW50IHN1bSA9IDA7IAogICAgaW5kZXggPSBpbmRleCArIDE7CiAgICB3aGlsZSAoaW5kZXg+MCkKICAgIHsKICAgICAgICBzdW0gKz0gQklUcmVlW2luZGV4XTsKICAgICAgICBpbmRleCAtPSBpbmRleCAmICgtaW5kZXgpOwogICAgfQogICAgcmV0dXJuIHN1bTsKfQogCmJvb2wgdXBkYXRlKGludCBCSVRyZWVbXSwgaW50IGwsIGludCByLCBpbnQgbiwgaW50IHZhbCkKewogICAgcmV0dXJuIHVwZGF0ZUJJVChCSVRyZWUsIG4sIGwsIHZhbCk7CiAgICAvLyB1cGRhdGVCSVQoQklUcmVlLCBuLCByKzEsIC12YWwpOwp9Cgp2b2lkIHByaW50dHJlZShpbnQgQklUcmVlW10sIGludCBuKXsKCWZvcihpbnQgaT0wO2k8PW47aSsrKQoJCWNvdXQ8PEJJVHJlZVtpXTw8IiAiOwoJY291dDw8IlxuIjsKfQogCmludCBtYWluKCkKewoJaW50IHQgPSAxOwoJd2hpbGUodC0tPjApewoJCW5lbUUuY2xlYXIoKTsKCQltYXA8aW50LGludD46OmtleV9jb21wYXJlIG15Y29tcCA9IG5lbUUua2V5X2NvbXAoKTsKCQkKCQkKCQkvLyBtZW1zZXQodGVtcCwgLTEsIHNpemVvZiB0ZW1wKTsKCQkKCQlpbnQgbix1OwoJCWNpbj4+bj4+dTsKCQlpbnQgYXJyW25dLCB2YWxbbl07CgkJZm9yKGludCBpPTA7aTxuO2krKyl7CgkJCWNpbj4+dmFsW2ldOwoJCQlhcnJbaV0gPTA7CgkJfQogICAgCS8vIGludCAqQklUcmVlID0gY29uc3RydWN0QklUcmVlKHZhbCwgbik7CiAgICAJaW50IEJJVHJlZVtuKzFdOwogICAgCW1lbXNldChCSVRyZWUsIDAsIHNpemVvZiBCSVRyZWUpOwogICAgCQogICAgCWludCBzdHJ0ID0gMCwgZW5kID0gbi0xOwogICAgCQogICAgCWZvcihpbnQgaT0wO2k8dTtpKyspewogICAgCQkvLyBwcmludHRyZWUoQklUcmVlLCBuKTsKICAgIAkJaW50IGNzIDsKICAgIAkJY2luPj5jczsKICAgIAkJaWYoY3M9PTEpewogICAgCQkJaW50IGsseDsKICAgIAkJCWNpbj4+az4+eDsKICAgIAkJCWlmKCEoZW5kPChrLTEpKSl7CiAgICAJCQkJaWYoc3RydD09ay0xKQogICAgCQkJCQlzdHJ0Kys7CiAgICAJCQkJdXBkYXRlKEJJVHJlZSwgay0xLCBuLCBuLCAxKTsKICAgIAkJCQllbmQrKzsKICAgIAkJCX0KICAgIAkJCWJvb2wgdXBkID0gdHJ1ZTsKICAgIAkJCWZvciAobWFwPGludCxpbnQ+OjppdGVyYXRvciBpdD1uZW1FLnVwcGVyX2JvdW5kKGstMSk7CiAgICAJCQkJCWl0IT1uZW1FLmVuZCgpOyArK2l0KXsKICAgIAkJCQl1cGQgPSBmYWxzZTsKICAgIAkJCQljb3V0PDwidXBkYXRlZCI8PGVuZGw7CiAgICAJCQkJaW50IHRhID0gaXQtPmZpcnN0LCB0YiA9IGl0LT5zZWNvbmQ7CiAgICAJCQkJbmVtRS5lcmFzZShpdCk7CiAgIAkJCQkJbmVtRS5pbnNlcnQobWFrZV9wYWlyKHRhKzEsIGl0LT5zZWNvbmQpKTsKICAgCQkJCX0KICAgCQkJCWlmKHVwZCkKICAgIAkJCQluZW1FLmluc2VydChtYWtlX3BhaXIoay0xLCB4KSk7CiAgICAJCQkJCiAgICAJCQkvLyBjb3V0PDwibWFwID0gIjsKICAgIAkJCS8vIGZvcihtYXA8aW50LGludD46Oml0ZXJhdG9yIGl0PW5lbUUuYmVnaW4oKTtpdCE9bmVtRS5lbmQoKTsgKytpdCkKICAgIAkJCS8vIAljb3V0PDxpdC0+Zmlyc3Q8PCItLT4iPDxpdC0+c2Vjb25kPDwiICI7CiAgICAJCQkvLyBjb3V0PDxlbmRsOwogICAgCQkJCiAgICAJCQkKICAgIAkJfQogICAgCQllbHNlCiAgICAJCWlmKGNzPT0yKXsKICAgIAkJCWludCBrOwogICAgCQkJY2luPj5rOwogICAgCQkJaWYoKGstMSk8PWVuZCkKICAgIAkJCQllbmQtLTsKICAgIAkJCWlmKHN0cnQ8PWstMSl7CiAgICAJCQkJdXBkYXRlKEJJVHJlZSwgay0xLCBuLCBuLCAtMSk7CiAgICAJCQl9CiAgICAJCQllbHNlewogICAgCQkJCXVwZGF0ZShCSVRyZWUsIDAsIG4sIG4sIC0xKTsJCiAgICAJCQkJc3RydC0tOwogICAgCQkJfQogICAgCQkJZm9yIChtYXA8aW50LGludD46Oml0ZXJhdG9yIGl0PW5lbUUudXBwZXJfYm91bmQoay0xKTsKICAgIAkJCQkJCWl0IT1uZW1FLmVuZCgpOyBpdCsrKXsKICAgIAkJCQkvLyBjb3V0PDxpdC0+Zmlyc3Q8PCIgIjw8aXQtPnNlY29uZDw8ZW5kbDsKICAgIAkJCQlpbnQgdGEgPSBpdC0+Zmlyc3QsIHRiID0gaXQtPnNlY29uZDsKICAgIAkJCQluZW1FLmVyYXNlKGl0KTsKCSAgICAJCQluZW1FLmluc2VydChtYWtlX3BhaXIodGEtMSwgdGIpKTsKICAgIAkJCX0KICAgIAkJCXN0ZDo6bWFwPGludCxpbnQ+OjppdGVyYXRvciBpdDsKCiAgCQkJCWl0ID0gbmVtRS5maW5kKGstMSk7CiAgCQkJCWlmIChpdCAhPSBuZW1FLmVuZCgpKQogICAgCQkJCW5lbUUuZXJhc2UgKGl0KTsKICAgIAkJCQogICAgCQkJCiAgICAJCX0KICAgIAkJZWxzZQogICAgCQlpZihjcz09Myl7CiAgICAJCQlpbnQgazsKICAgIAkJCWNpbj4+azsKICAgIAkJCWlmKG5lbUUuY291bnQoay0xKT09MSl7CiAgICAJCQkJY291dDw8bmVtRS5hdChrLTEpPDwiXG4iOwogICAgCQkJfQogICAgCQkJZWxzZXsKICAgIAkJCQlpbnQgcG8gPSBnZXRTdW0oQklUcmVlLCBrKzEpOwogICAgCQkJCS8vIGNvdXQ8PGs8PCIgIjw8cG88PGVuZGw7CiAgICAJCQkJY291dDw8dmFsW2stcG8tMV08PCJcbiI7CiAgICAJCQl9CiAgICAJCX0KICAgIAkJLy8gcHJpbnR0cmVlKEJJVHJlZSwgbik7CiAgICAJfQogICAgCQoJfQogICAgCiAgICByZXR1cm4gMDsKfQ==