#P50437. 「NOI2017」游戏

「NOI2017」游戏

题目描述

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

小 L 的赛车有三辆,分别用大写字母 AABBCC 表示。地图一共有四种,分别用小写字母 xxaabbcc 表示。

其中,赛车 AA 不适合在地图 aa 上使用,赛车 BB 不适合在地图 bb 上使用,赛车 CC 不适合在地图 cc 上使用,而地图 xx 则适合所有赛车参加。

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

nn 场游戏的地图可以用一个小写字母组成的字符串描述。例如:S=xaabxcbcS=\texttt{xaabxcbc} 表示小 L 计划进行 88 场游戏,其中第 11 场和第 55 场的地图类型是 xx,适合所有赛车,第 22场和第 33 场的地图是 aa,不适合赛车 AA,第 44 场和第 77 场的地图是 bb,不适合赛车 BB,第 66 场和第 88 场的地图是 cc,不适合赛车 CC

小 L 对游戏有一些特殊的要求,这些要求可以用四元组 (i,hi,j,hj) (i, h_i, j, h_j) 来描述,表示若在第 ii 场使用型号为 hih_i 的车子,则第 jj 场游戏要使用型号为 hjh_j 的车子。

你能帮小 L 选择每场游戏使用的赛车吗?如果有多种方案,输出任意一种方案。

如果无解,输出 -1

输入格式

输入第一行包含两个非负整数 nn, dd

输入第二行为一个字符串 SS

nn, dd, SS 的含义见题目描述,其中 SS 包含 nn 个字符,且其中恰好 dd 个为小写字母 xx

输入第三行为一个正整数 mm ,表示有 mm 条用车规则。

接下来 mm 行,每行包含一个四元组 i,hi,j,hji,h_i,j,h_j ,其中 i,ji,j 为整数,hi,hjh_i,h_j 为字符 AABBCC,含义见题目描述。

输出格式

输出一行。

若无解输出 -1

样例

3 1
xcc
1
1 A 2 B
ABA

LL 计划进行 33 场游戏,其中第 11 场的地图类型是 xx,适合所有赛车,第 22 场和第 33 场的地图是 cc,不适合赛车 CC

LL 希望:若第 11 场游戏使用赛车 AA,则第 22 场游戏使用赛车 BB

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

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

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

数据范围与提示

测试点编号 nn dd mm 其他性质
11 2\le 2 00 4\le 4
22 n\le n
33 5\le 5 00 10\le 10
44 n\le n
55 10\le 10 00 20\le 20
66 8\le 8
77 20\le 20 00 40\le 40 SS 中只包含 cc
88
99 8\le 8 SS 中只包含 xxcc
1010
1111 100\le 100 00 200\le 200 SS 中只包含 cc
1212
1313 8\le 8 SS 中只包含 xxcc
1414
1515 5×103\le 5\times 10^3 00 104\le 10^4
1616 8\le 8 SS 中只包含 xxcc
1717
1818 5×104\le 5\times 10^4 00 105\le 10^5
1919 8\le 8 SS 中只包含 xxcc
2020