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