住在拜特兰一开始就已经足够好了,但善良的国王决定取悦他的臣民并引入一种国家语言。他召集了最优秀的智者,派出一支探险队前往遥远的国家,以便他们了解如何设计语言的一切。
过了一段时间,智者们旅行回来后更加聪明了。他们在餐厅里关了六个月,之后对国王说:“语言有很多种,但几乎所有的字母都有分元音和辅音的字母;总之,元音和辅音必须正确组合。”
规则非常多,都有例外,但我们的语言将被剥夺这样的缺陷!我们建议引入一套元音和辅音组合的正式规则,并将所有满足这些规则的单词包含在语言中。
构词规则为:
- 字母以某种方式分为元音和辅音;
- 所有单词的长度恰好为 n;
- 有 m 个形式为 (pos1, t1, pos2, t2) 的规则。每条规则是:如果位置 pos1 有一个类型为 t1 的字母,那么位置 pos2 有一个类型为 t2 的字母。
给你一些长度为n的字符串s,它不一定是新语言的正确单词。在该语言的所有字典顺序不小于字符串 s 的单词中,找到字典顺序最小的单词。
输入
第一行包含由字母“V”(元音)和“C”(辅音)组成的单行,确定哪些字母是元音,哪些字母是辅音。该字符串 l 的长度是新语言字母表的大小 (1 ≤ l ≤ 26)。英语字母表的前l个字母被用作新语言的字母表中的字母。如果字符串的第 i 个字符等于“V”,则对应的字母是元音,否则是辅音。
第二行包含两个整数 n, m (1 ≤ n ≤ 200, 0 ≤ m ≤ 4n(n - 1)) — 单个单词中的字母数和相应的规则数。
接下来的 m 行按以下格式描述该语言的 m 个规则:pos1, t1, pos2, t2 (1 ≤ pos1, pos2 ≤ n, pos1 ≠ pos2, $$t_{1}, t_{2} \in \{$$ 'V', 'C' })。
最后一行包含长度为n的字符串s,由英文字母表的前l个小字母组成。
保证没有两条规则是相同的。
输出
打印字典顺序不小于 s 的语言的最小单词。如果此类单词不存在(例如,如果该语言根本没有单词),则打印“-1”(不带引号)。
示例
输入 #1
VC 2 1 1 V 2 C aa
输出 #1
ab
输入 #2
VC 2 1 1 C 2 V bb
输出 #2
-1
输入 #3
VCC 4 3 1 C 2 V 2 C 3 V 3 V 4 V abac
输出 #3
acaa
注意
在第一个测试中,单词“aa”不是该语言的单词,但单词“ab”是。
在第二个测试中,所有四种可能性中,只有单词“bb”不是某种语言的单词,但所有其他单词按字典顺序排列较少,因此没有答案。
在第三次测试中,由于最后一条规则,“abac”不属于该语言(“a”是元音,“c”是辅音)。唯一符合给定规则的前缀为“ab”的单词是“abaa”。但它小于“abac”,所以答案将是“acaa”