← 返回题目列表

Codeforces · 568/C

C. 新语言

中文机器翻译题面 查看原题

住在拜特兰一开始就已经足够好了,但善良的国王决定取悦他的臣民并引入一种国家语言。他召集了最优秀的智者,派出一支探险队前往遥远的国家,以便他们了解如何设计语言的一切。

过了一段时间,智者们旅行回来后更加聪明了。他们在餐厅里关了六个月,之后对国王说:“语言有很多种,但几乎所有的字母都有分元音和辅音的字母;总之,元音和辅音必须正确组合。”

规则非常多,都有例外,但我们的语言将被剥夺这样的缺陷!我们建议引入一套元音和辅音组合的正式规则,并将所有满足这些规则的单词包含在语言中。

构词规则为:

- 字母以某种方式分为元音和辅音;
- 所有单词的长度恰好为 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”