GCTAA Logo

Governor's Career & Technical Academy Arlington

Finding Anagrams


Finding Anagrams

Write a program that outputs all sentences that are anagrams of the input sentence using only words from the supplied dictionary. For sentence to be a valid anagram, it must use all of the letters in the input sentence exactly once.

Input

The first line is a sentence. The remaining lines are the words of a dictionary, entered one word per line. Other than the spaces appearing between words of the first line, the input will consist only of lower-case alphabetic symbols ('a' - 'z').

Output

You must print all combinations of words from the dictionary that are anagrams of the first sentence. For example, Raining Mad Fangs is an anagram of Finding Anagrams. For each combination of words, you don't have to print them out in every possible order. You may may only use each word from the dictionary once per anagram. However, the same word may appear multiple times in the dictionary.

If no anagrams are possible from the input sentence, your program should print No anagrams for this sentence.

Example

An example input file could contain:

finding anagrams
admiring
afar
drama
fan
fans
fangs
mad
minding
nag
race
rain
quick
raining
signing
soup

Given this input above, the program would print out:

admiring fans nag
drama fan signing
fangs mad raining

Test Data