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。