

class      lowerCamelCase_ :


 class      lowerCamelCase_ :
  _lowerCAmelCase									=	'''_prev''', '''_data''', '''_next'''




  def __init__(			self  ,  _UpperCAmelCase  ,  _UpperCAmelCase  ,  _UpperCAmelCase							):
    __UpperCAmelCase	:  Optional[Any]		=     link_p
    __UpperCAmelCase	:  Tuple		=     element
    __UpperCAmelCase	:  Dict		=     link_n




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




 def __init__(			self							):
   __UpperCAmelCase	:  Union[str, Any]		=     self._Node(_UpperCAmelCase  ,  _UpperCAmelCase  ,  _UpperCAmelCase							)
   __UpperCAmelCase	:  Dict		=     self._Node(_UpperCAmelCase  ,  _UpperCAmelCase  ,  _UpperCAmelCase							)
   __UpperCAmelCase	:  Dict		=     self._trailer
   __UpperCAmelCase	:  Optional[int]		=     self._header
   __UpperCAmelCase	:  List[str]		=     0




 def __len__(			self							):
   return self._size




 def     a       (			self							):
   return self.__len__() == 0




 def     a       (			self  ,  _UpperCAmelCase  ,  _UpperCAmelCase  ,  _UpperCAmelCase							):
   # Create new_node by setting it's prev.link -> header
   # setting it's next.link -> trailer
   __UpperCAmelCase	:  Union[str, Any]		=     self._Node(_UpperCAmelCase  ,  _UpperCAmelCase  ,  _UpperCAmelCase							)
   __UpperCAmelCase	:  Union[str, Any]		=     new_node
   __UpperCAmelCase	:  Tuple		=     new_node
   self._size += 1
   return self




 def     a       (			self  ,  _UpperCAmelCase							):
   __UpperCAmelCase	:  Optional[Any]		=     node._prev
   __UpperCAmelCase	:  Dict		=     node._next

   __UpperCAmelCase	:  Optional[int]		=     successor
   __UpperCAmelCase	:  Optional[int]		=     predecessor
   self._size -= 1
   __UpperCAmelCase	:  List[Any]		=     node._data
   __UpperCAmelCase	:  int		=     None
   del node
   return temp



class      lowerCamelCase_ (			_DoublyLinkedBase):




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




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




 def     a       (			self  ,  _UpperCAmelCase							):
   return self._insert(self._header  ,  _UpperCAmelCase  ,  self._header._next							)




 def     a       (			self  ,  _UpperCAmelCase							):
   return self._insert(self._trailer._prev  ,  _UpperCAmelCase  ,  self._trailer							)




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




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









'''simple docstring'''



def       _a      (		_lowercase   :      str    ):





     '''simple docstring'''






     __UpperCAmelCase      :					Union[str, Any]    				=     5381
     for x in s:
          __UpperCAmelCase      :					Union[str, Any]    				=     ((hash_value << 5) + hash_value) + ord(_lowercase    )
     return hash_value & 0XFFFFFFFF