tetriss

În vacanţa de iarnă, elevii au descoperit pe Internet un nou joc ce se desfăşoară pe o suprafaţă dreptunghiulară de dimensiune $n \times m$ ( $n$ linii şi $m$ coloane). Jocul utilizează $n$ piese şi un set de $p$ machete. Piesele sunt formate din litere mici ale alfabetului englez, dispuse pe orizontală şi pot avea lungimi diferite (lungimea fiecărei piese nu depăşeşte valoarea lui $m$). Fiecare piesă va fi completată la sfârşit cu spaţii, astfel încât lungimea ei să coincidă cu dimensiunea $m$ a suprafeţei de joc.
Fiecare machetă are rolul de a transforma un şir de caractere (denumit şir de intrare) în alt şir de caractere (denumit şir de ieşire).

De exemplu, macheta ab-de aplicată pieselor:

aycd
bxcab

transformă şirul ab (şir de intrare) în şirul de (şir de ieşire)
şi piesele se modifică astfel:

dycd
excab 

Dacă într-o machetă, şirul de ieşire este mai scurt decât şirul de intrare, atunci şirul de ieşire se va completa cu spaţii la sfârşit, astfel încât să aibă aceeaşi lungime cu şirul de intrare.
Regulile jocului sunt următoarele:

• piesele se deplasează de sus în jos, pe suprafaţa necompletată iniţial şi se aşează unele peste altele;
• după depunerea unei piese peste piesa anterioară, se aplică pe fiecare coloană, începând de la coloana $1$, dacă este posibil, de sus în jos, setul de machete, în ordinea în care acestea sunt date (de exemplu pe o coloană oarecare se aplică, dacă este posibil, macheta $1$, apoi macheta $2$, $\dots$ încheind cu macheta $p$). O machetă se aplică pe o coloană până când se ajunge la marginea de jos a suprafeţei de joc, moment în care se trece la urmatoarea machetă (cea care îi urmează în setul specificat de machete).

După ce au fost plasate toate piesele pe suprafaţa de joc şi s-au aplicat machetele, conform regulilor anterioare, aceasta se rearanjează astfel:

• pentru fiecare coloană, privită de sus în jos (ce reprezintă un şir de caractere), se vor elimina spaţiile care se repetă (cele de la extremităţi se elimină toate şi pentru cele care se repetă în interior, din mai multe spaţii consecutive va rămâne unul singur).

Dintre şirurile obţinute, se alege şirul de lungime maximă (dacă sunt mai multe astfel de şiruri se va reţine şirul cel mai apropiat de marginea din stânga a suprafeţei de joc) şi acesta va fi transformat după următoarea regulă: se rearanjează literele lui în ordine alfabetică, păstrând lungimea şi poziţia cuvintelor (se consideră cuvânt o succesiune de litere cuprinse între două spaţii, cu excepţia primului cuvânt care are spaţiu doar după el şi a ultimului cuvânt care are spaţiu doar în faţa lui).
De exemplu, şirul ana are mere se va transforma în şirul aaa eee mnrr.

Cerinţă:

Date fiind dimensiunile suprafeţei de joc, machetele şi piesele ce participă la joc, să se afişeze şirul obţinut în urma transformărilor cerute în enunţul problemei.

Date de intrare:

Fişierul de intrare tetriss.in conţine pe prima linie trei numere naturale $n$, $m$ (dimensiunile suprafeţei de joc) şi $p$ (numărul de machete), separate prin spaţiu între ele, pe următoarele $p$ linii conţine machetele şi pe următoarele $n$ linii conţine piesele de joc.

Date de ieşire:

Fişierul de ieşire tetriss.out va conţine o singură linie ce conţine şirul obţinut în urma transformărilor cerute în enunţul problemei.

Restricţii şi precizări:

• $1 \leq n \leq 200$, $1 \leq m \leq 100$, $1 \leq p \leq 100$
• pentru fiecare machetă, $0 <$ dimensiunea şirului de intrare $\leq n$
• pentru fiecare machetă, $0 <$ dimensiunea şirului de ieşire $\leq$ dimensiunea şirului de intrare

Exemplu

tetriss.in

4 6 8
bc-fg
ef-e
cd-d
eb-c
fd-cd
gdf-fg
fg-a
mc-m
cddfgh
bcdd
edfghd
aemcb

tetriss.out

3

Explicație