from time import *
import re
import random
 
 
def f1(a,b):
    m=b.split("^")
    s=''
    for i in range(len(a)):
        s+=m[i]
        s+=a[i]
    s+=m[-1]
    return s
 
def f2(a,b):
    m=b.split("^")
    s=[]
    for i in range(len(a)):
        s.append(m[i])
        s.append(a[i])
    s.append(m[-1])
    return "".join(s)
 
def f3(a,b):
    m=b.split("^")
    return "".join(m[i]+a[i] for i in range(len(a)))+m[-1]
 
r=re.compile("\^")
def f4(a,b):
    s=""
    i=0
    for t,m in enumerate(r.finditer(b)):
        s+=b[i:m.start()]+a[t]
        i=m.end()
    s+=b[i:]
    return s
 
def f5(a,b):
    s=b
    for x in a:
        s=s.replace("^",x,1)
    return s
 
alpha = 'abcdefghijklmnopqrstuvwxyz'
number = '0123456789'
def g(n):
    data=[]
    for c in range(n):
        w=random.randint(12,30)
        a=["".join(random.choices(alpha,k=random.randint(5,20))) for x in range(w)]
        b="^".join("".join(random.choices(number,k=random.randint(5,20))) for x in range(w+1))
        data+=[[a,b]]
    return data
 
def test(*ff):
    a=["aa","bb","cc"]
    b="111^222^3333^44444"
    data=g(10000)
    print(f"example data:\n{data[0][0]}\n{data[0][1]}")
    for f in ff:
        assert f(a,b)=="111aa222bb3333cc44444"
        print(f"{f.__name__}: {f(a,b)}")
        t1=time()
        c=[f(*x) for x in data]    
        t2=time()
        print(f"time: {(t2-t1)*1e3:.3f}")
 
test(f1,f2,f3,f4,f5)
 
 

ZnJvbSB0aW1lIGltcG9ydCAqCmltcG9ydCByZQppbXBvcnQgcmFuZG9tCgoKZGVmIGYxKGEsYik6CiAgICBtPWIuc3BsaXQoIl4iKQogICAgcz0nJwogICAgZm9yIGkgaW4gcmFuZ2UobGVuKGEpKToKICAgICAgICBzKz1tW2ldCiAgICAgICAgcys9YVtpXQogICAgcys9bVstMV0KICAgIHJldHVybiBzCgpkZWYgZjIoYSxiKToKICAgIG09Yi5zcGxpdCgiXiIpCiAgICBzPVtdCiAgICBmb3IgaSBpbiByYW5nZShsZW4oYSkpOgogICAgICAgIHMuYXBwZW5kKG1baV0pCiAgICAgICAgcy5hcHBlbmQoYVtpXSkKICAgIHMuYXBwZW5kKG1bLTFdKQogICAgcmV0dXJuICIiLmpvaW4ocykKCmRlZiBmMyhhLGIpOgogICAgbT1iLnNwbGl0KCJeIikKICAgIHJldHVybiAiIi5qb2luKG1baV0rYVtpXSBmb3IgaSBpbiByYW5nZShsZW4oYSkpKSttWy0xXQoKcj1yZS5jb21waWxlKCJcXiIpCmRlZiBmNChhLGIpOgogICAgcz0iIgogICAgaT0wCiAgICBmb3IgdCxtIGluIGVudW1lcmF0ZShyLmZpbmRpdGVyKGIpKToKICAgICAgICBzKz1iW2k6bS5zdGFydCgpXSthW3RdCiAgICAgICAgaT1tLmVuZCgpCiAgICBzKz1iW2k6XQogICAgcmV0dXJuIHMKCmRlZiBmNShhLGIpOgogICAgcz1iCiAgICBmb3IgeCBpbiBhOgogICAgICAgIHM9cy5yZXBsYWNlKCJeIix4LDEpCiAgICByZXR1cm4gcwoKYWxwaGEgPSAnYWJjZGVmZ2hpamtsbW5vcHFyc3R1dnd4eXonCm51bWJlciA9ICcwMTIzNDU2Nzg5JwpkZWYgZyhuKToKICAgIGRhdGE9W10KICAgIGZvciBjIGluIHJhbmdlKG4pOgogICAgICAgIHc9cmFuZG9tLnJhbmRpbnQoMTIsMzApCiAgICAgICAgYT1bIiIuam9pbihyYW5kb20uY2hvaWNlcyhhbHBoYSxrPXJhbmRvbS5yYW5kaW50KDUsMjApKSkgZm9yIHggaW4gcmFuZ2UodyldCiAgICAgICAgYj0iXiIuam9pbigiIi5qb2luKHJhbmRvbS5jaG9pY2VzKG51bWJlcixrPXJhbmRvbS5yYW5kaW50KDUsMjApKSkgZm9yIHggaW4gcmFuZ2UodysxKSkKICAgICAgICBkYXRhKz1bW2EsYl1dCiAgICByZXR1cm4gZGF0YQoKZGVmIHRlc3QoKmZmKToKICAgIGE9WyJhYSIsImJiIiwiY2MiXQogICAgYj0iMTExXjIyMl4zMzMzXjQ0NDQ0IgogICAgZGF0YT1nKDEwMDAwKQogICAgcHJpbnQoZiJleGFtcGxlIGRhdGE6XG57ZGF0YVswXVswXX1cbntkYXRhWzBdWzFdfSIpCiAgICBmb3IgZiBpbiBmZjoKICAgICAgICBhc3NlcnQgZihhLGIpPT0iMTExYWEyMjJiYjMzMzNjYzQ0NDQ0IgogICAgICAgIHByaW50KGYie2YuX19uYW1lX199OiB7ZihhLGIpfSIpCiAgICAgICAgdDE9dGltZSgpCiAgICAgICAgYz1bZigqeCkgZm9yIHggaW4gZGF0YV0gICAgCiAgICAgICAgdDI9dGltZSgpCiAgICAgICAgcHJpbnQoZiJ0aW1lOiB7KHQyLXQxKSoxZTM6LjNmfSIpCiAgICAKdGVzdChmMSxmMixmMyxmNCxmNSkKCg==