


"""simple docstring"""


class snake_case   :
		class snake_case   :
				__UpperCamelCase							     =      '_prev', '_data', '_next'







				def __init__(       self   :							Optional[int]     , a__   :							Tuple     , a__   :							Union[str, Any]     , a__   :							int		)							->    Optional[Any]:





								'''simple docstring'''







								_A       	=      link_p
								_A       	=      element
								_A       	=      link_n







				def 			a_			(       self   :							Any		)							->    Optional[Any]:





								'''simple docstring'''







								return (
								    F""" Prev -> {self._prev is not None}, Next -> {self._next is not None}"""
								)







		def __init__(       self   :							Any		)							->    List[str]:





						'''simple docstring'''







						_A       	=      self._Node(a__     , a__     , a__		)
						_A       	=      self._Node(a__     , a__     , a__		)
						_A       	=      self._trailer
						_A       	=      self._header
						_A       	=      0







		def __len__(       self   :							List[str]		)							->    List[str]:





						'''simple docstring'''







						return self._size







		def 			a_			(       self   :							Optional[Any]		)							->    Union[str, Any]:





						'''simple docstring'''







						return self.__len__() == 0







		def 			a_			(       self   :							Any     , a__   :							int     , a__   :							List[str]     , a__   :							Optional[Any]		)							->    Union[str, Any]:





						'''simple docstring'''







						_A       	=      self._Node(a__     , a__     , a__		)
						_A       	=      new_node
						_A       	=      new_node
						self._size += 1
						return self







		def 			a_			(       self   :							Tuple     , a__   :							Dict		)							->    Dict:





						'''simple docstring'''







						_A       	=      node._prev
						_A       	=      node._next

						_A       	=      successor
						_A       	=      predecessor
						self._size -= 1
						_A       	=      node._data
						_A       	=      _A       	=      _A       	=      None
						del node
						return temp





class snake_case   (	_DoublyLinkedBase):







		def 			a_			(       self   :							List[Any]		)							->    List[Any]:





						'''simple docstring'''







						if self.is_empty():
										raise Exception("List is empty"		)
						return self._header._next._data







		def 			a_			(       self   :							Union[str, Any]		)							->    List[Any]:





						'''simple docstring'''







						if self.is_empty():
										raise Exception("List is empty"		)
						return self._trailer._prev._data







		def 			a_			(       self   :							List[Any]     , a__   :							str		)							->    Any:





						'''simple docstring'''







						return self._insert(self._header     , a__     , self._header._next		)







		def 			a_			(       self   :							Optional[int]     , a__   :							Union[str, Any]		)							->    List[Any]:





						'''simple docstring'''







						return self._insert(self._trailer._prev     , a__     , self._trailer		)







		def 			a_			(       self   :							Dict		)							->    Optional[Any]:





						'''simple docstring'''







						if self.is_empty():
										raise IndexError("remove_first from empty list"		)
						return self._delete(self._header._next		)







		def 			a_			(       self   :							Union[str, Any]		)							->    List[str]:





						'''simple docstring'''







						if self.is_empty():
										raise IndexError("remove_first from empty list"		)
						return self._delete(self._trailer._prev		)



"""simple docstring"""


def   a__			(					__lowercase  ,      __lowercase )						->						Tuple:
				_A       	=      1
				while b > 0:
								if b & 1:
												res *= a

								a *= a
								b >>= 1

				return res






def   a__			(					__lowercase  ,      __lowercase  ,      __lowercase )						->						Optional[Any]:
				_A       	=      1
				while b > 0:
								if b & 1:
												_A       	=      ((res % c) * (a % c)) % c

								a *= a
								b >>= 1

				return res