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  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.

* 

* 

* 

* 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.

3 3
ab 2
ab
bc 2
bc
ca 2
ac

abc

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.

3 3
cb 3
bbc
ca 2
ac
ab 3
abb

-1

4 3
ac 4
cccc
ba 0

cb 4
cccc

cccc