CF568C.New Language

Living in Byteland was good enough to begin with, but the good king decided to please his subjects and to introduce a national language. He gathered the best of wise men, and sent an expedition to faraway countries, so that they would find out all about how a language should be designed.

After some time, the wise men returned from the trip even wiser. They locked up for six months in the dining room, after which they said to the king: "there are a lot of different languages, but almost all of them have letters that are divided into vowels and consonants; in a word, vowels and consonants must be combined correctly."

There are very many rules, all of them have exceptions, but our language will be deprived of such defects! We propose to introduce a set of formal rules of combining vowels and consonants, and include in the language all the words that satisfy them.

The rules of composing words are:

• The letters are divided into vowels and consonants in some certain way;
• All words have a length of exactly n;
• There are m rules of the form (_pos_1, _t_1, _pos_2, _t_2). Each rule is: if the position _pos_1 has a letter of type _t_1, then the position _pos_2 has a letter of type _t_2.

You are given some string s of length n, it is not necessarily a correct word of the new language. Among all the words of the language that lexicographically not smaller than the string s, find the minimal one in lexicographic order.

在比特兰（Byteland）生活原本已经相当不错，但仁慈的国王决定取悦他的子民，引入一种民族语言。他召集了国内最睿智的贤者，并派出一支远征队前往遥远的国度，以全面考察语言应当如何设计。

过了一段时间，贤者们从旅途归来，变得更加睿智。他们在餐厅里闭关六个月后，向国王禀报：“世界上存在大量不同的语言，但几乎所有的语言都把字母划分为元音字母和辅音字母；在一个单词中，元音与辅音必须以恰当的方式组合。”

尽管存在大量规则，且每条规则都有例外，但我们的语言将彻底摒弃此类缺陷！我们提议引入一套关于元音与辅音组合的形式化规则，并将所有满足这些规则的单词纳入该语言之中。

构词规则如下：

• 字母被以某种确定的方式划分为元音字母和辅音字母；
• 所有单词的长度恰好为 $n$；
• 共有 $m$ 条规则，每条规则形如 $(\text{pos}_1,\,t_1,\,\text{pos}_2,\,t_2)$。其含义为：若位置 $\text{pos}_1$ 上的字母类型为 $t_1$，则位置 $\text{pos}_2$ 上的字母类型必须为 $t_2$。

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

The first line contains a single line consisting of letters 'V' (Vowel) and 'C' (Consonant), determining which letters are vowels and which letters are consonants. The length of this string l is the size of the alphabet of the new language (1 ≤ l ≤ 26). The first l letters of the English alphabet are used as the letters of the alphabet of the new language. If the i-th character of the string equals to 'V', then the corresponding letter is a vowel, otherwise it is a consonant.

The second line contains two integers n, m (1 ≤ n ≤ 200, 0 ≤ m ≤ 4_n_(n - 1)) — the number of letters in a single word and the number of rules, correspondingly.

Next m lines describe m rules of the language in the following format: _pos_1, _t_1, _pos_2, _t_2 (1 ≤ _pos_1, _pos_2 ≤ n, _pos_1 ≠ _pos_2, 'V', 'C' }).

The last line contains string s of length n, consisting of the first l small letters of the English alphabet.

It is guaranteed that no two rules are the same.

第一行包含一个仅由字母 '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$ 行，每行描述一条语言规则，格式为：$pos_1,\ t_1,\ pos_2,\ t_2$（其中 $1 \leq pos_1, pos_2 \leq n$，$pos_1 \neq pos_2$，$t_1, t_2 \in \{ \text{'V'}, \text{'C'} \}$）。

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

保证任意两条规则互不相同。

Print a smallest word of a language that is lexicographically not smaller than s. If such words does not exist (for example, if the language has no words at all), print "-1" (without the quotes).

输出该语言中字典序不小于字符串 s 的最短单词。如果不存在这样的单词（例如，该语言中没有任何单词），则输出 -1（不带引号）。

In the first test word "aa" is not a word of the language, but word "ab" is.

In the second test out of all four possibilities only word "bb" is not a word of a language, but all other words are lexicographically less, so there is no answer.

In the third test, due to the last rule, "abac" doesn't belong to the language ("a" is a vowel, "c" is a consonant). The only word with prefix "ab" that meets the given rules is "abaa". But it is less than "abac", so the answer will be "acaa"

在第一个测试中，单词 “aa” 不属于该语言，但单词 “ab” 属于该语言。

在第二个测试中，在全部四种可能的单词中，仅有单词 “bb” 不属于该语言，而其余所有单词均字典序更小，因此不存在答案。

在第三个测试中，根据最后一条规则，“abac” 不属于该语言（“a” 是元音字母，“c” 是辅音字母）。满足给定规则且以 “ab” 为前缀的唯一单词是 “abaa”。但它比 “abac” 字典序更小，因此答案为 “acaa”。