看上去像是匹配，字典序最小？无法保证。
贪心处理？
不妨考虑从前到后，尽量填小的，要使得后面一定有解即可！
相当于一个完美匹配！
根据Hall定理，枚举字符集子集s，使得s的所有个数小于等于相邻的点个数
又是后缀，所以预处理，b[i][s]，[i,n]，可填集合和s有交集的位置的数量。
验证即可。
O(6*2^6*n)
注意无解Impossible
#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') #define pb push_back #define solid const auto & #define enter cout<<endl #define pii pair<int,int> using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);} template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar(' ');} namespace Modulo{ const int mod=998244353; int ad(int x,int y){return (x+y)>=mod?x+y-mod:x+y;} void inc(int &x,int y){x=ad(x,y);} int mul(int x,int y){return (ll)x*y%mod;} void inc2(int &x,int y){x=mul(x,y);} int qm(int x,int y=mod-2){int ret=1;while(y){if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;} } //using namespace Modulo; namespace Miracle{ const int N=1e5+5; int buc[6]; int a[N],b[N][1<<6]; int sz[1<<6]; char s[N],cc[233]; int n; int lim=(1<<6)-1; bool che(int p,int c){ for(reg s=1;s<=lim;++s){ int lp=sz[s]; if(s&(1<<c)) --lp; if(lp>b[p][s]) return false; } return true; } int main(){ scanf("%s",s+1); n=strlen(s+1); for(reg i=1;i<=n;++i){ ++buc[s[i]-'a']; a[i]=lim; } int m;rd(m); for(reg i=1;i<=m;++i){ int p;rd(p); a[p]=0; scanf("%s",cc+1); int l=strlen(cc+1); for(reg j=1;j<=l;++j){ a[p]|=(1<<(cc[j]-'a')); } } for(reg i=n;i>=1;--i){ for(reg t=0;t<=lim;++t){ b[i][t]=b[i+1][t]; if(t&a[i]) ++b[i][t]; } } for(reg s=0;s<=lim;++s){ sz[s]=0; for(reg j=0;j<6;++j){ if(s&(1<<j)){ sz[s]+=buc[j]; } } } for(reg i=1;i<=n;++i){ bool fl=false; for(reg j=0;j<6;++j){ if(buc[j]&&a[i]&(1<<j)){ if(che(i+1,j)){ s[i]='a'+j; fl=true; --buc[j]; break; } } } if(!fl){ printf("Impossible");return 0; } for(reg s=0;s<=lim;++s){ sz[s]=0; for(reg j=0;j<6;++j){ if(s&(1<<j)){ sz[s]+=buc[j]; } } } } printf("%s",s+1); return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* */