You are given a dictionary of r roots and one sentence of space-separated words. For every word in the sentence, if one or more roots are a prefix of that word, replace the word by the shortest such root; if two roots of equal shortest length both match, they must be identical, so the replacement is unique. If no root is a prefix of the word, keep the word unchanged.
Output the resulting sentence with words separated by single spaces, in the original order. All roots and words consist of lowercase English letters only.
Input format
Line 1: an integer r.
Line 2: r space-separated roots.
Line 3: the sentence, one or more space-separated words.
Output format
A single line: the transformed sentence.
Constraints
- 1 <= r <= 100000
- The sentence has 1..100000 words.
- Each root/word has length 1..30, lowercase English letters.