# coding=utf-8

# Copyright (c) 2017, 2019, Oracle and/or its affiliates.

# Copyright (c) 2017, The PyPy Project

#

# The MIT License

# Permission is hereby granted, free of charge, to any person

# obtaining a copy of this software and associated documentation

# files (the "Software"), to deal in the Software without

# restriction, including without limitation the rights to use,

# copy, modify, merge, publish, distribute, sublicense, and/or

# sell copies of the Software, and to permit persons to whom the

# Software is furnished to do so, subject to the following conditions:

#

# The above copyright notice and this permission notice shall be included

# in all copies or substantial portions of the Software.

#

# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS

# OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL

# THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING

# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER

# DEALINGS IN THE SOFTWARE.

class repeat():

def __init__(self, obj, times=None):

self.obj = obj

self.times = times

self.step = 0

def __iter__(self):

return self

def __next__(self):

if self.times is not None:

if self.step >= self.times:

raise StopIteration

else:

self.step += 1

return self.obj

class chain():

"""

Return a chain object whose .__next__() method returns elements from the

first iterable until it is exhausted, then elements from the next

iterable, until all of the iterables are exhausted.

"""

def __init__(self, *iterables):

self._iterables = iterables

self._len = len(iterables)

if self._len > 0:

self._current = iter(self._iterables[0])

self._idx = 0

def __iter__(self):

return self

def __next__(self):

if self._idx >= self._len:

raise StopIteration

try:

return next(self._current)

except (StopIteration, IndexError):

self._idx += 1

if self._idx >= self._len:

raise StopIteration

self._current = iter(self._iterables[self._idx])

return self.__next__()

@classmethod

def from_iterable(cls, arg):

return cls(*iter(arg))

class starmap():

"""starmap(function, sequence) --> starmap object

Return an iterator whose values are returned from the function evaluated

with an argument tuple taken from the given sequence.

"""

def __init__(self, fun, iterable):

self.fun = fun

self.iterable = iter(iterable)

def __iter__(self):

return self

def __next__(self):

obj = next(self.iterable)

return self.fun(*obj)

class islice(object):

def __init__(self, iterable, *args):

self._iterable = enumerate(iter(iterable))

self._indexes = iter(range(*args))

def __iter__(self):

return self

def __next__(self):

index = next(self._indexes) # may raise StopIteration

while True:

i, element = next(self._iterable) # may raise StopIteration

if i == index:

return element

class count(object):

def __init__(self, start=0, step=1):

if not isinstance(start, (int, float)) or \

not isinstance(step, (int, float)):

raise TypeError('a number is required')

self._cnt = start

self._step = step

def __next__(self):

_cnt = self._cnt

self._cnt += self._step

return _cnt

def __repr__(self):

_repr = 'count({}'.format(self._cnt)

if not isinstance(self._step, int) or self._step != 1:

_repr += ', {}'.format(self._step)

return _repr + ')'

class permutations():

"""permutations(iterable[, r]) --> permutations object

Return successive r-length permutations of elements in the iterable.

permutations(range(3), 2) --> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1)

"""

def __init__(self, iterable, r = None):

self.pool = iterable

if r is None:

self.r = len(iterable)

else:

self.r = r

n = len(iterable)

n_minus_r = n - self.r

if n_minus_r < 0:

self.stopped = self.raised_stop_iteration = True

else:

self.stopped = self.raised_stop_iteration = False

self.indices = list(range(n))

self.cycles = list(range(n, n_minus_r, -1))

self.started = False

def __iter__(self):

return self

def __next__(self):

if self.stopped:

self.raised_stop_iteration = True

raise StopIteration

r = self.r

indices = self.indices

result = tuple([self.pool[indices[i]] for i in range(r)])

cycles = self.cycles

i = r - 1

while i >= 0:

j = cycles[i] - 1

if j > 0:

cycles[i] = j

indices[i], indices[-j] = indices[-j], indices[i]

return result

cycles[i] = len(indices) - i

n1 = len(indices) - 1

assert n1 >= 0

num = indices[i]

for k in range(i, n1):

indices[k] = indices[k+1]

indices[n1] = num

i -= 1

self.stopped = True

if self.started:

raise StopIteration

else:

self.started = True

return result

def __reduce__(self):

if self.raised_stop_iteration:

pool = []

else:

pool = self.pool

result = [

type(self),

tuple([

tuple(pool), self.r

])

]

if not self.raised_stop_iteration:

# we must pickle the indices and use them for setstate

result = result + [

tuple([

tuple(self.indices),

tuple(self.cycles),

self.started,

])]

return tuple(result)

def __setstate__(self, state):

state = list(state)

if len(state) == 3:

indices, cycles, started = state

indices = list(indices)

cycles = list(cycles)

self.started = bool(started)

else:

raise ValueError("invalid arguments")

if len(indices) != len(self.pool) or len(cycles) != self.r:

raise ValueError("invalid arguments")

n = len(self.pool)

for i in range(n):

index = indices[i]

if index < 0:

index = 0

elif index > n-1:

index = n-1

self.indices[i] = index

for i in range(self.r):

index = cycles[i]

if index < 1:

index = 1

elif index > n-i:

index = n-i

self.cycles[i] = index

class product():

"""Cartesian product of input iterables.

Equivalent to nested for-loops in a generator expression. For example,

``product(A, B)`` returns the same as ``((x,y) for x in A for y in B)``.

The nested loops cycle like an odometer with the rightmost element advancing

on every iteration. This pattern creates a lexicographic ordering so that if

the input's iterables are sorted, the product tuples are emitted in sorted

order.

To compute the product of an iterable with itself, specify the number of

repetitions with the optional *repeat* keyword argument. For example,

``product(A, repeat=4)`` means the same as ``product(A, A, A, A)``.

This function is equivalent to the following code, except that the

actual implementation does not build up intermediate results in memory::

def product(*args, **kwds):

# product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy

# product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111

pools = map(tuple, args) * kwds.get('repeat', 1)

result = [[]]

for pool in pools:

result = [x+[y] for x in result for y in pool]

for prod in result:

yield tuple(prod)

"""

def __init__(self, *args, repeat=1):

self.gears = [list(arg) for arg in args] * repeat

for gear in self.gears:

if len(gear) == 0:

self.indices = None

self.lst = None

self.stopped = True

break

else:

self.indices = [0] * len(self.gears)

self.lst = None

self.stopped = False

def _rotate_previous_gears(self):

lst = self.lst

x = len(self.gears) - 1

lst[x] = self.gears[x][0]

self.indices[x] = 0

x -= 1

# the outer loop runs as long as a we have a carry

while x >= 0:

gear = self.gears[x]

index = self.indices[x] + 1

if index < len(gear):

# no carry: done

lst[x] = gear[index]

self.indices[x] = index

return

lst[x] = gear[0]

self.indices[x] = 0

x -= 1

else:

self.lst = None

self.stopped = True

def fill_next_result(self):

# the last gear is done here, in a function with no loop,

# to allow the JIT to look inside

if self.lst is None:

self.lst = [None for gear in self.gears]

for index, gear in enumerate(self.gears):

self.lst[index] = gear[0]

return

lst = self.lst

x = len(self.gears) - 1

if x >= 0:

gear = self.gears[x]

index = self.indices[x] + 1

if index < len(gear):

# no carry: done

lst[x] = gear[index]

self.indices[x] = index

else:

self._rotate_previous_gears()

else:

self.stopped = True

def __iter__(self):

return self

def __next__(self):

if not self.stopped:

self.fill_next_result()

if self.stopped:

raise StopIteration

return tuple(self.lst)

def __reduce__(self):

if not self.stopped:

gears = [tuple(gear) for gear in self.gears]

result = [

type(self),

tuple(gears)

]

if self.lst is not None:

result = result + [tuple(self.indices)]

else:

result = [

type(self),

tuple([tuple([])])

]

return tuple(result)

def __setstate__(self, state):

gear_count = len(self.gears)

indices = list(state)

lst = []

for i, gear in enumerate(self.gears):

index = indices[i]

gear_size = len(gear)

if self.indices is None or gear_size == 0:

self.stopped = True

return

if index < 0:

index = 0

if index > gear_size - 1:

index = gear_size - 1

self.indices[i] = index

lst.append(gear[index])

self.lst = lst

class accumulate(object):

"""

"accumulate(iterable) --> accumulate object

Return series of accumulated sums."""

def __init__(self, iterable, func=None):

self.iterable = iter(iterable)

self.func = func

self.total = None

def __iter__(self):

return self

def __next__(self):

value = next(self.iterable)

if self.total is None:

self.total = value

return value

if self.func is None:

self.total += value

else:

self.total = self.func(total, value)

return self.total

class dropwhile(object):

"""

dropwhile(predicate, iterable) --> dropwhile object

Drop items from the iterable while predicate(item) is true.

Afterwards, return every element until the iterable is exhausted.

"""

def __init__(self, predicate, iterable):

self.predicate = predicate

self.iterable = iter(iterable)

self.done_dropping = False

def __iter__(self):

return self

def __next__(self):

while not self.done_dropping:

n = next(self.iterable)

if self.predicate(n):

continue

else:

self.done_dropping = True

return n

return next(self.iterable)

class filterfalse(object):

"""

filterfalse(function or None, sequence) --> filterfalse object

Return those items of sequence for which function(item) is false.

If function is None, return the items that are false.

"""

def __init__(self, func, sequence):

self.func = func or (lambda x: False)

self.iterator = iter(sequence)

def __iter__(self):

return self

def __next__(self):

while True:

n = next(self.iterator)

if not self.func(n):

return n

class takewhile(object):

"""Make an iterator that returns elements from the iterable as

long as the predicate is true.

Equivalent to :

def takewhile(predicate, iterable):

for x in iterable:

if predicate(x):

yield x

else:

break

"""

def __init__(self, predicate, iterable):

self._predicate = predicate

self._iter = iter(iterable)

def __iter__(self):

return self

def __next__(self):

value = next(self._iter)

if not self._predicate(value):

self._iter = iter([])

raise StopIteration()

return value

class groupby(object):

"""Make an iterator that returns consecutive keys and groups from the

iterable. The key is a function computing a key value for each

element. If not specified or is None, key defaults to an identity

function and returns the element unchanged. Generally, the

iterable needs to already be sorted on the same key function.

The returned group is itself an iterator that shares the

underlying iterable with groupby(). Because the source is shared,

when the groupby object is advanced, the previous group is no

longer visible. So, if that data is needed later, it should be

stored as a list:

groups = []

uniquekeys = []

for k, g in groupby(data, keyfunc):

groups.append(list(g)) # Store group iterator as a list

uniquekeys.append(k)

"""

def __init__(self, iterable, key=None):

self._iterator = iter(iterable)

self._keyfunc = key

self._tgtkey = self._currkey = self._currvalue = None

def __iter__(self):

return self

def __next__(self):

self._skip_to_next_iteration_group()

key = self._tgtkey = self._currkey

grouper = _groupby(self, key)

return (key, grouper)

def _skip_to_next_iteration_group(self):

while True:

if self._currkey is None:

pass

elif self._tgtkey is None:

break

else:

if not self._tgtkey == self._currkey:

break

newvalue = next(self._iterator)

if self._keyfunc is None:

newkey = newvalue

else:

newkey = self._keyfunc(newvalue)

self._currkey = newkey

self._currvalue = newvalue

class _groupby():

def __init__(self, groupby, tgtkey):

self.groupby = groupby

self.tgtkey = tgtkey

def __iter__(self):

return self

def __next__(self):

groupby = self.groupby

if groupby._currvalue is None:

newvalue = next(groupby._iterator)

if groupby._keyfunc is None:

newkey = newvalue

else:

newkey = groupby._keyfunc(newvalue)

assert groupby._currvalue is None

groupby._currkey = newkey

groupby._currvalue = newvalue

assert groupby._currkey is not None

if not self.tgtkey == groupby._currkey:

raise StopIteration(None)

result = groupby._currvalue

groupby._currvalue = None

groupby._currkey = None

return result

class combinations():

"""

combinations(iterable, r) --> combinations object

Return successive r-length combinations of elements in the iterable.

combinations(range(4), 3) --> (0,1,2), (0,1,3), (0,2,3), (1,2,3)

"""

def __init__(self, pool, indices, r):

self.pool = pool

self.indices = indices

if r < 0:

raise ValueError("r must be non-negative")

self.r = r

self.last_result = None

self.stopped = r > len(pool)

def get_maximum(self, i):

return i + len(self.pool) - self.r

def max_index(self, j):

return self.indices[j - 1] + 1

def __iter__(self):

return self

def __next__(self):

if self.stopped:

raise StopIteration

if self.last_result is None:

# On the first pass, initialize result tuple using the indices

result = [None] * self.r

for i in range(self.r):

index = self.indices[i]

result[i] = self.pool[index]

else:

# Copy the previous result

result = self.last_result[:]

# Scan indices right-to-left until finding one that is not at its

# maximum

i = self.r - 1

while i >= 0 and self.indices[i] == self.get_maximum(i):

i -= 1

# If i is negative, then the indices are all at their maximum value

# and we're done

if i < 0:

self.stopped = True

raise StopIteration

# Increment the current index which we know is not at its maximum.

# Then move back to the right setting each index to its lowest

# possible value

self.indices[i] += 1

for j in range(i + 1, self.r):

self.indices[j] = self.max_index(j)

# Update the result for the new indices starting with i, the

# leftmost index that changed

for i in range(i, self.r):

index = self.indices[i]

elem = self.pool[index]

result[i] = elem

self.last_result = result

return tuple(result)

class combinations_with_replacement(combinations):

"""

combinations_with_replacement(iterable, r) --> combinations_with_replacement object

Return successive r-length combinations of elements in the iterable

allowing individual elements to have successive repeats.

combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC

"""

def __init__(self, iterable, r):

pool = list(iterable)

if r < 0:

raise ValueError("r must be non-negative")

indices = [0] * r

super().__init__(pool, indices, r)

self.stopped = len(pool) == 0 and r > 0

def get_maximum(self, i):

return len(self.pool) - 1

def max_index(self, j):

return self.indices[j - 1]

class zip_longest():

"""

zip_longest(iter1 [,iter2 [...]], [fillvalue=None]) --> zip_longest object

Return a zip_longest object whose .next() method returns a tuple where

the i-th element comes from the i-th iterable argument. The .next()

method continues until the longest iterable in the argument sequence

is exhausted and then it raises StopIteration. When the shorter iterables

are exhausted, the fillvalue is substituted in their place. The fillvalue

defaults to None or can be specified by a keyword argument.

"""

def __iter__(self):

return self

def _fetch(self, index):

it = self.iterators[index]

if it is not None:

try:

return next(it)

except StopIteration:

self.active -= 1

if self.active <= 0:

# It was the last active iterator

raise

self.iterators[index] = None

return self.fillvalue

def __next__(self):

if self.active <= 0:

raise StopIteration

nb = len(self.iterators)

if nb == 0:

raise StopIteration

result = []

for index in range(nb):

result.append(self._fetch(index))

return tuple(result)

def __new__(subtype, iter1, *args, fillvalue=None):

self = object.__new__(subtype)

self.fillvalue = fillvalue

self.active = len(args) + 1

self.iterators = [iter(iter1)] + [iter(arg) for arg in args]

return self

class cycle():

"""

Make an iterator returning elements from the iterable and

saving a copy of each. When the iterable is exhausted, return

elements from the saved copy. Repeats indefinitely.

Equivalent to :

def cycle(iterable):

saved = []

for element in iterable:

yield element

saved.append(element)

while saved:

for element in saved:

yield element

"""

def __init__(self, iterable):

self.saved = []

self.iterable = iter(iterable)

self.index = 0

def __iter__(self):

return self

def __next__(self):

if self.index > 0:

if not self.saved:

raise StopIteration

if len(self.saved) > self.index:

obj = self.saved[self.index]

self.index += 1

else:

obj = self.saved[0]

self.index = 1

else:

try:

obj = next(self.iterable)

except StopIteration:

if not self.saved:

raise

obj = self.saved[0]

self.index = 1

else:

self.saved.append(obj)

return obj