#K74012. Word Pattern Matching

    ID: 34103 Type: Default 1000ms 256MiB

Word Pattern Matching

Word Pattern Matching

You are given a string pattern and a list of words. A word is said to match the pattern if there exists a bijection between a letter in the pattern and a letter in the word, such that the pattern can be transformed into the word by replacing each occurrence of a letter with the corresponding letter from the word.

More formally, for a word w and a pattern p both of the same length, the matching condition is defined as:

\(\forall i, j \in [1, n],\; p_i = p_j \iff w_i = w_j\)

Given a list of words and a pattern, your task is to output all words that match the pattern.

inputFormat

The input is read from stdin and consists of:

  1. A line containing the pattern string.
  2. A line containing an integer n, the number of words.
  3. n lines each containing a single word.

Both the pattern and the words consist only of lowercase letters.

outputFormat

Output to stdout a single line containing all the words that match the given pattern separated by a single space. If no word matches the pattern, output an empty line.

## sample
abb
6
abc
deq
mee
aqq
dkd
ccc
mee aqq

</p>