#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; struct SplayNode{ SplayNode *l, *r, *p; int sz; char val; bool rev; SplayNode(char val):val(val), sz(1), rev(false), l(nullptr), r(nullptr){} void toggle(){ this->rev^=true; swap(this->l, this->r); } void push(){ if(this->rev){ if(this->l) this->l->toggle(); if(this->r) this->r->toggle(); this->rev=false; } } void update(){ this->sz=1; if(this->l) this->sz+=this->l->sz; if(this->r) this->sz+=this->r->sz; } void rotate(){ SplayNode *p=this->p, *pp=p->p, *ch; if(p->l==this) ch=this->r; else ch=this->l; if(pp){ if(pp->l==p) pp->l=this; else pp->r=this; } this->p=pp; if(p->l==this) this->r=p; else this->l=p; p->p=this; if(p->l==this) p->l=ch; else p->r=ch; if(ch) ch->p=p; p->update(); update(); } int state(){ if(!this->p) return 0; else if(this->p->l==this) return 1; else return -1; } void splay(){ push(); while(this->p){ if(!this->p->p){ this->p->push(); push(); rotate(); }else{ this->p->p->push(); this->p->push(); push(); if(this->p->state()==state()){ this->p->rotate(); rotate(); }else{ rotate(); rotate(); } } } } }; using node=SplayNode; node *get(node *root, int idx){ node *now=root; while(1){ now->push(); int lsize=(now->l?now->l->sz:0); if(idxl; else if(idx==lsize){ now->splay(); return now; }else{ idx-=lsize+1; now=now->r; } } } node *merge(node *l, node *r){ if(!l) return r; if(!r) return l; l=get(l, l->sz-1); l->r=r; r->p=l; l->update(); return l; } pair split(node *t, int k){//[0, k), [k, n) if(!t) return make_pair(nullptr, nullptr); if(k==0) return make_pair(nullptr, t); else if(k==t->sz) return make_pair(t, nullptr); t=get(t, k); node *s=t->l; if(s) s->p=nullptr; t->l=nullptr; t->update(); return make_pair(s, t); } int main() { int n, k; cin>>n>>k; string s; cin>>s; vector v(n); for(int i=0; il=v[i-1], v[i-1]->p=v[i], v[i]->update(); } node *root=v[n-1]; for(int i=0; itoggle(), q.first->push(); root=merge(p.first, merge(q.first, q.second)); } string ans; auto dfs=[&](auto dfs, node *now){ if(!now) return; dfs(dfs, now->l); ans+=now->val; dfs(dfs, now->r); }; dfs(dfs, root); cout<