#include using namespace std; #define int long long #define rep(i,n) for(int i=0;i=0;i--) #define all(v) v.begin(),v.end() #define P pair #define len(s) (int)s.size() template inline bool chmin(T &a, T b){ if(a>b){a=b;return true;} return false; } template inline bool chmax(T &a, T b){ if(a>S>>T; assert(len(S)<=100000&&len(T)<=100000); rep(i,26){ nexS[len(S)][i]=len(S); nexT[len(T)][i]=len(T); } rev(i,len(S)){ rep(j,26)nexS[i][j]=nexS[i+1][j]; nexS[i][S[i]-'a']=i; } rev(i,len(T)){ rep(j,26)nexT[i][j]=nexT[i+1][j]; nexT[i][T[i]-'a']=i; } int now=len(T);inc[len(S)]=now; rev(i,len(S)){ now=max(-1ll,now-1); while(now>=0&&T[now]!=S[i])now--; inc[i]=now; } if(inc[0]!=-1){ cout<<"-1\n";return 0; } string Ans; int curS=0,curT=0; while(curS=nexT[curT][i]+1)continue; curS=nexS[curS][i]+1; curT=nexT[curT][i]+1; Ans+=('a'+i); break; } } }