C. 新语言

单次测试时限：2 秒
内存限制：256 兆字节

在比特国（Byteland）的生活原本已经足够美好，但贤明的国王决定取悦他的臣民，引入一门国家语言。他召集了最优秀的智者，并派遣了一支远征队前往遥远的国度，让他们彻底弄清楚一门语言应当如何设计。

一段时间后，智者们带着更丰富的智慧返回。他们在餐厅里闭关了六个月，然后对国王说：“世界上有很多不同的语言，但几乎所有的语言中，字母都被分为元音和辅音；在一个单词中，元音和辅音必须正确组合。”

规则非常之多，且所有规则都有例外，但我们的语言将摆脱这些缺陷！我们建议引入一套形式化的元音与辅音组合规则，并将所有满足这些规则的单词纳入本语言。

单词的构成规则如下：

1. 字母以某种确定的方式被划分为元音和辅音；
2. 所有单词的长度恰好为 $n$；
3. 有 $m$ 条形式为 $(pos1, t1, pos2, t2)$ 的规则。每条规则的含义是：如果位置 $pos1$ 上的字母类型为 $t1$，那么位置 $pos2$ 上的字母类型必须为 $t2$。

给定一个长度为 $n$ 的字符串 $s$，它不一定是该语言中的合法单词。在所有字典序不小于字符串 $s$ 的语言单词中，找出字典序最小的那一个。

---

输入
第一行包含一个由字母 'V'（元音）和 'C'（辅音）组成的字符串，用于确定哪些字母是元音、哪些是辅音。该字符串的长度 $l$ 是新语言的字母表大小（$1 \le l \le 26$）。新语言使用英文字母表中的前 $l$ 个小写字母作为字母表。若该字符串的第 $i$ 个字符为 'V'，则对应的第 $i$ 个字母是元音，否则为辅音。

第二行包含两个整数 $n$ 和 $m$（$1 \le n \le 200$，$0 \le m \le 4n(n-1)$）—— 单词长度和规则数量。

接下来 $m$ 行，每行描述一条规则，格式为：$pos1, t1, pos2, t2$（$1 \le pos1, pos2 \le n$，$pos1 \neq pos2$，$t1, t2 \in \{\text{'V'}, \text{'C'}\}$）。

最后一行包含一个长度为 $n$ 的字符串 $s$，由前 $l$ 个小写英文字母组成。

输入保证没有两条规则完全相同。

---

输出
输出一个语言中字典序不小于 $s$ 的最小单词。如果不存在这样的单词（例如，语言本身没有任何单词），则输出 -1。

---

样例

样例 1
输入

VC
2 1
1 V 2 C
aa

输出

ab

样例 2
输入

VC
2 1
1 C 2 V
bb

输出

-1

样例 3
输入

VCC
4 3
1 C 2 V
2 C 3 V
3 V 4 V
abac

输出

acaa

---

说明
在第一个样例中，单词 "aa" 不是该语言的单词，但单词 "ab" 是。

在第二个样例中，四种可能的单词中只有 "bb" 不是该语言的单词，但所有其他单词的字典序都小于 "bb"，因此没有答案。

在第三个样例中，由于最后一条规则，"abac" 不属于该语言（'a' 是元音，'c' 是辅音）。唯一以 "ab" 为前缀且满足给定规则的单词是 "abaa"，但它小于 "abac"，因此答案是 "acaa"。