Программист Пётр ненавидит сокращения. Его предшественник, напротив, считал, что код должен быть коротким, и активно пользовался сокращениями. К счастью, перед увольнением он составил словарь — список S, состоящий из N полных слов, которые он сокращал.

У Петра есть текст T, состоящий из M слов. Слово из текста T_i является сокращением слова из словаря S_j, если выполняются следующие условия:

• T_i является подпоследовательностью S_j, то есть слово T_i можно получить путём удаления нуля или более символов из слова S_j;
• не существует другого слова в словаре S_k (k ≠ j), для которого слово T_i являлось бы подпоследовательностью.

Помогите Петру избавить текст от сокращений, заменив каждое из них соответствующим полным словом из словаря. Если слово в тексте не является сокращением, оставьте его без изменений.