def repeat(object, times=None):

    # repeat(10, 3) --> 10 10 10

    if times is None:

        while True:

            yield object

    else:

        for i in range(times):

            yield object

def cycle(iterable):

    # cycle('ABCD') --> A B C D A B C D A B C D ...

    saved = []

    for element in iterable:

        yield element

        saved.append(element)

    while saved:

        for element in saved:

def count(start=0, step=1):

    # count(10) --> 10 11 12 13 14 ...

    # count(2.5, 0.5) -> 2.5 3.0 3.5 ...

    n = start

    while True:

        yield n

        n += step

def compress(data, selectors):

    # compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F

    return (d for d, s in zip(data, selectors) if s)

def dropwhile(predicate, iterable):

    # dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1

    iterable = iter(iterable)

    for x in iterable:

        if not predicate(x):

            yield x

            break

    for x in iterable:

        yield x

def takewhile(predicate, iterable):

    # takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4

    for x in iterable:

        if predicate(x):

            yield x

        else:

            break

def tee(iterable, n=2):

    it = iter(iterable)

    deques = [collections.deque() for i in range(n)]

    def gen(mydeque):

        while True:

            if not mydeque:             # when the local deque is empty

                try:

                    newval = next(it)   # fetch a new value and

                except StopIteration:

                    return

                for d in deques:        # load it to all the deques

                    d.append(newval)

            yield mydeque.popleft()

    return tuple(gen(d) for d in deques)

def filterfalse(predicate, iterable):

    # filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8

    if predicate is None:

        predicate = bool

    for x in iterable:

        if not predicate(x):

            yield x

def starmap(function, iterable):

    # starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000

    for args in iterable:

        yield function(*args)

class ZipExhausted(Exception):

    pass

def zip_longest(*args, **kwds):

    # zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-

    fillvalue = kwds.get('fillvalue')

    counter = len(args) - 1

    def sentinel():

        nonlocal counter

        if not counter:

            raise ZipExhausted

        counter -= 1

        yield fillvalue

    fillers = repeat(fillvalue)

    iterators = [chain(it, sentinel(), fillers) for it in args]

    try:

        while iterators:

            yield tuple(map(next, iterators))

    except ZipExhausted:

        pass

def take(n, iterable):

    "Return first n items of the iterable as a list"

    return list(islice(iterable, n))

def tabulate(function, start=0):

    "Return function(0), function(1), ..."

    return map(function, count(start))

def tail(n, iterable):

    "Return an iterator over the last n items"

    # tail(3, 'ABCDEFG') --> E F G

    return iter(collections.deque(iterable, maxlen=n))

def consume(iterator, n):

    "Advance the iterator n-steps ahead. If n is none, consume entirely."

    # Use functions that consume iterators at C speed.

    if n is None:

        # feed the entire iterator into a zero-length deque

        collections.deque(iterator, maxlen=0)

    else:

        # advance to the empty slice starting at position n

        next(islice(iterator, n, n), None)

def nth(iterable, n, default=None):

    "Returns the nth item or a default value"

    return next(islice(iterable, n, None), default)

def all_equal(iterable):

    "Returns True if all the elements are equal to each other"

    g = groupby(iterable)

    return next(g, True) and not next(g, False)

def quantify(iterable, pred=bool):

    "Count how many times the predicate is true"

    return sum(map(pred, iterable))

def padnone(iterable):

    """Returns the sequence elements and then returns None indefinitely.

    Useful for emulating the behavior of the built-in map() function.

    """

    return chain(iterable, repeat(None))

def ncycles(iterable, n):

    "Returns the sequence elements n times"

    return chain.from_iterable(repeat(tuple(iterable), n))

def dotproduct(vec1, vec2):

    return sum(map(operator.mul, vec1, vec2))

def flatten(listOfLists):

    "Flatten one level of nesting"

    return chain.from_iterable(listOfLists)

def repeatfunc(func, times=None, *args):

    """Repeat calls to func with specified arguments.

    Example:  repeatfunc(random.random)

    """

    if times is None:

        return starmap(func, repeat(args))

    return starmap(func, repeat(args, times))

def pairwise(iterable):

    "s -> (s0,s1), (s1,s2), (s2, s3), ..."

    a, b = tee(iterable)

    next(b, None)

    return zip(a, b)

def grouper(iterable, n, fillvalue=None):

    "Collect data into fixed-length chunks or blocks"

    # grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx"

    args = [iter(iterable)] * n

    return zip_longest(*args, fillvalue=fillvalue)

def roundrobin(*iterables):

    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"

    # Recipe credited to George Sakkis

    pending = len(iterables)

    nexts = cycle(iter(it).__next__ for it in iterables)

    while pending:

        try:

            for next in nexts:

                yield next()

        except StopIteration:

            pending -= 1

            nexts = cycle(islice(nexts, pending))

def partition(pred, iterable):

    'Use a predicate to partition entries into false entries and true entries'

    # partition(is_odd, range(10)) --> 0 2 4 6 8   and  1 3 5 7 9

    t1, t2 = tee(iterable)

    return filterfalse(pred, t1), filter(pred, t2)

def powerset(iterable):

    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"

    s = list(iterable)

    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def unique_everseen(iterable, key=None):

    "List unique elements, preserving order. Remember all elements ever seen."

    # unique_everseen('AAAABBBCCDAABBB') --> A B C D

    # unique_everseen('ABBCcAD', str.lower) --> A B C D

    seen = set()

    seen_add = seen.add

    if key is None:

        for element in filterfalse(seen.__contains__, iterable):

            seen_add(element)

            yield element

    else:

        for element in iterable:

            k = key(element)

            if k not in seen:

                seen_add(k)

                yield element

def unique_justseen(iterable, key=None):

    "List unique elements, preserving order. Remember only the element just seen."

    # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B

    # unique_justseen('ABBCcAD', str.lower) --> A B C A D

    return map(next, map(itemgetter(1), groupby(iterable, key)))

def iter_except(func, exception, first=None):

    """ Call a function repeatedly until an exception is raised.

    Converts a call-until-exception interface to an iterator interface.

    Like builtins.iter(func, sentinel) but uses an exception instead

    of a sentinel to end the loop.

    Examples:

        iter_except(functools.partial(heappop, h), IndexError)   # priority queue iterator

        iter_except(d.popitem, KeyError)                         # non-blocking dict iterator

        iter_except(d.popleft, IndexError)                       # non-blocking deque iterator

        iter_except(q.get_nowait, Queue.Empty)                   # loop over a producer Queue

        iter_except(s.pop, KeyError)                             # non-blocking set iterator

    """

    try:

        if first is not None:

            yield first()            # For database APIs needing an initial cast to db.first()

        while True:

            yield func()

    except exception:

        pass

def first_true(iterable, default=False, pred=None):

    """Returns the first true value in the iterable.

    If no true value is found, returns *default*

    If *pred* is not None, returns the first item

    for which pred(item) is true.

    """

    # first_true([a,b,c], x) --> a or b or c or x

    # first_true([a,b], x, f) --> a if f(a) else b if f(b) else x

    return next(filter(pred, iterable), default)

def random_product(*args, repeat=1):

    "Random selection from itertools.product(*args, **kwds)"

    pools = [tuple(pool) for pool in args] * repeat

    return tuple(random.choice(pool) for pool in pools)

def random_permutation(iterable, r=None):

    "Random selection from itertools.permutations(iterable, r)"

    pool = tuple(iterable)

    r = len(pool) if r is None else r

    return tuple(random.sample(pool, r))

def random_combination(iterable, r):

    "Random selection from itertools.combinations(iterable, r)"

    pool = tuple(iterable)

    n = len(pool)

    indices = sorted(random.sample(range(n), r))

    return tuple(pool[i] for i in indices)

def random_combination_with_replacement(iterable, r):

    "Random selection from itertools.combinations_with_replacement(iterable, r)"

    pool = tuple(iterable)

    n = len(pool)

    indices = sorted(random.randrange(n) for i in range(r))

    return tuple(pool[i] for i in indices)