对于所有的x，我们枚举他的地图类型，事实上我们只需要枚举前两种地形就可以覆盖所有的情况。
之后就变成了裸的2-sat问题。
对于一个限制，我们分类讨论：
1.h[u]不可选，跳过
2.h[v]不可选，则h[v]也不可选，将u与u‘连边，表示u不可选。
3.否则从u向v连边表示选u就必须选v，从u’向v‘连边表示选v'就必须选u’（逆否命题）。
tarjan缩点判断可行性。
输出方案按照缩点编号选择编号小的点输出即可（逆序拓扑序）。
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define maxn 400005
using namespace std;
inline int read() {
int x=,f=;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-;
for(;isdigit(ch);ch=getchar()) x=x*+ch-'';
return x*f;
}
struct Edge {int to,nxt;}e[maxn*];
int head[maxn],cnt;
void add(int u,int v) {e[cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt++;}
struct Ask {int u,v;char a[],b[];}q[maxn];
int n,d,pos[maxn],m;
char s[maxn],cs[maxn];
bool flag=;
int dfn[maxn],low[maxn],tot,bel[maxn],par[maxn],l[maxn],r[maxn],sta[maxn],top,scc;
bool vis[maxn],inq[maxn];
void init() {
memset(head,-,sizeof(head));cnt=;
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(bel,,sizeof(bel));tot=;scc=;
memset(vis,,sizeof(vis));
memset(inq,,sizeof(inq));
}
void tarjan(int x) {
dfn[x]=low[x]=++tot;sta[++top]=x;inq[x]=;
for(int i=head[x];i>=;i=e[i].nxt) {
int to=e[i].to;
if(!dfn[to]) {
tarjan(to);
low[x]=min(low[x],low[to]);
}
else if(inq[to]) {low[x]=min(low[x],dfn[to]);}
}
if(dfn[x]==low[x]) {
scc++;
while() {
inq[sta[top]]=;
bel[sta[top--]]=scc;
if(sta[top+]==x) break;
}
}
}
int que[maxn],fro,tail,in[maxn];
void work() {
init();
for(int i=;i<=n;i++) {
int ttmp=;
if(s[i]=='x') {s[i]=cs[i];ttmp=;}
if(s[i]=='a') {l[i]=i+n,r[i]=i+n+n;}
if(s[i]=='b') {l[i]=i,r[i]=i+n+n;}
if(s[i]=='c') {l[i]=i,r[i]=i+n;}
if(ttmp==) s[i]='x';
par[l[i]]=r[i];par[r[i]]=l[i];vis[r[i]]=vis[l[i]]=;
}
int ql,qr;
for(int i=;i<=m;i++) {
if(q[i].a[]=='A') ql=q[i].u;
else if(q[i].a[]=='B') ql=q[i].u+n;
else ql=q[i].u+n+n;
if(q[i].b[]=='A') qr=q[i].v;
else if(q[i].b[]=='B') qr=q[i].v+n;
else qr=q[i].v+n+n;
if(ql==qr) continue;
if(!vis[ql]) continue;
if(!vis[qr]) {
add(ql,par[ql]);
continue;
}
add(ql,qr);add(par[qr],par[ql]);
}
for(int i=;i<=n+n+n;i++) {if(vis[i]&&!dfn[i]) tarjan(i);}
for(int i=;i<=n+n+n;i++) {
if(!vis[i]) continue;
if(bel[i]==bel[par[i]]) return;
}
flag=;
for(int i=;i<=n;i++) {
int out=;
if(bel[l[i]]<bel[r[i]]) out=l[i];
else out=r[i];
if(out==i) printf("A");
else if(out==i+n) printf("B");
else printf("C");
}
}
void dfs(int x) {
if(x==d+) {
work();
if(flag) exit();
return;
}
cs[pos[x]]='a';dfs(x+);
cs[pos[x]]='b';dfs(x+);
}
int main() {
n=read(),d=read();
scanf("%s",s+);
for(int i=;i<=n;i++) {if(s[i]=='x') pos[++pos[]]=i;}
m=read();
for(int i=;i<=m;i++) {q[i].u=read();scanf("%s",q[i].a+);q[i].v=read();scanf("%s",q[i].b+);}
dfs();printf("-1\n");
}