After observing the results of Spy Syndrome, Yash realised the errors of his ways. He now believes that a super spy such as Siddhant can’t use a cipher as basic and ancient as Caesar cipher. After many weeks of observation of Siddhant’s sentences, Yash determined a new cipher technique.
- Convert all letters of the sentence to lowercase.
- Reverse each of the words of the sentence individually.
- Remove all the spaces in the sentence.
For example, when this cipher is applied to the sentence
Kira is childish and he hates losing
the resulting string is
Now Yash is given some ciphered string and a list of words. Help him to find out any original sentence composed using only words from the list. Note, that any of the given words could be used in the sentence multiple times.
Hash 后加 map 里，暴力匹配即可，
不需要用 Trie 树