当前没有测试数据。

题目描述

There is a hidden string of length n composed of the first m lowercase English letters. For any two different English letters, we will tell you a subsequence of the hidden string constructed by removing all other letters from the hidden string.

For example, if the hidden string is "apple" and the chosen letters are 'e' and 'p', the resulting subsequence would be "ppe"; if the chosen letters are 'a' and 'x', the resulting subsequence would be "a".

Now, please recover the hidden string. Output -1 if there are no possible hidden string. Output any one if there are multiple possible hidden strings.

输入格式

The first line contains two integers n and m.

Following are $m \cdot (m-1)/2$ groups of two lines. The first line in each group contains a two-letter string composed of c1, c2, and an integer LEN. The second line contains a string composed of letters c1, c2 with length LEN, indicates the resulting subsequence by removing all other letters except c1 and c2 from the hidden string.

• $1 \le n \le 10^4$

• $2 \le m \le 10$

• $0 \le LEN \le n$

• all unordered pairs of letters in first m small English letters will occur exactly once.

输出格式

If there is at least one possible hidden string, please output any. Otherwise, output -1.

样例

样例输入 1

3 3
ab 2
ab
bc 2
bc
ca 2
ac

样例输出 1

abc

样例解释 1

First group tells us that there is one 'a' and one 'b' where 'a' is before 'b', the second group tells us there is one 'b' and one 'c' where 'b' is before 'c'. So the only possible answer is "abc" which satisfies the last group as well.

样例输入 2

3 3
cb 3
bbc
ca 2
ac
ab 3
abb3 3
cb 3
bbc
ca 2
ac
ab 3
abb

样例输出 2

-1

样例输入 3

4 3
ac 4
cccc
ba 0

cb 4
cccc

样例输出 3

cccc