In English, a root can be followed by some other word to form another longer word — a successor. Given a dictionary of roots and a sentence, replace all successors in the sentence with the shortest matching root.

Return the modified sentence.

Example 1:

Input:
cat bat rat
the cattle was rattled by the battery
Output: the cat was rat by the bat

Example 2:

Input:
a b c
aadsfasf absbs bbab cadsfafs
Output: a a b c

Constraints:

• 1 ≤ dictionary.length ≤ 1000
• 1 ≤ dictionary[i].length ≤ 100
• 1 ≤ sentence.length ≤ 10⁶

Input format: First line: space-separated dictionary roots. Second line: the sentence.

Output format: Modified sentence.