gistfile1.py

import sys
from multiprocessing import Process, Queue
from cStringIO import StringIO
import gc

def memory_safe(f):
    def g(*args):
        def h(q, aargs):
            q.put(f(*aargs))
        q = Queue()
        p = Process(target=h, args=(q, args))
        p.start()
        return q.get()
    return g

#@memory_safe
def solve(inp):
    inp_stream = StringIO(inp)
    s = inp_stream.readline().strip()[:-1]
    k = int(inp_stream.readline())

    tree = {}
    parent = {}

    for line in inp_stream:
        line = line.split()
        start = line[0]
        end = line[1]
        pos = int(line[2])
        length = int(line[3])
        seq = s[pos - 1: pos - 1 + length]
        tree.setdefault(start, []).append((end, seq))
        parent[end] = start

    root = 'node1'

    mults = {}
    lengths = {}

    def dfs(node, tree, depth):
        lengths[node] = depth
        if node not in tree:
            mults[node] = 1
        else:
            mults[node] = 0
            for next, seq in tree[node]:
                mults[node] += dfs(next, tree, depth + len(seq))
        return mults[node]

    dfs(root, tree, 0)

    #print mults
    #print lengths

    ans = None, 0

    for node, mult in mults.iteritems():
        if mult >= k:
            length = lengths[node]
            if ans[1] < length:
                ans = node, length

    cur = ans[0]
    ansseq = []
    while cur != root:
        par = parent[cur]
        for next, seq in tree[par]:
            if next == cur:
                ansseq = [seq] + ansseq
                break
        cur = par

    return ''.join(ansseq)

inp = sys.stdin.read()
print solve(inp)

gc.collect()