The spacebar does not work on Vasya's keyboard. Therefore, he is now typing all the texts together. Write a program that will split the text typed by Vasya into words from the given dictionary.
Input
First, the input of the program receives the text entered by Vasya – one line of no more than 100 Latin lowercase letters. The next input line specifies the value N – the number of words in the dictionary (N – is a natural number not exceeding 2000). The next N lines contain words from the – one word per line, each word contains no more than 20 Latin lowercase letters. The words are written in alphabetical order.
Imprint
Print Vasya's text with spaces between words (a space after the last word is acceptable). If there are several options for splitting the string into words, print any of them. It is guaranteed that at least one way to split a string into dictionary words exists.
Examples
| # |
Input |
Output |
| 1 |
whatcanido
6
a
an
can
do
i
what |
what can i do |