textmare

Se dă un șir de caractere alcătuit din N litere mici din alfabetul latin, ce reprezinta o frază; între cuvinte nu apar spații de separare. De asemenea se dă un vocabular, format din M cuvinte care nu sunt neapărat diferite și nu apar într-o ordine prestabilită.

Cerință

Despărțiți fraza într-un număr minim de cuvinte; toate aceste cuvinte trebuie să existe în vocabularul dat.

Date de intrare

Fișier de intrare: textmare.in

• pe prima linie apare fraza care trebuie despărțită în cuvinte;
• următoarea linie conține numărul de cuvinte din vocabular;
• următoarele linii conțin câte un cuvânt din vocabular;

Date de ieșire

Fișier de ieșire: textmare.out
Fișierul este format din fraza despărțită în cuvinte. Între oricare două cuvinte consecutive va apărea exact câte un blanc. Fișierul se va termina cu o linie goală. Dacă nu există soluție, în fisierul de ieșire se va scrie doar cifra 0;

Restricții și precizări:

• Fie S numărul total de caractere din dicționar.
• Pentru 25 de puncte: 1 ≤ N, M ≤ 1 000 și fiecare cuvânt din vocabular are cel mult 16 caractere.
• Pentru încă 35 de puncte: 1 ≤ N, M ≤ 32 000 și fiecare cuvânt din vocabular are cel mult 16 caractere.
• Pentru încă 40 de puncte: 1 ≤ N ≤ 100 000, 1 ≤ M ≤ 500 000, 1 ≤ S ≤ 500 000.
• Dacă există mai multe soluții, la ieșire va fi produsă una singură;
• Într-o frază un singur cuvânt din vocabular poate să apară de mai multe ori.

Exemplu

textmare.in

acestaesteuntext
8
text
acesta
acest
a
care
este
un
simplu

textmare.out

acesta este un text