小 L 计划进行 $n$ 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。
小 L 的赛车有三辆，分别用大写字母 A、B、C 表示。地图一共有四种，分别用小写字母 x、a、b、c 表示。其中，赛车 A 不适合在地图 a 上使用，赛车 B 不适合在地图 b 上使用，赛车 C 不适合在地图 c 上使用，而地图 x 则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有 d 张。
$n$ 场游戏的地图可以用一个小写字母组成的字符串描述。例如：$\underline{S=xaabxcbc}$ 表示小 L 计划进行 8 场游戏，其中第 1 场和第 5 场的地图类型是 x，适合所有赛车，第 2 场和第 3 场的地图是 a，不适合赛车 A，第 4 场和第 7 场的地图是 b，不适合赛车 B，第 6 场和第 8 场的地图是 c，不适合赛车 C。
小 L 对游戏有一些特殊的要求，这些要求可以用四元组 $(i,h_i , j,h_j )$ 来描述，表示若在第 $i$ 场使用型号为 $h_i$ 的车子，则第 $j$ 场游戏要使用型号为 $h_j$ 的车子。
你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。如果无解，输出 “-1”（不含双引号）。
输入格式
输入第一行包含两个非负整数 $n,d$。
输入第二行为一个字符串 $S$ 。
$n,d,S$ 的含义见题目描述，其中 $S$ 包含 $n$ 个字符，且其中恰好 $d$ 个为小写字母 $x$。
输入第三行为一个正整数 $m$ ，表示有 $m$ 条用车规则。接下来 $m$ 行，每行包含一个四元组 $i,h_i,j,h_j$ ，其中 $i,j$ 为整数，$h_i,h_j$ 为字符 A 、B 或 C，含义见题目描述。
输出格式
输出一行。
若无解，输出 “-1”（不含双引号）。
若有解，则包含一个长度为 $n$ 的仅包含大写字母 A、B、C 的字符串，表示小 L 在这 $n$ 场游戏中如何安排赛车的使用。如果存在多组解，输出其中任意一组即可。
样例一
input
3 1 xcc 1 1 A 2 B
output
ABA
explanation
小 L 计划进行 3 场游戏，其中第 1 场的地图类型是 x，适合所有赛车，第 2 场和第 3 场的地图是 c，不适合赛车 C。
小 L 希望：若第 1 场游戏使用赛车 A，则第 2 场游戏使用赛车 B。
那么为这 3 场游戏分别安排赛车 A、B、A 可以满足所有条件。
若依次为 3 场游戏安排赛车为 BBB 或 BAA 时，也可以满足所有条件，也被视为正确答案。但依次安排赛车为 AAB 或 ABC 时，因为不能满足所有条件，所以不被视为正确答案。
样例二
见下载文件中的 ex_game2.in 与 ex_game2.ans。
限制与约定
| 测试点编号 | $n$ | $d$ | $m$ | 其他性质 |
|---|---|---|---|---|
| 1 | $\le 2$ | $0$ | $\le 4$ | 无 |
| 2 | $\le n$ | |||
| 3 | $\le 5$ | $0$ | $\le 10$ | |
| 4 | $\le n$ | |||
| 5 | $\le 10$ | $0$ | $\le 20$ | |
| 6 | $\le 8$ | |||
| 7 | $\le 20$ | $0$ | $\le 40$ | S中只包含c |
| 8 | 无 | |||
| 9 | $\le 8$ | S中只包含x或c | ||
| 10 | 无 | |||
| 11 | $\le 100$ | $0$ | $\le 200$ | S中只包含c |
| 12 | 无 | |||
| 13 | $\le 8$ | S中只包含x或c | ||
| 14 | 无 | |||
| 15 | $\le 5000$ | $0$ | $\le 10000$ | |
| 16 | $\le 8$ | S中只包含x或c | ||
| 17 | 无 | |||
| 18 | $\le 50000$ | $0$ | $\le 100000$ | |
| 19 | $\le 8$ | S中只包含x或c | ||
| 20 | 无 |
时间限制：1s $2\texttt{s}$
空间限制：$512\texttt{MB}$
鄂公网安备 42010202000505 号