The heavy rain pounded on the dormitory windows. It had been raining for two days straight in Cluj Napoca. Everything was grey and soaking wet. Morale was down. The Finalists decided to gather in the dormitory common room and play a game of Scrabble with Comisia. Of course, Comisia was feeling generous so they offered to take the winner out for a slice of pizza. The game was on!
You are given a list of words and a sequence of letters. Display the words (in alphabetical order) that can be formed by picking a subgroup of letters from the initial word and rearranging them.
InputThe sequence of letters is on the first line of the file. N, the number of words is on the next line.
The next N lines will be occupied by the words that must be found in the dictionary.
OutputIn the output file you must display the words that can be obtained, one on every line, in alphabetical order.
1 ≤ n ≤ 70 000
1 ≤ |sequence|, |word[i]| ≤ 30
By |x| we mean the length of string x.
a < aa
The letters in the sequence will not be separated by spaces.