#This is just a handy function that clears the screen on windows.
import os
clear = lambda: os.system('cls')

def fib(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    return fib(n - 2) + fib(n - 1)

def fib_iter(n):
    prev, curr = 1, 0
    for _ in range(n-1):
         prev, curr = curr, prev + curr
    return curr

def memo(f):
    cache = {}
    def memoized(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return memoized

@memo
def fib_memo(n):
    """Compute the nth Fibonacci number.

    >>> fib_memo(35)
    5702887
    >>> fib_memo(100)
    218922995834555169026
    """
    if n == 1:
        return 0
    if n == 2:
        return 1
    return fib_memo(n - 2) + fib_memo(n - 1)

# Recursive lists in OOP
class Rlist(object):
    """A recursive list consisting of a first element and the rest.

    >>> s = Rlist(1, Rlist(2, Rlist(3)))
    >>> len(s)
    3
    >>> s[0]
    1
    >>> s[1]
    2
    >>> s[2]
    3
    """
    class EmptyList(object):
        def __len__(self):
            return 0
    empty = EmptyList()

    def __init__(self, first, rest=empty):
        self.first = first
        self.rest = rest

    def __repr__(self):
        f = repr(self.first)
        if self.rest is Rlist.empty:
            return 'Rlist({0})'.format(f)
        else:
            return 'Rlist({0}, {1})'.format(f, repr(self.rest))

    def __len__(self):
        return 1 + len(self.rest)

    def __getitem__(self, i):
        if i == 0:
            return self.first
        return self.rest[i - 1]

def extend_rlist(s1, s2):
    """Return a list containing the elements of s1 followed by those
    of s2.

    >>> s = Rlist(1, Rlist(2, Rlist(3)))
    >>> extend_rlist(s.rest, s)
    Rlist(2, Rlist(3, Rlist(1, Rlist(2, Rlist(3)))))
    """
    if s1 is Rlist.empty:
        return s2
    return Rlist(s1.first, extend_rlist(s1.rest, s2))

def map_rlist(s, fn):
    """Return an Rlist resulting from mapping fn over the elements of
    s.

    >>> s = Rlist(1, Rlist(2, Rlist(3)))
    >>> map_rlist(s, lambda x: x * x)
    Rlist(1, Rlist(4, Rlist(9)))
    """
    if s is Rlist.empty:
        return s
    return Rlist(fn(s.first), map_rlist(s.rest, fn))

def filter_rlist(s, fn):
    """Filter the elements of s by predicate fn.

    >>> s = Rlist(1, Rlist(2, Rlist(3)))
    >>> filter_rlist(s, lambda x: x % 2 == 1)
    Rlist(1, Rlist(3))
    """
    if s is Rlist.empty:
        return s
    rest = filter_rlist(s.rest, fn)
    if fn(s.first):
        return Rlist(s.first, rest)
    return rest

# Take 1: Sets as unordered sequences
s = Rlist(1, Rlist(2, Rlist(3))) # A set is an Rlist with no duplicates

def empty(s):
    return s is Rlist.empty

def set_contains(s, v):
    """Return true if set s contains value v as an element.

    >>> set_contains(s, 2)
    True
    >>> set_contains(s, 5)
    False
    """
    if empty(s):
        return False
    if s.first == v:
        return True
    return set_contains(s.rest, v)

def adjoin_set(s, v):
    """Return a set containing all elements of s and element v.

    >>> t = adjoin_set(s, 4)
    >>> t
    Rlist(4, Rlist(1, Rlist(2, Rlist(3))))
    """
    if set_contains(s, v):
        return s
    return Rlist(v, s)

def intersect_set(set1, set2):
    """Return a set containing all elements common to set1 and set2.

    >>> t = adjoin_set(s, 4)
    >>> intersect_set(t, map_rlist(s, lambda x: x*x))
    Rlist(4, Rlist(1))
    """
    return filter_rlist(set1, lambda v: set_contains(set2, v))

def union_set(set1, set2):
    """Return a set containing all elements either in set1 or set2.

    >>> t = adjoin_set(s, 4)
    >>> union_set(t, s)
    Rlist(4, Rlist(1, Rlist(2, Rlist(3))))
    """
    set1_not_set2 = filter_rlist(set1, lambda v: not set_contains(set2, v))
    return extend_rlist(set1_not_set2, set2)

# Take 2: Sets as (sorted) ordered sequences
def set_contains2(s, v):
    """Return true if set s contains value v as an element.

    >>> set_contains2(s, 2)
    True
    >>> set_contains2(s, 5)
    False
    """
    if empty(s) or s.first > v:
        return False
    if s.first == v:
        return True
    return set_contains2(s.rest, v)

def intersect_set2(set1, set2):
    """Return a set containing all elements common to set1 and set2.

    >>> t = Rlist(2, Rlist(3, Rlist(4)))
    >>> intersect_set2(s, t)
    Rlist(2, Rlist(3))
    """
    if empty(set1) or empty(set2):
        return Rlist.empty
    e1, e2 = set1.first, set2.first
    if e1 == e2:
        return Rlist(e1, intersect_set2(set1.rest, set2.rest))
    if e1 < e2:
        return intersect_set2(set1.rest, set2)
    if e2 < e1:
        return intersect_set2(set1, set2.rest)