




class       A      :
     """simple docstring"""

     class       A      :
          """simple docstring"""

          _snake_case:						Union[str, Any]  ="_prev", "_data", "_next"




          def __init__(     self	: List[str]						,	A__	: Any						,	A__	: Tuple						,	A__	: int      )					->							int:
                lowerCamelCase__   	=					link_p
                lowerCamelCase__   	=					element
                lowerCamelCase__   	=					link_n




          def 			__snake_case (     self	: List[str]      )					->							Any:
                return (
                    F""" Prev -> {self._prev is not None}, Next -> {self._next is not None}"""
                )




     def __init__(     self	: List[str]      )					->							int:
           lowerCamelCase__   	=					self._Node(A__						,	A__						,	A__      )
           lowerCamelCase__   	=					self._Node(A__						,	A__						,	A__      )
           lowerCamelCase__   	=					self._trailer
           lowerCamelCase__   	=					self._header
           lowerCamelCase__   	=					0




     def __len__(     self	: int      )					->							List[str]:
           return self._size




     def 			__snake_case (     self	: Optional[Any]      )					->							str:
           return self.__len__() == 0




     def 			__snake_case (     self	: Union[str, Any]						,	A__	: Dict						,	A__	: Optional[int]						,	A__	: Union[str, Any]      )					->							Union[str, Any]:
           # Create new_node by setting it's prev.link -> header
           # setting it's next.link -> trailer
           lowerCamelCase__   	=					self._Node(A__						,	A__						,	A__      )
           lowerCamelCase__   	=					new_node
           lowerCamelCase__   	=					new_node
           self._size += 1
           return self




     def 			__snake_case (     self	: List[Any]						,	A__	: List[str]      )					->							Tuple:
           lowerCamelCase__   	=					node._prev
           lowerCamelCase__   	=					node._next

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






class       A      (		_DoublyLinkedBase		):
     """simple docstring"""

     def 			__snake_case (     self	: int      )					->							str:
           if self.is_empty():
                 raise Exception('List is empty'      )
           return self._header._next._data




     def 			__snake_case (     self	: Optional[int]      )					->							Dict:
           if self.is_empty():
                 raise Exception('List is empty'      )
           return self._trailer._prev._data




     def 			__snake_case (     self	: int						,	A__	: Tuple      )					->							Optional[int]:
           return self._insert(self._header						,	A__						,	self._header._next      )




     def 			__snake_case (     self	: str						,	A__	: Dict      )					->							str:
           return self._insert(self._trailer._prev						,	A__						,	self._trailer      )




     def 			__snake_case (     self	: Union[str, Any]      )					->							Union[str, Any]:
           if self.is_empty():
                 raise IndexError('remove_first from empty list'      )
           return self._delete(self._header._next      )




     def 			__snake_case (     self	: List[Any]      )					->							List[Any]:
           if self.is_empty():
                 raise IndexError('remove_first from empty list'      )
           return self._delete(self._trailer._prev      )





def       lowerCAmelCase_      (	lowerCamelCase:							str    )       ->      int:


      '''simple docstring'''




      lowerCamelCase__   	=					53_81
      for x in s:
            lowerCamelCase__   	=					((hash_value << 5) + hash_value) + ord(lowerCamelCase    )
      return hash_value & 0Xffff_ffff