empty_rlist = None

def make_rlist(first, rest = empty_rlist):
    """A recursive list, r, such that first(r) is FIRST and 
    rest(r) is REST,  which must be an rlist."""
    return [first, rest]

def first(r):
    """The first item in R."""
    return r[0]

def rest(r):
    """The tail of R."""
    return r[1]

def isempty(r):
    """True iff R is the empty sequence"""
    return r is None

def set_first(r, v):
    r[0] = v

def set_rest(r, v):
    r[1] = v

def map_rlist(f, s):                      
    """The rlist of values F(x) for each  
    x in rlist S (in the same order.)"""  
    if (isempty(s)):                      
        return s
    result = last = make_rlist(f(first(s)))
    s = rest(s) 
    while not isempty(s):
        set_rest(last,
                 make_rlist(f(first(s))))  
        last, s = rest(last), rest(s)
    return result

def cons(left, right):
    def data(which, value=None):
        if which == 0: return left
        elif which == 1: return right
        elif which == 2: left = value
        else: right = value
    return data

def left(pair):
    return pair(0)
def right(pair):
    return pair(1)
def set_left(pair, v):
    return pair(2, v)
def set_right(pair, v):
    return pair(3, v)

import time
def make_dice(sides = 6, seed = None):
    """A new 'sides'-sided die that yields numbers between 1 and
    'sides' when called.  'seed' controls the sequence of values.
    If it is defaulted, the system chooses a non-deterministic value."""

    if seed == None:
         seed = int(time.time() * 100000)
    a, c, m = 25214903917, 11, 2**48  # From Java

    def die():
        nonlocal seed
        seed = (a*seed + c) % m
        return seed % sides + 1
    return die

def frequencies(L):
    """A dictionary giving, for each w in L, the number of times w 
    appears in L.
    >>> frequencies(['the', 'name', 'of', 'the', 'name', 'of', 'the',
    ...              'song'])
    {'of': 2, 'the': 3, 'name': 2, 'song': 1}
    """
    return { L[i-1]: L[i] for i in range(1, len(L)) }

# Or, the long way:

def frequencies2(L):
    """A dictionary giving, for each w in L, the number of times w 
    appears in L.
    >>> frequencies(['the', 'name', 'of', 'the', 'name', 'of', 'the',
    ...              'song'])
    {'of': 2, 'the': 3, 'name': 2, 'song': 1}
    """
    result = {}
    for i in range(1, len(L)):
        result[L[i-1]] = L[i]
    return result

def is_duplicate(L):
    """True iff L contains a duplicated item."""
    items = {}
    for x in L:
        if x in items: return True
        items[x] = True   # Or any value
    return False

def common_keys(D0, D1):
    """Return dictionary containing the keys common to D0 and D1."""
    result = {}
    for x in D0:
         if x in D1: result[x] = True
    return result

# Using sets

def is_duplicate(L):
    """True iff L contains a duplicated item."""
    return len(L) != len(set(L))

def common_keys(D0, D1):
    """Return set containing the keys common to D0 and D1."""
    return set(D0) & set(D1)