Valid Permutations

You are given a string S and a dictionary of valid words. Your task is to generate all unique permutations of the string S and then output those permutations that are present in the dictionary. The answer should include the valid permutations sorted in lexicographical order. If no valid permutation exists, print an empty line.

Note: Multiple occurrences of the same dictionary word should be considered as one. All comparisons are case-sensitive.

The permutations must be generated from the characters of the string S using every character exactly once. The dictionary is provided as a list of words.

The answer must be computed using input from standard input (stdin) and printed to standard output (stdout).

inputFormat

The first line of input contains the string S.
The second line contains an integer N, representing the number of words in the dictionary.
The third line contains N words separated by spaces, which form the dictionary.

outputFormat

Output a single line that contains the valid permutations (that appear in the dictionary), sorted in lexicographical order and separated by a single space. If no valid permutation exists, print an empty line.

## sample

cba
4
abc acb bac cab

abc acb bac cab

</p>