#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
const int maxn = 1e5 + 10;
const int L = 10;
int n, m, d, sc, tot, top, p[L], dfn[maxn], low[maxn], scc[maxn], stk[maxn];
bool check, instack[maxn];
char s[maxn];
vector<int> e[maxn];
vector<tuple<int, char, int, char> > g;
#define A(x, ch, t) (x + (((s[x] - 96) % 3 != (ch - 65)) ^ t) * n)
void tarjan(int u) {
	low[u] = dfn[stk[++top] = u] = ++tot, instack[u] = true;
	for (int v : e[u])
		if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
		else if (instack[v]) low[u] = min(low[u], dfn[v]);
	if (dfn[u] == low[u]) {
		sc++;
		while (stk[top] != u) scc[stk[top]] = sc, instack[stk[top--]] = false;
		scc[stk[top]] = sc; instack[stk[top--]] = false;
	}
}
bool solve() {
	for (int i = 1; i <= n << 1; i++) e[i].clear(), dfn[i] = 0; tot = 0;
	for (auto [u, cu, v, cv] : g)
		if (s[u] != cu + 32)
			if (s[v] != cv + 32) e[A(u, cu, 0)].push_back(A(v, cv, 0)), e[A(v, cv, 1)].push_back(A(u, cu, 1));
			else e[A(u, cu, 0)].push_back(A(u, cu, 1));
	for (int i = 1; i <= n << 1; i++) if (!dfn[i]) tarjan(i);
	for (int i = 1; i <= n; i++) if (scc[i] == scc[i + n]) return false;
	for (int i = 1; i <= n; i++) cout << (char)(65 + (s[i] - 94 + (scc[i] < scc[i + n] ? -1 : 1)) % 3);
	return true;
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> d >> s + 1 >> m; d = 0; g.resize(m);
	for (int i = 1; i <= n; i++) if (s[i] == 'x') p[d++] = i;
	for (auto& [u, cu, v, cv] : g) cin >> u >> cu >> v >> cv, --u, --v;
	for (int mask = 0; mask < 1 << d; mask++) {
		for (int i = 0; i < d; i++) s[p[i]] = 97 + (mask >> i & 1);
		if (solve()) return 0;
	} cout << -1 << '\n';
	return 0;
}

hack样例：

2 1
xc
3
2 B 2 A
2 A 1 C
2 B 1 A

正确答案：

CA

代码答案：

BB