Communication Line

This problem requires you to write a program which does three tasks which might facilitate the use of a communication line. The first task is that of translating from one set of codes to another. The second task is to compress 80-character lines to a smaller size by compressing blanks. The final task is that of grouping these “compressed” lines into larger lines. The three tasks are to be performed in sequence.

To perform the translation, you will be first given two strings $S$ and $T$. The $i$’th character in $S$ is to be translated to the $i$’th character in $T$. Any character not appearing in $S$ should not be translated.

Then you will read a sequence of lines of input. For each line $L$, you will do the following:

• For each character of $L$ appearing in $S$, replace it with its corresponding character in $T$.

• Then for each consecutive sequence of $4$ or more blanks in $L$, replace the sequence with & followed by exactly two digits indicating the number of blanks that were replaced (use a leading 0 if necessary).

Finally, after translation and compression of all lines has taken place these lines should be concatenated to form fewer lines in the following way.

For some given value $N$, concatenate as many of the first few lines (retaining their order) as possible so that the concatenated string (including any blanks) has length at most $N$. Output this new concatenated line and repeat with the remaining lines until no line remains.

Input

The first line of input begins with two numbers $N$ ($1 \le N < 1000$) and $M$ ($1 \le M \le 20$) followed by two strings $S$ and $T$ of length $M$ each. $S$ is composed of distinct characters. This means the $i$th character in $S$ should be translated to the $i$th character in $T$. Both $S$ and $T$ only contain letters, digits, and the following punctuation characters:

Then a number of lines follow, each containing exactly $80$ characters. Each line consists only of letters, digits, punctuation characters, and spaces. A line may have leading or trailing spaces. The final line begins with **** followed by $76$ spaces and no other line is exactly like this. There will be at most $100$ lines apart from the first and last line.

Output

Output the final lines obtained by concatenating the results of translating and compressing each of these lines according to the concatenation procedure described above.

40 3 ABC $.$
         ABC                                                                    
  ABCD                                                                          
 A B  D   A    BCB      CC                                                      
A B                                                                             
 A B  D   A    BCB      CC                                                      
****                                                                            

&09$.$&68  $.$D&74
 $ .  D   $&04.$.&06$$&54$ .&77
 $ .  D   $&04.$.&06$$&54