A glossary must be sorted according to a custom alphabet: a given permutation of the 26 lowercase English letters that defines the collation order (the first letter of the permutation is treated as smallest). Sort the given words in ascending order under this custom alphabet, using the usual lexicographic rule (compare letter by letter using the custom order; if one word is a prefix of another, the shorter word comes first). Duplicate words are allowed.
Input format
Line 1: a 26-character string, a permutation of a-z giving the custom order.
Line 2: an integer n.
The next n tokens (each on its own line) are the words (lowercase letters only).
Output format
The n words, one per line, sorted ascending under the custom alphabet.
Constraints
- 1 ≤ n ≤ 100000
- Each word has length 1..50 and contains only lowercase English letters.