from __future__ import annotations

from collections.abc import Iterable
from dataclasses import dataclass
from typing import Any




class       __lowerCAmelCase     :



 '''simple docstring'''
 _lowerCamelCase  :		str 			=       ('_front', '_back', '_len')




 @dataclass
 class       __lowerCAmelCase     :



  '''simple docstring'''
  _lowerCamelCase  :		Any 			=       None
  _lowerCamelCase  :		Deque._Node | None 			=       None
  _lowerCamelCase  :		Deque._Node | None 			=       None







 class       __lowerCAmelCase     :



  '''simple docstring'''
  _lowerCamelCase  :		str 			=       ('_cur',)

  def __init__(	self				:						List[str]				,	lowerCamelCase				:						Deque._Node | None     )       ->							None:
         _UpperCamelCase   :				Dict       =     cur

  def __iter__(	self				:						Optional[int]     )       ->							Deque._Iterator:
         return self

  def     __snake_case    (	self				:						int     )       ->							Any:
         if self._cur is None:
                # finished iterating
                raise StopIteration
         _UpperCamelCase   :				Any       =     self._cur.val
         _UpperCamelCase   :				Any       =     self._cur.next_node

         return val







 def __init__(	self				:						List[Any]				,	lowerCamelCase				:						Iterable[Any] | None = None     )       ->							None:
        _UpperCamelCase   :				Any       =     None
        _UpperCamelCase   :				Any       =     None
        _UpperCamelCase   :				int       =     0

        if iterable is not None:
               # append every value to the deque
               for val in iterable:
                      self.append(lowerCamelCase     )

 def     __snake_case    (	self				:						str				,	lowerCamelCase				:						Any     )       ->							None:
        _UpperCamelCase   :				str       =     self._Node(lowerCamelCase				,	lowerCamelCase				,	lowerCamelCase     )
        if self.is_empty():
               # front = back
               _UpperCamelCase   :				Optional[int]       =     node
               _UpperCamelCase   :				Tuple       =     1
        else:
               # connect nodes
               _UpperCamelCase   :				List[Any]       =     node
               _UpperCamelCase   :				int       =     self._back
               _UpperCamelCase   :				Optional[int]       =     node  # assign new back to the new node

               self._len += 1

               # make sure there were no errors
               assert not self.is_empty(), "Error on appending value."

 def     __snake_case    (	self				:						Any				,	lowerCamelCase				:						Any     )       ->							None:
        _UpperCamelCase   :				Optional[int]       =     self._Node(lowerCamelCase				,	lowerCamelCase				,	lowerCamelCase     )
        if self.is_empty():
               # front = back
               _UpperCamelCase   :				Union[str, Any]       =     node
               _UpperCamelCase   :				str       =     1
        else:
               # connect nodes
               _UpperCamelCase   :				int       =     self._front
               _UpperCamelCase   :				str       =     node
               _UpperCamelCase   :				str       =     node  # assign new front to the new node

               self._len += 1

               # make sure there were no errors
               assert not self.is_empty(), "Error on appending value."

 def     __snake_case    (	self				:						List[str]				,	lowerCamelCase				:						Iterable[Any]     )       ->							None:
        for val in iterable:
               self.append(lowerCamelCase     )

 def     __snake_case    (	self				:						Optional[Any]				,	lowerCamelCase				:						Iterable[Any]     )       ->							None:
        for val in iterable:
               self.appendleft(lowerCamelCase     )

 def     __snake_case    (	self				:						Union[str, Any]     )       ->							Any:
        assert not self.is_empty(), "Deque is empty."

        _UpperCamelCase   :				str       =     self._back
        _UpperCamelCase   :				Tuple       =     self._back.prev_node  # set new back
        # drop the last node - python will deallocate memory automatically
        _UpperCamelCase   :				List[str]       =     None

        self._len -= 1

        return topop.val

 def     __snake_case    (	self				:						List[str]     )       ->							Any:
        assert not self.is_empty(), "Deque is empty."

        _UpperCamelCase   :				Tuple       =     self._front
        _UpperCamelCase   :				Any       =     self._front.next_node  # set new front and drop the first node
        _UpperCamelCase   :				Any       =     None

        self._len -= 1

        return topop.val

 def     __snake_case    (	self				:						Optional[Any]     )       ->							bool:
        return self._front is None

 def __len__(	self				:						Tuple     )       ->							int:
        return self._len

 def __eq__(	self				:						str				,	lowerCamelCase				:						object     )       ->							bool:

        if not isinstance(lowerCamelCase				,	lowerCamelCase     ):
               return NotImplemented

        _UpperCamelCase   :				Union[str, Any]       =     self._front
        _UpperCamelCase   :				Union[str, Any]       =     other._front

        # if the length of the dequeues are not the same, they are not equal
        if len(self     ) != len(lowerCamelCase     ):
               return False

        while me is not None and oth is not None:
               # compare every value
               if me.val != oth.val:
                      return False
               _UpperCamelCase   :				Optional[Any]       =     me.next_node
               _UpperCamelCase   :				List[str]       =     oth.next_node

        return True

 def __iter__(	self				:						Union[str, Any]     )       ->							Deque._Iterator:
        return Deque._Iterator(self._front     )

 def __repr__(	self				:						str     )       ->							str:
        _UpperCamelCase   :				List[Any]       =     []
        _UpperCamelCase   :				Union[str, Any]       =     self._front
        while aux is not None:
               # append the values in a list to display
               values_list.append(aux.val     )
               _UpperCamelCase   :				List[str]       =     aux.next_node

        return f"[{', '.join(repr(lowerCamelCase     ) for val in values_list     )}]"


if __name__ == "__main__":
 import doctest

 doctest.testmod()




from __future__ import annotations


def SCREAMING_SNAKE_CASE (   lowercase_:		int						,  lowercase_:		int						,  lowercase_:		int ):
       assert n > 1 and a > 0 and greatest_common_divisor(lowercase_						,  lowercase_ ) == 1
       ((_UpperCamelCase)  ,					(_UpperCamelCase)  ,					(_UpperCamelCase))   :				Optional[int]       =     extended_gcd(lowercase_						,  lowercase_ )  # Implemented below
       _UpperCamelCase   :				str       =     (b * s) % n
       return x


def SCREAMING_SNAKE_CASE (   lowercase_:		int						,  lowercase_:		int ):
       ((_UpperCamelCase)  ,					(_UpperCamelCase))   :				Union[str, Any]       =     extended_euclid(lowercase_						,  lowercase_ )  # Implemented below
       if b < 0:
              _UpperCamelCase   :				Union[str, Any]       =     (b % n + n) % n
       return b


def SCREAMING_SNAKE_CASE (   lowercase_:		int						,  lowercase_:		int						,  lowercase_:		int ):
       _UpperCamelCase   :				Union[str, Any]       =     invert_modulo(lowercase_						,  lowercase_ )
       _UpperCamelCase   :				str       =     (b * s) % n
       return x


def SCREAMING_SNAKE_CASE (   lowercase_:		int						,  lowercase_:		int ):
       assert a >= 0 and b >= 0

       if b == 0:
              _UpperCamelCase  ,					_UpperCamelCase  ,					_UpperCamelCase   :				Any       =     a, 1, 0
       else:
              ((_UpperCamelCase)  ,					(_UpperCamelCase)  ,					(_UpperCamelCase))   :				Dict       =     extended_gcd(lowercase_						,  a % b )
              _UpperCamelCase   :				List[str]       =     q
              _UpperCamelCase   :				Any       =     p - q * (a // b)

       assert a % d == 0 and b % d == 0
       assert d == a * x + b * y

       return (d, x, y)


def SCREAMING_SNAKE_CASE (   lowercase_:		int						,  lowercase_:		int ):
       if b == 0:
              return (1, 0)
       ((_UpperCamelCase)  ,					(_UpperCamelCase))   :				Optional[Any]       =     extended_euclid(lowercase_						,  a % b )
       _UpperCamelCase   :				List[Any]       =     a // b
       return (y, x - k * y)


def SCREAMING_SNAKE_CASE (   lowercase_:		int						,  lowercase_:		int ):
       if a < b:
              _UpperCamelCase  ,					_UpperCamelCase   :				Optional[int]       =     b, a

       while a % b != 0:
              _UpperCamelCase  ,					_UpperCamelCase   :				Union[str, Any]       =     b, a % b

       return b


if __name__ == "__main__":
 from doctest import testmod

 testmod(name='''modular_division''', verbose=True)
 testmod(name='''modular_division2''', verbose=True)
 testmod(name='''invert_modulo''', verbose=True)
 testmod(name='''extended_gcd''', verbose=True)
 testmod(name='''extended_euclid''', verbose=True)
 testmod(name='''greatest_common_divisor''', verbose=True)



