#include using namespace std; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a struct BBSTBase{ using u32 = uint32_t; u32 xor128(){ static u32 x = 123456789; static u32 y = 362436069; static u32 z = 521288629; static u32 w = 88675123; u32 t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } static array pool; size_t ptr; BBSTBase():ptr(0){} size_t count(const Node *a){ return a?a->cnt:0; } inline Node* create(){ return &pool[ptr++]; } inline Node* create(Node v){ return &(pool[ptr++]=v); } virtual void toggle(Node *a)=0; virtual Node* eval(Node* a)=0; virtual Node* recalc(Node* a)=0; Node* toggle(Node *a,size_t l,size_t r){ auto s=split(a,l); auto t=split(s.second,r-l); auto u=eval(t.first); toggle(u); return merge(s.first,merge(u,t.second)); } Node* merge(Node* a,Node* b){ if(a==nullptr) return b; if(b==nullptr) return a; if(xor128()%(count(a)+count(b))r=merge(a->r,b); a->r->p=a; return recalc(a); } b=eval(b); b->l=merge(a,b->l); b->l->p=b; return recalc(b); } pair split(Node* a,size_t k){ if(a==nullptr) return make_pair(a,a); a=eval(a); if(k<=count(a->l)){ if(a->l) a->l->p=nullptr; auto s=split(a->l,k); a->l=s.second; if(a->l) a->l->p=a; return make_pair(s.first,recalc(a)); } if(a->r) a->r->p=nullptr; auto s=split(a->r,k-(count(a->l)+1)); a->r=s.first; if(a->r) a->r->p=a; return make_pair(recalc(a),s.second); } Node* insert(Node *a,size_t pos,Node v){ Node* b=create(v); auto s=split(a,pos); return a=merge(merge(s.first,b),s.second); } Node* erase(Node *a,size_t pos){ auto s=split(a,pos); auto t=split(s.second,1); return merge(s.first,t.second); } Node* find_by_order(Node *a,size_t k){ assert(kl); if(kl,k); if(k>num) return find_by_order(a->r,k-(num+1)); return a; } inline bool is_right(Node* a){ return a->p&&a->p->r==a; } size_t order_of_key(Node* a){ size_t res=count(a->l); while(a){ if(is_right(a)) res+=count(a->p->l)+1; a=a->p; } return res; } Node* build(size_t l,size_t r,const vector &vs){ if(l+1==r) return create(vs[l]); size_t m=(l+r)>>1; return merge(build(l,m,vs),build(m,r,vs)); } Node* build(const vector &vs){ return build(0,vs.size(),vs); } }; template array BBSTBase::pool; template struct NodeBase{ using T = Tp; NodeBase *l,*r,*p; size_t cnt; bool rev; T val; NodeBase():cnt(1),rev(0){l=r=p=nullptr;} NodeBase(T val): cnt(1),rev(0),val(val){l=r=p=nullptr;} }; template struct Array : BBSTBase{ using T = typename Node::T; using super = BBSTBase; Array():super(){} using super::count; Node* recalc(Node *a){ a->cnt=count(a->l)+1+count(a->r); return a; } using super::toggle; void toggle(Node *a){ swap(a->l,a->r); a->rev^=1; } // remove "virtual" for optimization virtual Node* eval(Node* a){ if(a->rev){ if(a->l) toggle(a->l); if(a->r) toggle(a->r); a->rev=false; } return recalc(a); } using super::find_by_order; Node* set_val(Node *a,size_t k,T val){ auto b=find_by_order(a,k); b->val=val; return b; } T get_val(Node *a,size_t k){ return find_by_order(a,k)->val; } void dump(Node* a,typename vector::iterator it){ if(!count(a)) return; if(a->rev){ if(a->l) toggle(a->l); if(a->r) toggle(a->r); a->rev=false; } dump(a->l,it); *(it+count(a->l))=a->val; dump(a->r,it+count(a->l)+1); } vector dump(Node* a){ vector vs(count(a)); dump(a,vs.begin()); return vs; } }; //INSERT ABOVE HERE signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,k; cin>>n>>k; string s; cin>>s; const size_t LIM = 1e6; using Node = NodeBase; Array as; vector vs; for(int i=0;i