非常基础的SAMSAMSAM题目。

假设给你了S1S_1S1​，那么显然非常好求，随便怎么搞都行。

字典序这玩意也非常好翻译啊，直接枚举前缀LCSLCSLCS就完了。

然后就是实现细节。乍一看这玩意要线段树合并，还要可持久化啊 直接把我劝退了 。不过如果固定了rrr就非常好做，因此直接一波离线即可。

很久没打这种数据结构了

一遍过了，就很离谱。要是考场上有这手感还愁打不出来数据结构？？？

#include
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std;
const int N=4e5+5;
int Q,n,tot,last,L[N],R[N],ed[N];
int num,dfn[N],sz[N],id[N];
string s;
string q[200005];
string ans[200005];
vectorG[N];
vectorg[N];
struct node{int link,len,to[26];
}t[N];
void extend(char c){int cur=++tot;t[cur].len=t[last].len+1;int p=last;while(p!=-1&&!t[p].to[c-'a']){t[p].to[c-'a']=cur;p=t[p].link;}if(p!=-1) {int q=t[p].to[c-'a'];if(t[p].len+1==t[q].len){t[cur].link=q;}else{int clone=++tot;t[clone].len=t[p].len+1;t[clone].link=t[q].link;for(int i=0;i<26;i++)t[clone].to[i]=t[q].to[i];while(p!=-1&&t[p].to[c-'a']==q){t[p].to[c-'a']=clone;p=t[p].link;}t[q].link=t[cur].link=clone;}}last=cur;
} 
void dfs(int u){sz[u]=1,dfn[u]=++num;for(auto v:g[u]){dfs(v),sz[u]+=sz[v];}
}
int T[N<<2];
void ins(int p,int l,int r,int x,int y){if(l==r){T[p]=y;return;}int mid=l+r>>1;x<=mid?ins(p<<1,l,mid,x,y):ins(p<<1|1,mid+1,r,x,y);T[p]=max(T[p<<1],T[p<<1|1]);
}
int qry(int p,int l,int r,int ql,int qr){if(ql<=l&&r<=qr){return T[p];}int mid=l+r>>1;if(qr<=mid)return qry(p<<1,l,mid,ql,qr);if(midif(x&&qry(1,1,num,dfn[x],dfn[x]+sz[x]-1)>=y){return 1;}return 0;
}
void work(int j){int len=q[j].size();int it=0,k=0;while(kid[k]=it,it=t[it].to[q[j][k]-'a'],k++;}id[k]=it;for(;~k;k--){int down=(k==len)?0:q[j][k]-'a'+1;for(int l=down;l<26;l++){if(ask(t[id[k]].to[l],L[j]+k)){for(int i=0;ians[j]+=q[j][i];}ans[j]+=('a'+l);return;}}}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0); cin>>s>>Q,n=s.size();t[0].link=-1;memset(T,-1,sizeof T);for(int i=0;icin>>L[i]>>R[i]>>q[i],L[i]--,R[i]--;G[R[i]].pb(i);}for(int i=1;i<=tot;i++){g[t[i].link].pb(i);}dfs(0);for(int i=0;iins(1,1,num,dfn[ed[i]],i);for(auto j:G[i]){work(j);}}for(int i=1;i<=Q;i++){if(!ans[i].size()){cout<<"-1"<<"\n";}else {cout<