def process_input(input):
    """ Returns rules and messages, as lists
        Rules = ['0: 4 1 5', '1: 2 3 | 3 2', etc]
        Messages = ['ababbb', 'bababa', etc]
    """
    # first split the rules block from the messages block
    rules_line, messages_line = input.split("\n\n")

    # then split each blow into a list of sorted rules / messages
    rules = rules_line.splitlines()

    # we want to sort, since we want RULE0 at the top.
    # PEG will start by applying the first rule in the PEG grammar.
    rules.sort(key = lambda x: int(x.split(":")[0]))
    messages = messages_line.splitlines()
    return rules, messages