← 返回题目列表

Codeforces · 551/B

B. 祖古基字符串

中文机器翻译题面 查看原题

GukiZ 教授不接受原样的字符串。他喜欢交换字符串中的一些字母以获得新的字母。

GukiZ 有字符串 a、b 和 c。他想通过交换a中的一些字母来获得字符串k,使得k应该包含尽可能多的等于b或c的不重叠子串。字符串x的子串是由x中的连续字符段组成的字符串。如果字符串 x 中的位置 i 被两个子字符串占据,则字符串 x 的两个子字符串重叠。

GukiZ 很失望,因为他的学生没有一个能够解决这个问题。你能帮助他们找到可能的字符串 k 之一吗?

输入

第一行包含字符串 a,第二行包含字符串 b,第三行包含字符串 c(1 ≤ |a|、|b|、|c| ≤ 105,其中 |s| 表示字符串 s 的长度)。

所有三个字符串均仅包含小写英文字母。

b 和 c 可能重合。

输出

找到可能的字符串 k 之一,如问题陈述中所述。如果有多个可能的答案,请打印其中任何一个。

示例

输入 #1

aaa
a
b

输出 #1

aaa

输入 #2

pozdravstaklenidodiri
niste
dobri

输出 #2

nisteaadddiiklooprrvz

输入 #3

abbbaaccca
ab
aca

输出 #3

ababacabcc

注意

在第三个示例中,此最佳解决方案在位置 1 – 2 (ab)、3 – 4 (ab)、5 – 7 (aca) 上具有三个等于 b 或 c 的不重叠子串。在此示例中,存在许多其他最佳解决方案,其中之一是 acaababbcc。