Напишите программу, которая будет заменять в тексте все вхождения строки s на строку t. Гарантируется, что никакие два вхождения шаблона s не пересекаются друг с другом.

В первой строке дан текст —– это строка из строчных букв английского алфавита, длина которой не превышает 10⁶.

Во второй строке записан шаблон s, вхождения которого будут заменены.
В третьей строке дана строка t, которая будет заменять вхождения.

Обе строки s и t состоят из строчных букв английского алфавита, длина каждой строки не превосходит 10⁵. Размер итоговой строки не превосходит 2⋅ 10⁶.

В единственной строке выведите результат всех замен — текст, в котором все вхождения s заменены на t.