Prefix Replacement

Problem statement

We can append some other words to a prefix to frame new words. For example, the prefix re can be followed by words start and cap to form words restart or recap.

Given a list consisting of multiple prefixes and a sentence, replace all the words in the sentence with the prefix forming it. If a word can be replaced by more than one prefix, replace it with the prefix that has the shortest length.

Return the modified sentence after the replacement.

Example 1

Sample Input