Morse code

In Morse code, each letter is represented by a sequence of dots and dashes. However, this alone is not enough to transmit text by radio. Morse code also defines the duration of each dot and dash, as well as the different pauses between them.

In this problem, we work with a digitized radio signal encoded on the sending side using Morse code. The signal is a string of + and - characters. Each character tells whether there was sound during the corresponding time tick: + means there was sound, and - means there was no sound. For our purposes, Morse code has five types of elements. They are written into the signal as follows:

For instance, with the standard Latin Morse alphabet, the two words HELLO WORLD are encoded into a signal with 63 elements and 109 ticks:

The pause between the words lasts five ticks. The signal has no pauses or special elements at the beginning or at the end of the text.

The automatic digitization procedure is known to produce errors, which makes the signal hard to decode. The procedure can shorten or lengthen any element by one tick, except that a one-tick element cannot become any shorter.

You are given a dictionary and a digitized signal. Find the minimal number of errors that the digitization procedure could have made, and recover the original text, assuming that:

1. the original text contains only words from the dictionary,
2. the Latin Morse alphabet is used,
3. there are no errors other than those described above.

The first line contains two integers: $M$, the number of words in the dictionary, and $N$, the number of ticks in the signal ($1 \le M, N \le 5\,000$).

The next $M$ lines contain the dictionary words, one per line. Each word is non-empty and contains only capital Latin letters. The total length of all words does not exceed $5\,000$.

The remaining lines contain the digitized signal, a sequence of + and - characters with total length $N$. The sequence may be split arbitrarily into several non-empty lines. The signal contains at least one +.

If the signal could not have been produced under the given conditions, print a single number -1.

Otherwise, print a single integer $K \ge 0$ on the first line, the minimum possible number of errors. On the second line, print the original text that produces the signal with this number of errors. The words of the text are separated by exactly one space.

If several texts produce the signal with the minimal number of errors, print the lexicographically smallest one. A space is smaller than any letter.

The first sample is exactly the example from the problem statement, with no errors. The second sample has the same text, but twelve elements are cut or extended by one tick. The third sample has an 11-tick pause, which cannot be produced. The longest element is the 5-tick pause between words, which can become 6 ticks long because of an error. The fourth sample has five dots, which can form the letters E, I, S, and H in various combinations. However, the only word in the dictionary, HELLO, cannot be built from these letters alone.