import re, collections, sys, randomdef words(text): return re.findall('[a-z]+', text.lower()) def defaultdict_factoryn(n, default):
    if n == 1: return lambda: default
    return lambda: collections.defaultdict(defaultdict_factoryn(n-1, default))def multidict_set(d, l, v):
    curd = d;
    i = 0
    for ele in l:
        i += 1
        if i == len(l):
            curd[ele] = v
        else:
            curd = curd[ele]def multidict_add(d, l, v):
    curd = d;
    i = 0
    for ele in l:
        i += 1
        if i == len(l):
            curd[ele] += v
        else:
            curd = curd[ele]def multidict_get(d, l):
    curd = d;
    i = 0
    for ele in l:
        curd = curd[ele]
    return curddef train(features, n):
    model = collections.defaultdict(defaultdict_factoryn(n, 1))
    prevlen = n
    prev = collections.deque()
    for f in features:
        if (len(prev) < prevlen):
            prev.append(f)
            continue
        multidict_add(model, prev, 1)
        prev.popleft()
        prev.append(f)
    return modeldef most_likely(prev):
    l = multidict_get(Model, prev)
    if not l:
        return ""
    l = l.items()
    if len(l) == 0:
        return ""
    l = sorted(l, cmp=lambda x, y:y[1] - x[1])
    count = min(len(l) - 1, 10)
    return l[random.randint(0, count)][0]

stage