1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| const int N=2e5+10,INF=1e9+10;
int n,m;
char s[N];
int trans[N][26],link[N],len[N],End[N],cnt,lst;
void Extend(int c){
int p=lst,cur=++cnt; len[cur]=len[lst]+1,lst=cur;
End[cur]=len[cur];
while(~p && !trans[p][c]) trans[p][c]=cur,p=link[p];
if(p==-1){ link[cur]=0; return; }
int q=trans[p][c];
if(len[q]==len[p]+1){ link[cur]=q; return; }
int r=++cnt;
len[r]=len[p]+1,memcpy(trans[r],trans[q],104);
while(~p && trans[p][c]==q) trans[p][c]=r,p=link[p];
link[r]=link[q],link[q]=link[cur]=r;
}
const int M=N*32;
int ls[M],rs[M];
void Upd(int &p,int l,int r,int x){
p=++cnt;
if(l==r) return;
int mid=(l+r)>>1;
x<=mid?Upd(ls[p],l,mid,x):Upd(rs[p],mid+1,r,x);
}
int Uni(int x,int y) {
if(!x||!y) return x|y;
int z=++cnt;
ls[z]=Uni(ls[x],ls[y]),rs[z]=Uni(rs[x],rs[y]);
return z;
}
int Que(int p,int l,int r,int ql,int qr) {
if(ql>qr || !p) return 0;
if(ql<=l && r<=qr) return 1;
int mid=(l+r)>>1;
if(ql<=mid && Que(ls[p],l,mid,ql,qr)) return 1;
if(qr>mid && Que(rs[p],mid+1,r,ql,qr)) return 1;
return 0;
}
vector <int> G[N];
int rt[N];
void dfs(int u) {
if(End[u]) Upd(rt[u],1,n,End[u]);
for(int v:G[u]) dfs(v),rt[u]=Uni(rt[u],rt[v]);
}
int K[N];
void Solve(){
int l=rd(),r=rd();
scanf("%s",s+1),m=strlen(s+1),s[m+1]='a'-1;
int p=0;
rep(i,1,m) {
K[i]=trans[K[i-1]][s[i]-'a'];
if(!K[i]) break;
p=i;
}
drep(i,p,0) {
rep(j,s[i+1]-'a'+1,25) {
int x=trans[K[i]][j];
if(!x) continue;
if(!Que(rt[x],1,n,l+i,r)) continue;
s[i+1]=j+'a',s[i+2]=0,puts(s+1);
return;
}
}
puts("-1");
}
int main(){
link[0]=-1,scanf("%s",s+1),n=strlen(s+1);
rep(i,1,n) Extend(s[i]-'a');
rep(i,1,cnt) G[link[i]].pb(i);
cnt=0,dfs(0);
rep(_,1,rd()) Solve();
}
|