Профессор GukiZ не всегда принимает строки такими, какие они есть. Получая строку, он иногда переставляет местами некоторые буквы в строке, таким образом, чтобы получалась новая строка.
У GukiZ есть строки a, b, и c. Он хочет получить строку k, поменяв местами некоторые буквы в a, так, чтобы в k содержалось как можно больше непересекающихся подстрок, равных либо b, либо c. Подстрока строки x — это строка, сформированная непрерывным подотрезком символов из x. Две подстроки строки x пересекаются, если есть такая позиция i в строке x, которая принадлежит обеим этим подстрокам.
GukiZ был разочарован, когда ни один из его учеников не смог решить эту задачу. Сможете помочь им и найти одну из возможных строк k?
Выходные данные
Найдите одну из возможных строк k, отвечающую описанию, данному в условии задачи. Если есть несколько возможных ответов, выведите любой.
Примечание
В третьем примере у данного оптимального решения есть три непересекающиеся подстроки, равные либо b, либо c в позициях 1 – 2 (ab), 3 – 4 (ab), 5 – 7 (aca). В этом примере существует много других оптимальных решений, одно из них: acaababbcc.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
aaa
a
b
|
aaa
|
|
2
|
pozdravstaklenidodiri
niste
dobri
|
nisteaadddiiklooprrvz
|
|
3
|
abbbaaccca
ab
aca
|
ababacabcc
|