<PREV Problem:
NEXT>
Solved by 37 users: defrager, zloy_mipt, Jacob, ilyakor, Kuznetsov_S, WsemirZ, Ravent, UdH-WiNGeR, JohnJones_001, regal, MIKseR, dan, DmitrievVladimir814, gafrustam814, M_A_X, risinka_814, yura814, WinZib, Robin_Hood, coolzero814, Fat, abortmozga.ru, Romka, topspin, RAVEman, fetetriste, vi002, plantator, vitar, Dest, karakurt25, checkil, oleg.dudrov, ripatti, mikelan, adamant, dzhavaharnal.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Archiver

Time limit = 1 second(s)

An archiver is a program that compresses data removing redundant fragments. The problem is to implement basic archiver for text files. The repeated fragments can be replaced with letters that are not used in the source text.

Since the replacements might have common subsequences, the commpression ratio depends on the replacements being used.

The problem is to find the most compact compressed form of the source text.

Input The first line contains the number of replacement fragments R (1 ≤ R ≤ 400). The second line contain the number of lines in the source text (1 ≤ N ≤ 1000). Then follow R pair of lines in which the first is a source fragment and the second is a replacement. The last N lines contain the source text. All the lines do not exceed 255 characters.

Output Compressed text

Input#1
3 2
абв
A
где
B
бвэюягд
C
абвэюягде
гдеабв
Output#1
аCе
BA

Author:
Peculiarities of national computer science problems
2000

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 54.161.108.158