Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. ZgukistringZ

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputProfessor GukiZ doesn't accept string as they are. He likes to swap some letters in string to obtain a new one.

GukiZ has strings *a*, *b*, and *c*. He wants to obtain string *k* by swapping some letters in *a*, so that *k* should contain as many non-overlapping substrings equal either to *b* or *c* as possible. Substring of string *x* is a string formed by consecutive segment of characters from *x*. Two substrings of string *x* overlap if there is position *i* in string *x* occupied by both of them.

GukiZ was disappointed because none of his students managed to solve the problem. Can you help them and find one of possible strings *k*?

Input

The first line contains string *a*, the second line contains string *b*, and the third line contains string *c* (1 ≤ |*a*|, |*b*|, |*c*| ≤ 10^{5}, where |*s*| denotes the length of string *s*).

All three strings consist only of lowercase English letters.

It is possible that *b* and *c* coincide.

Output

Find one of possible strings *k*, as described in the problem statement. If there are multiple possible answers, print any of them.

Examples

Input

aaa

a

b

Output

aaa

Input

pozdravstaklenidodiri

niste

dobri

Output

nisteaadddiiklooprrvz

Input

abbbaaccca

ab

aca

Output

ababacabcc

Note

In the third sample, this optimal solutions has three non-overlaping substrings equal to either *b* or *c* on positions 1 – 2 (*ab*), 3 – 4 (*ab*), 5 – 7 (*aca*). In this sample, there exist many other optimal solutions, one of them would be *acaababbcc*.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/22/2021 17:02:38 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|