CF568C New Language

在 Byteland 生活本来就不错，但仁慈的国王决定取悦他的子民并引入国家语言。他召集了最睿智的人，派出远征队去遥远的国家，去了解如何设计一种语言。 一段时间后，智者们变得更加睿智地归来。他们在餐厅里闭关六个月，然后对国王说：“有许多不同的语言，但几乎所有语言的字母都分为元音和辅音；在一个单词中，元音和辅音必须正确地组合。” 有很多规则，每个规则都有例外，但我们的语言将消除此类缺陷！我们建议引入一组形式化的元音和辅音组合规则，并将所有满足这些规则的单词包含在语言中。 构成单词的规则如下： - 字母按某种方式分为元音和辅音； - 所有单词的长度恰好为 $n$； - 共有 $m$ 条规则，每条规则形式为 $(pos_{1}, t_{1}, pos_{2}, t_{2})$。每条规则的意思是：如果第 $pos_{1}$ 个位置是类型 $t_{1}$ 的字母，那么第 $pos_{2}$ 个位置必须是类型 $t_{2}$ 的字母。 给定一个长度为 $n$ 的字符串 $s$，它未必是一种新语言的合法单词。在所有字典序不小于字符串 $s$ 的新语言单词中，找到字典序最小的一个。

第一行包含仅由 'V'（元音）和 'C'（辅音）组成的字符串，表示哪些字母是元音、哪些是辅音。该字符串长度 $l$，即新语言字母表的大小（$1 \leq l \leq 26$）。新语言使用英文小写前 $l$ 个字母作为字母表。如果第 $i$ 个字符是 'V'，则对应的字母是元音，否则是辅音。 第二行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 200$，$0 \leq m \leq 4n(n-1)$），分别表示单词长度和规则数量。 接下来 $m$ 行描述这 $m$ 条规则，格式为：$pos_{1}, t_{1}, pos_{2}, t_{2}$（$1 \leq pos_{1}, pos_{2} \leq n$，$pos_{1} \ne pos_{2}$，$t_1, t_2 \in \{V, C\}$）。 最后一行为长度为 $n$ 的字符串 $s$，仅由新语言字母表的前 $l$ 个英文小写字母组成。 保证没有重复规则。

输出一个字典序不小于 $s$ 的、满足所有规则的、字典序最小的新语言单词。如果不存在这样的单词（比如，这种语言没有任何合法单词），输出 "-1"（不含引号）。

第一个样例中，"aa" 不是该语言的合法单词，但 "ab" 是。 第二个样例中，所有四种可能中，只有 "bb" 不是该语言的单词，但其他单词字典序都比目标串小，所以输出 "-1"。 第三个样例，由于最后一条规则，"abac" 不是该语言的单词（"a" 是元音，"c" 是辅音）。以 "ab" 为前缀且满足规则的唯一单词是 "abaa"，但其字典序比 "abac" 小，所以答案是 "acaa"。 由 ChatGPT 5 翻译