import sys
from itertools import tee

def head_tail(xs):
    # xs=x:xt -> (x, xt)
    # xs=[] -> (None, None)
    if isinstance(xs, tuple):
        assert len(xs)==2
        return xs
    if isinstance(xs, list):
        if xs:
            return xs[0], xs[1:]
        else:
            return None, None
    xs = iter(xs)
    try:
        x = next(xs)
    except StopIteration:
        return None, None
    return x, xs


def merge(xs, ys):
    # iterative version
    while True:
        xs = x, xt = head_tail(xs)
        ys = y, yt = head_tail(ys)
        if x is None:
            if y is not None:
                yield y
                for _ in yt: yield _
            return
        if y is None:
            yield x
            for _ in xt: yield _
            return
        c = cmp((len(x), x), (len(y), y))
        if c<0:
            yield x
            xs = xt
        elif c==0:
            yield x
            xs, ys = xt, yt
        else:
            yield y
            ys = yt

def prod(xs, ys):
    x, xt = head_tail(xs)
    y, yt = head_tail(ys)
    if x is None or y is None:
        return
    else:
        yield x+y
        yt, yt2 = tee(yt)
        for _ in merge(prod([x], yt), prod(xt, (y, yt2))):
            yield _

def closure(xs, level=sys.maxint):
    if level<0: return
    x, xt = head_tail(xs)
    if x is None:
        yield ''
    elif x=='':
        for _ in closure(xt, level-1): yield _
    else:
        yield ''
        xt, xt2 = tee(xt)
        for _ in prod((x, xt), closure((x, xt2), level-1)): yield _

assert head_tail((1, [2,3,4])) == (1, [2,3,4])
assert head_tail((1, [])) == (1, [])
assert head_tail([]) == (None, None)
assert head_tail([1]) == (1, [])
assert head_tail([1,2]) == (1, [2])
assert head_tail([1,2,3]) == (1, [2,3])
assert head_tail(x for x in []) == (None, None)
x, xs = head_tail(x for x in [1])
assert x == 1
assert list(xs) == []
x, xs = head_tail(x for x in [1,2])
assert x == 1
assert list(xs) == [2]
x, xs = head_tail(x for x in [1,2,3])
assert x == 1
assert list(xs) == [2,3]

assert list(merge(list('134'),list('1247'))) == ['1','2','3','4','7']
assert list(merge(['a','aab'],['b','bb'])) == ['a','b','bb','aab']
assert list(prod(['','a'],['b','ab'])) == ['b','ab','aab']
assert list(prod(['a','b'],['','a','b'])) == ['a','b','aa','ab','ba','bb']
assert list(closure(['a'], 3)) == ['', 'a', 'aa', 'aaa']
assert list(closure(['a','b'], 2)) == ['', 'a', 'b', 'aa', 'ab', 'ba', 'bb']
assert len(list(closure(['a','b'], 5))) == 63

"(a|bc)*d"
g = prod(closure(merge(['a'], prod(['b'],['c']))),['d'])
try:
    for s in g: print s
except RuntimeError:
    pass