#2305. 「NOI2017」游戏

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: nzhtl1477

题目描述

小 L 计划进行 n 场游戏,每场游戏使用一张地图,小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆,分别用大写字母 A B C 表示。地图一共有四种,分别用小写字母 x a b c 表示。

其中,赛车 A 不适合在地图 a 上使用,赛车 B 不适合在地图 b 上使用,赛车 C 不适合在地图 c 上使用,而地图 x 则适合所有赛车参加。

适合所有赛车参加的地图并不多见,最多只会有 d 张。

n 场游戏的地图可以用一个小写字母组成的字符串描述。例如: S=\texttt{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

样例

样例输入

3 1
xcc
1
1 A 2 B

样例输出

ABA

L 计划进行 3 场游戏,其中第 1 场的地图类型是 x ,适合所有赛车,第 2 场和第 3 场的地图是 c ,不适合赛车 C

L 希望:若第 1 场游戏使用赛车 A ,则第 2 场游戏使用赛车 B

那么为这 3 场游戏分别安排赛车 A B A 可以满足所有条件。

若依次为 3 场游戏安排赛车为 BBB BAA 时,也可以满足所有条件,也被视为正确答案。

但依次安排赛车为 AAB ABC 时,因为不能满足所有条件,所以不被视为正确答案。

数据范围与提示

Screen Shot 2018-03-12 at 23.17.17.png