从题面中四元组\((i,h_i,j,h_j)\)限制选择车子型号，不难想到这题要用\(2-SAT\)解决。
考虑转化为\(2-SAT\)模型，发现除地图\(x\)外，其他地图都只有两种车子型号可以参加，那么就把这两种型号转化为两种状态。
若\(S_i=a\)，则状态为\(B\)和\(C\)。
若\(S_i=b\)，则状态为\(A\)和\(C\)。
若\(S_i=c\)，则状态为\(A\)和\(B\)。
然后讨论四元组的情况，设\(i\)为输入的状态，\(i^\prime\)为另一个状态。
若在第\(i\)场，\(h_i\)不可用，则不进行连边。
若在第\(i\)场，\(h_i\)可用，在第\(j\)场，\(h_j\)不可用，则从\(i\)向\(i^\prime\)连边，表示不能选\(i\)。
若两个都可用，则从\(i\)向\(j\)连边，表示若选\(i\)，则一定选\(j\)，同时从\(j^\prime\)向\(i^\prime\)连边，这里表示若没有选\(j\)，则一定没有选\(i\)。
继续考虑如何处理地图\(x\)，发现其数量\(d\leqslant8\)，数据规模很小，那么我们就可以用\(dfs\)将其所有可能的情况枚举一遍，再检查是否合法。
我们只需考虑地图\(x\)等价于地图\(a\)和地图\(b\)两种情况，因为此时已经包括\(A,B,C\)三种车型了。
时间复杂度为\(O(2^d(n+m))\)。
实现细节还是蛮多的，不清楚的就看代码吧。
\(code:\)
#include<bits/stdc++.h>
#define maxn 1000010
using namespace std;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,d,m,x_cnt;
bool flag;
char s[maxn],a[5],b[5],c1[maxn],c2[maxn];
int pos[maxn];
struct node
{
int x,y;
char a,b;
}t[maxn];
struct edge
{
int to,nxt;
}e[maxn];
int head[maxn],edge_cnt;
void add(int from,int to)
{
e[++edge_cnt]=(edge){to,head[from]};
head[from]=edge_cnt;
}
int dfn_cnt,co_cnt,top;
int dfn[maxn],low[maxn],co[maxn],st[maxn];
bool vis[maxn];
void tarjan(int x)
{
dfn[x]=low[x]=++dfn_cnt;
st[++top]=x;
vis[x]=true;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(!dfn[y])
{
tarjan(y);;
low[x]=min(low[x],low[y]);
}
else if(vis[y])
low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x])
{
co_cnt++;
int now;
do
{
now=st[top--];
vis[now]=false;
co[now]=co_cnt;
}while(now!=x);
}
}
bool check()
{
for(int i=1;i<=2*n;++i)
if(!dfn[i])
tarjan(i);
for(int i=1;i<=n;++i)
if(co[i]==co[i+n])
return false;
return true;
}
void clear()
{
edge_cnt=dfn_cnt=co_cnt=top=0;
memset(st,0,sizeof(st));
memset(co,0,sizeof(co));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(vis,0,sizeof(vis));
memset(head,0,sizeof(head));
}
void work()
{
clear();
for(int i=1;i<=m;++i)
{
int x=t[i].x,y=t[i].y;
char a=t[i].a,b=t[i].b;
if(s[x]==a) continue;
if(s[y]==b)
{
add(x+(a==c2[x])*n,x+(a==c1[x])*n);
continue;
}
add(x+(a==c2[x])*n,y+(b==c2[y])*n);
add(y+(b==c1[y])*n,x+(a==c1[x])*n);
}
if(check())
{
flag=true;
for(int i=1;i<=n;i++)
{
if(co[i]<co[i+n]) printf("%c",c1[i]);
else printf("%c",c2[i]);
}
}
}
void dfs(int x)
{
if(flag) return;
if(x==d+1)
{
work();
return;
}
int now=pos[x];
s[now]='A',c1[now]='B',c2[now]='C',dfs(x+1);
s[now]='B',c1[now]='A',c2[now]='C',dfs(x+1);
}
int main()
{
read(n),read(d);
scanf("%s",s+1);
for(int i=1;i<=n;++i)
{
s[i]+='A'-'a';
if(s[i]=='A') c1[i]='B',c2[i]='C';
if(s[i]=='B') c1[i]='A',c2[i]='C';
if(s[i]=='C') c1[i]='A',c2[i]='B';
if(s[i]=='X') pos[++x_cnt]=i;
}
read(m);
for(int i=1;i<=m;++i)
{
read(t[i].x),scanf("%s",a),read(t[i].y),scanf("%s",b);
t[i].a=a[0],t[i].b=b[0];
}
dfs(1);
if(!flag) printf("-1");
return 0;
}