最直观的想法是贪心取， 然后网络流取check可不可行， 然后T了。

想到最大流可以等于最小割， 那么我们状压枚举字符代表的6个点连向汇点是否断掉，

然后再枚举64个本质不同的位置， 是否需要切段原点联想它的边， 单次check复杂度64 * 64

用sosdp能优化到64 * 6

#include
     
      #define LL long long#define LD long double#define ull unsigned long long#define fi first#define se second#define mk make_pair#define PLL pair
      
       #define PLI pair
       
        #define PII pair
        
         #define SZ(x) ((int)x.size())#define ALL(x) (x).begin(), (x).end()using namespace std;const int N = 2e5 + 7;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const int mod = 1e9 + 7;const double eps = 1e-8;const double PI = acos(-1);template
         
           inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;}template
          
            inline void sub(T& a, S b) {a -= b; if(a < 0) a += mod;}template
           
             inline bool chkmax(T& a, S b) { return a < b ? a = b, true : false;}template
            
              inline bool chkmin(T& a, S b) { return a > b ? a = b, true : false;}int n, m, mask[N], c[N], cnt[N], sos[N];char s[N], t[N], ans[N];bool check() { int sum = 0, ret = inf; for(int i = 0; i < 6; i++) sum += c[i]; for(int i = 0; i < 64; i++) sos[i] = cnt[i]; for(int i = 0; i < 6; i++) for(int j = 0; j < 64; j++) if(j >> i & 1) sos[j] += sos[j ^ (1 << i)]; for(int s1 = 0; s1 < 64; s1++) { int tmp = 0; for(int i = 0; i < 6; i++) if(s1 >> i & 1) tmp += c[i]; tmp += sum - sos[s1]; chkmin(ret, tmp); } return sum == ret;}inline int getId(char c) { return c - 'a';}int main() { scanf("%s", s + 1); n = strlen(s + 1); for(int i = 1; i <= n; i++) c[getId(s[i])]++; scanf("%d", &m); while(m--) { int p; scanf("%d%s", &p, t + 1); for(int i = 1; t[i]; i++) mask[p] |= 1 << getId(t[i]); } for(int i = 1; i <= n; i++) { if(!mask[i]) mask[i] = 63; cnt[mask[i]]++; } for(int i = 1; i <= n; i++) { bool flag = false; for(int j = 0; j < 6; j++) { if(c[j] && mask[i] >> j & 1) { c[j]--; cnt[mask[i]]--; flag = check(); if(flag) { ans[i] = 'a' + j; break; } c[j]++; cnt[mask[i]]++; } } if(!flag) return puts("Impossible"), 0; } ans[n + 1] = '\0'; puts(ans + 1); return 0;}/**/