Shortest Prefix Replacement

You are given roots, a list of lowercase strings, and sentence, a string of lowercase words separated by single spaces.

Replace every word of sentence that has some element of roots as a prefix with that root. When several roots are prefixes of the same word, use the shortest one. Words with no root as a prefix are left unchanged.

Return the resulting sentence, words separated by single spaces.

Examples

Example 1

Input: roots = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
Explanation: "cattle" starts with "cat", "rattled" starts with "rat", and "battery" starts with "bat". "the", "was" and "by" have no root as a prefix.

Example 2

Input: roots = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"
Explanation: Every word starts with one of the single-letter roots, so each collapses to that letter.