RE AC WA都有。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<stack>
#include<cstring>
#define MAX (int)(2e5+10)
using namespace std;
stack <int> S;
int n,m,dd,cnt=0,tot=0,scnt=0,t=0;
int d[MAX],scc[MAX],head[MAX],low[MAX];
int ni[MAX],nj[MAX],cx[MAX];
bool vis[MAX],flag=0;
char c[MAX],hi[MAX],hj[MAX];
struct edge{
	int to;int nxt;
}E[MAX];
void build(int x,int y){
	E[++cnt].to=y;
	E[cnt].nxt=head[x];
	head[x]=cnt;
}
char getc(int u,int nu){
	if(nu==2*u-1) return c[u]=='a'?'B':'A';
	else return c[u]=='c'?'B':'C';
}
int getn(int u,int hu){
	if(hu=='A'||(hu=='B'&&c[u]=='a')) return 2*u-1;
	if(hu=='C'||(hu=='B'&&c[u]=='c')) return 2*u;
}
int res(int p){
	return p%2?p+1:p-1;
}
void TJ(int x){
	d[x]=low[x]=++tot;
	S.push(x);
	vis[x]=1;
	for(int i=head[x]; i; i=E[i].nxt){
		int y=E[i].to;
		if(!d[y]){
			TJ(y);
			low[x]=min(low[x],low[y]);
		}
		else if(vis[y]){
			low[x]=min(low[x],d[y]);
		}
	}
	if(d[x]==low[x]){
		scnt++;
		int s;
		do{
			s=S.top();
			vis[s]=0;
			scc[s]=scnt;
			S.pop();
		}while(s!=x);
	}
}
void Clear(){
	tot=0,scnt=0;
	memset(head,0,sizeof(head));
	memset(low,0,sizeof(low));
	memset(vis,0,sizeof(vis));
	memset(d,0,sizeof(d));
	cnt=0;
}
bool judge(){
	for(int i=1; i<=n; i++)
		if(scc[i]==scc[i+n]) return 0;
	return 1;
}
bool Solve(){
	Clear();
	for(int i=1; i<=m; i++){
		if(hi[i]!=c[ni[i]]-32&&hj[i]==c[nj[i]]-32){
			if(getn(hi[i],hi[i])==2*ni[i]) build(2*ni[i],2*ni[i]-1);
			else build(2*ni[i-1],2*ni[i]);
		}
		else if(hi[i]!=c[ni[i]]-32){
			build(getn(ni[i],hi[i]),getn(nj[i],hj[i]));
			build(res(getn(nj[i],hj[i])),res(getn(ni[i],hi[i])));
		}
	}
	for(int i=1; i<+2*n; i++) if(!d[i]) TJ(i);
	return judge();
}
void dfs(int i){
	if(i==dd+1)
		if(Solve()){
			flag=1;return;
		}
	c[cx[i]]='a',dfs(i+1);
	if(flag) return;
	c[cx[i]]='c',dfs(i+1);
}
int main(){
	scanf("%d%d",&n,&dd);
	cin>>c+1;
	for(int i=1; i<=n; i++) if(c[i]=='x') cx[++t]=i;
	scanf("%d",&m);
	for(int i=1; i<=m; i++) cin>>ni[i]>>hi[i]>>nj[i]>>hj[i];
	dfs(1);
	if(flag) for(int i=1; i<=n; i++)
		cout<<(getc(i,2*i-(scc[2*i-1]<scc[2*i])));
	else cout<<-1;
	return 0;
}