Петя очень любит хоккей. Однажды, глядя хоккейный матч, он заснул. Ему приснился сон, в котором ему поручили переделать название хоккейной команды. Так, Пете дали исходное название команды w и набор запрещенных подстрок s₁, s₂, ..., s_n. Все эти строки состоят из больших и маленьких букв латинского алфавита. Строка w имеет длину |w|, ее символы пронумерованы от 1 до |w|.

Сначала Петя должен найти в строке w все вхождения запрещенных подстрок, причем регистр букв при поиске вхождений не учитывается. То есть строки «aBC» и «ABc» считаются эквивалентными.

После этого Петя должен произвести замену всех букв, покрывающихся вхождениями. Более формально: букву в позиции i необходимо заменить на любую другую, если для позиции i в строке w найдется такая пара индексов l, r (1 ≤ l ≤ i ≤ r ≤ |w|), что подстрока w[l ... r] является элементом набора s₁, s₂, ..., s_n, не учитывая регистр букв при сравнении строк. При замене регистр буквы должен сохраниться. Пете не разрешается заменять буквы, которые не покрывает ни одна запрещенная подстрока.

Буква letter (как большая, так и маленькая) у хоккеистов считается счастливой. Поэтому Петя должен так произвести замены, чтобы эта буква встречалась в итоговой строке как можно больше раз. Помогите ему — найдите лексикографически минимальную новую строку с максимальным возможным количеством счастливых букв.

Обратите внимание, что процесс замен не повторяется, а происходит лишь один раз. То есть если после Петиных замен в строке появились новые вхождения плохих подстрок, Петя не обращает на них внимание.