#include #define INF 1000000000 #define LINF 1000000000000000000 #define MOD 1000000007 #define mod 998244353 #define F first #define S second #define ll long long #define N 300010 #define M ((1<<20)+10) using namespace std; struct SegT0{ int lo[M],hi[M],val[M],pd[M]; void build(int x,int l,int r){ lo[x]=l,hi[x]=r,val[x]=pd[x]=0; if(l==r) return; int mid=(l+r)>>1,a=x<<1; build(a,l,mid); build(a|1,mid+1,r); return; } void pushdown(int x){ int a=x<<1; val[a]+=pd[x],pd[a]+=pd[x]; val[a|1]+=pd[x],pd[a|1]+=pd[x]; pd[x]=0; return; } void update(int x,int l,int r,int v){ int tl=lo[x],tr=hi[x]; if(l<=tl&&tr<=r){ val[x]+=v,pd[x]+=v; return; } if(pd[x]!=0) pushdown(x); int mid=(tl+tr)>>1,a=x<<1; if(mid>=l) update(a,l,r,v); if(mid0) return -1; int tl=lo[x],tr=hi[x]; if(tl==tr) return tl; if(pd[x]!=0) pushdown(x); int mid=(tl+tr)>>1,a=x<<1; int ret=find(a); return ret==-1?find(a|1):ret; } }segt0; struct SegT1{ int lo[M],hi[M]; ll pd[M]; pair val[M]; void build(int x,int l,int r){ lo[x]=l,hi[x]=r,pd[x]=0; if(l==r){ val[x]=make_pair(-LINF,l); return; } int mid=(l+r)>>1,a=x<<1; build(a,l,mid); build(a|1,mid+1,r); val[x]=max(val[a],val[a|1]); return; } void pushdown(int x){ int a=x<<1; val[a].F+=pd[x],pd[a]+=pd[x]; val[a|1].F+=pd[x],pd[a|1]+=pd[x]; pd[x]=0; return; } void update(int x,int l,int r,ll v){ int tl=lo[x],tr=hi[x]; if(l<=tl&&tr<=r){ val[x].F+=v,pd[x]+=v; return; } if(pd[x]!=0) pushdown(x); int mid=(tl+tr)>>1,a=x<<1; if(mid>=l) update(a,l,r,v); if(mid>1,a=x<<1; if(mid>=l) modify(a,l,v); else modify(a|1,l,v); val[x]=max(val[a],val[a|1]); return; } pair query(int x,int l,int r){ int tl=lo[x],tr=hi[x]; if(l<=tl&&tr<=r) return val[x]; if(pd[x]!=0) pushdown(x); int mid=(tl+tr)>>1,a=x<<1; pair ret=make_pair(-LINF,-INF); if(mid>=l) ret=max(ret,query(a,l,r)); if(mid seq[N]; vector > upds[N]; string s,pth[N]; pair calc(int v){ segt1.build(1,0,m-1); f[0]=0,g[0]=0,pre[0]=-1; for(int i=0;i>n>>sx>>sy>>s; s+="S"; for(int i=0,lst=0;i0){ segt0.update(1,0,x-1,-1); upds[i].push_back(make_pair(x-1,-1)); } } else{ segt0.update(1,0,i,1); v++; } } if(v) upds[i].push_back(make_pair(i,v)); } int l=0,r=n+1; while(l>1; if(calc(mid).S>=sy+1) l=mid+1; else r=mid; } l--; vector p0,p1,pos; auto v0=calc(l); for(int i=m;i;i=pre[i]) p0.push_back(pre[i]); auto v1=calc(l+1); for(int i=m;i;i=pre[i]) p1.push_back(pre[i]); ll tot; if(v0.S==sy+1){ tot=v0.F+1ll*l*v0.S; pos=p0; } else{ tot=((v1.F+1ll*(l+1)*v1.S)-(v0.F+1ll*l*v0.S))*(ll)(sy+1-v0.S)/(ll)(v1.S-v0.S); tot+=v0.F+1ll*l*v0.S; pos=p1; for(auto i:p1) vis[i]=true; for(auto i:p0) if(pos.size()<=sy&&(!vis[i])) pos.push_back(i); } if(tot=0&&tot;i--){ int v0=lo[i]; for(auto c:pth[i]) v0=max(lo[i],v0+(c=='L'?-1:1)); int l=lo[i],r=hi[i]; while(l>1,v=lo[i]; for(auto c:pth[i]) v=max(lo[i],min(mid,v+(c=='L'?-1:1))); if(v0-v<=tot) r=mid; else l=mid+1; } hi[i]=l; int v=lo[i]; for(auto c:pth[i]) v=max(lo[i],min(hi[i],v+(c=='L'?-1:1))); tot-=v0-v; delta[i]=v0-v; } vector > ans; for(int i=0,s=0;i<=sy;i++){ lo[i]-=s,hi[i]-=s; s+=delta[i]; ans.push_back(make_pair(lo[i]-1,i)); ans.push_back(make_pair(hi[i]+1,i)); } for(int i=0;i<=sy;i++) for(int j=lo[i];j<=hi[i];j++){ if(i==sy||jhi[i+1]) ans.push_back(make_pair(j,i+1)); } sort(ans.begin(),ans.end()); ans.erase(unique(ans.begin(),ans.end()),ans.end()); cout<