Professor 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*?
The first line contains string *a*, the second line contains string *b*, and the third line contains string *c* (1 ≤ |*a*|, |*b*|, |*c*| ≤ 10<sup class="upper-index">5</sup>, 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.
from collections import Counter
from collections import defaultdict
import random
import string

def fun1(a,b,c):
    # a = input()
    # b = input()
    # c = input()

    # if len(c) < len(b):b,c = c,b

    counta = {}
    countb = {}
    countc = {}
    for i in "abcdefghijklmnopqrstuvwxyz":
        counta[i]=0
        countb[i]=0
        countc[i]=0

    for i in a:counta[i]+=1
    for i in b:countb[i]+=1
    for i in c:countc[i]+=1

    maxV = 0
    count_of_b = 0
    count_of_c = 0
    opop=0

    tempCounta = {}
    for i,j in counta.items():tempCounta[i]=j
    _ = 0
    while(True):
        temp = len(a)

        for i in countc : 
            if countc[i]!=0: 
                temp = min(temp,tempCounta[i]//countc[i])

        if _ + temp>maxV:
            # print("testing-->",count_of_b,count_of_c)
            count_of_b = _
            count_of_c = temp
            maxV = _ + temp

        weCanProceed = True

        for i in countb:
            if tempCounta[i] < countb[i]: 
                weCanProceed=False
                break
        
        if not weCanProceed: break
        else : 
            for i in countb : tempCounta[i]-=countb[i]
        _+=1

    if count_of_c>0:
        for i in countc:
            counta[i]-=count_of_c*countc[i]

    if count_of_b>0:
        for i in countb:
            counta[i]-=count_of_b*countb[i]

    ans = b*count_of_b + c*count_of_c
    for i in counta:
        ans+=i*counta[i]

    return count_of_b+count_of_c,ans


def get_single(a, b):
    res = 2 ** 32
    for s in b.keys():
        res = min(res, a[s] // b[s])
    return res



def get_count(a, b, c):
        best = 0, get_single(a, c)
        r1 = 0
        while a & b == b:
            r1 += 1
            a = a - b
            r2 = get_single(a, c)
            if r1 + r2 > sum(best):
                best = r1, r2
        return best


def fun2(a,b,c):
        
    aa = Counter(a)
    bb = Counter(b)
    cc = Counter(c)
    
    r = get_count(Counter(a), bb, cc)
    
    res = b * r[0] + c * r[1]
    rest = aa - Counter(res)
    res += ''.join(list(rest.elements()))
    
    return r[0]+r[1],res

if __name__ == '__main__':
    while(True):
        letters = string.ascii_lowercase
        a =  ''.join(random.choice(letters) for i in range(100))
        b =  ''.join(random.choice(letters) for i in range(random.randint(1,20)))
        c =  ''.join(random.choice(letters) for i in range(random.randint(1,20)))
        # a = input()
        # b = input()
        # c = input()
        ans1,s1 = fun1(a,b,c)
        ans2,s2 = fun2(a,b,c)
        if ans1!=ans2:
            print(a)
            print(b)
            print(c)
            print("-->",ans1,s1)
            print("-->",ans2,s2)
            input()

