Presledki

V besedilu (zaporedju besed) smo izgubili vse presledke. Poznamo pa slovar besed, s pomočjo katerega želimo rekonstruirati originalno besedilo s presledki.

Besedilo je podano kot niz $S$ sestavljen iz velikih črk angleške abecede. Slovar besed je podan kot seznam $K$ nizov $B_i$, ki po dolžini ne presegajo 20 črk. Rekonstrukcija bo zagotov obstajala, morda jih bo obstajalo celo več. Vsako rekonstrukcijo lahko definiramo s seznamom dolžin besed. V primeru več rekonstrukcij želimo izbrati tako, ki bo imela leksikografsko najmanjši seznam dolžin besed (na začetku želimo torej čim krajše besede).

Omejitve podatkov:

• $1 \leq |S| \leq 100\,000$
• $1 \leq K \leq 10\,000$
• $1 \leq |B_i| \leq 20$

Vhodni in izhodni podatki:

V prvi vrstici je podan niz $S$ brez presledkov. V drugi vrstici je podana velikost slovarja $K$. Sledečih $K$ vrstic pa vsebuje besede iz slovarja $B_i$.

Izpišite rekonstrukcijo besedila s presledki.

Primer vhoda:

ABCAACAAAAAAA
5
AB
AAA
CA
ABC
AA

Pravilen izhod:

ABC AA CA AA AA AA