






"""simple docstring"""





from collections.abc import Iterable
from typing import Any
class    __lowerCamelCase    :

   def __init__(					self ,				snake_case_ = None      )		->       Tuple:
       UpperCamelCase__         =    value
       UpperCamelCase__         =    None  # Added in order to delete a node easier
       UpperCamelCase__         =    None
       UpperCamelCase__         =    None







   def __repr__(					self      )		->       str:
       from pprint import pformat

       if self.left is None and self.right is None:
           return str(self.value      )
       return pformat({F'{self.value}': (self.left, self.right)} ,				indent=1      )







class    __lowerCamelCase    :

   def __init__(					self ,				snake_case_ = None      )		->       List[str]:
       UpperCamelCase__         =    root

   def __str__(					self      )		->       str:
       return str(self.root      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       None:
       if new_children is not None:  # reset its kids
           UpperCamelCase__         =    node.parent
       if node.parent is not None:  # reset its parent
           if self.is_right(snake_case_      ):  # If it is the right children
               UpperCamelCase__         =    new_children
           else:
               UpperCamelCase__         =    new_children
       else:
           UpperCamelCase__         =    new_children

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       bool:
       if node.parent and node.parent.right:
           return node == node.parent.right
       return False

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       bool:
       return self.root is None

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       None:
       UpperCamelCase__         =    Node(snake_case_      )  # create a new Node
       if self.empty():  # if Tree is empty
           UpperCamelCase__         =    new_node  # set its root
       else:  # Tree is not empty
           UpperCamelCase__         =    self.root  # from root
           if parent_node is None:
               return
           while True:  # While we don't get to a leaf
               if value < parent_node.value:  # We go left
                   if parent_node.left is None:
                       UpperCamelCase__         =    new_node  # We insert the new node in a leaf
                       break
                   else:
                       UpperCamelCase__         =    parent_node.left
               else:
                   if parent_node.right is None:
                       UpperCamelCase__         =    new_node
                       break
                   else:
                       UpperCamelCase__         =    parent_node.right
           UpperCamelCase__         =    parent_node

   def 						SCREAMING_SNAKE_CASE__ (					self ,				*snake_case_      )		->       None:
       for value in values:
           self.__insert(snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       Node | None:
       if self.empty():
           raise IndexError('Warning: Tree is empty! please use another.'      )
       else:
           UpperCamelCase__         =    self.root
           # use lazy evaluation here to avoid NoneType Attribute error
           while node is not None and node.value is not value:
               UpperCamelCase__         =    node.left if value < node.value else node.right
           return node

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ = None      )		->       Node | None:
       if node is None:
           if self.root is None:
               return None
           UpperCamelCase__         =    self.root

       if not self.empty():
           while node.right is not None:
               UpperCamelCase__         =    node.right
       return node

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ = None      )		->       Node | None:
       if node is None:
           UpperCamelCase__         =    self.root
       if self.root is None:
           return None
       if not self.empty():
           UpperCamelCase__         =    self.root
           while node.left is not None:
               UpperCamelCase__         =    node.left
       return node

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       None:
       UpperCamelCase__         =    self.search(snake_case_      )  # Look for the node with that label
       if node is not None:
           if node.left is None and node.right is None:  # If it has no children
               self.__reassign_nodes(snake_case_ ,				snake_case_      )
           elif node.left is None:  # Has only right children
               self.__reassign_nodes(snake_case_ ,				node.right      )
           elif node.right is None:  # Has only left children
               self.__reassign_nodes(snake_case_ ,				node.left      )
           else:
               UpperCamelCase__         =    self.get_max(
                   node.left      )  # Gets the max value of the left branch
               self.remove(tmp_node.value      )  # type: ignore
               UpperCamelCase__         =    (
                   tmp_node.value  # type: ignore
               )  # Assigns the value to the node to delete and keep tree structure

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       Iterable:
       if node is not None:
           yield node  # Preorder Traversal
           yield from self.preorder_traverse(node.left      )
           yield from self.preorder_traverse(node.right      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_=None      )		->       Any:
       if traversal_function is None:
           return self.preorder_traverse(self.root      )
       else:
           return traversal_function(self.root      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       None:
       if node:
           self.inorder(snake_case_ ,				node.left      )
           arr.append(node.value      )
           self.inorder(snake_case_ ,				node.right      )







   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       int:
       UpperCamelCase__         =    []
       self.inorder(snake_case_ ,				snake_case_      )  # append all values to list using inorder traversal
       return arr[k - 1]







def   lowerCAmelCase_( SCREAMING_SNAKE_CASE					)					->	list[Node]:
    """simple docstring"""

    UpperCamelCase__         =    []
    if curr_node is not None:
        UpperCamelCase__         =    postorder(curr_node.left					) + postorder(curr_node.right					) + [curr_node]
    return node_list







def   lowerCAmelCase_( )					->	None:
    """simple docstring"""

    UpperCamelCase__         =    (8, 3, 6, 1, 10, 14, 13, 4, 7)
    UpperCamelCase__         =    BinarySearchTree()
    for i in testlist:
        t.insert(SCREAMING_SNAKE_CASE					)

    # Prints all the elements of the list in order traversal
    print(SCREAMING_SNAKE_CASE					)

    if t.search(6					) is not None:
        print('The value 6 exists'					)
    else:
        print('The value 6 doesn\'t exist'					)

    if t.search(-1					) is not None:
        print('The value -1 exists'					)
    else:
        print('The value -1 doesn\'t exist'					)

    if not t.empty():
        print('Max Value: ' ,	t.get_max().value					)  # type: ignore
        print('Min Value: ' ,	t.get_min().value					)  # type: ignore

    for i in testlist:
        t.remove(SCREAMING_SNAKE_CASE					)
        print(SCREAMING_SNAKE_CASE					)


if __name__ == "__main__":
  import doctest

  doctest.testmod(verbose=True)












"""simple docstring"""





def   lowerCAmelCase_( SCREAMING_SNAKE_CASE = 50_00_00_00					)					->	int:
    """simple docstring"""

    UpperCamelCase__         =    set()
    UpperCamelCase__         =    int((limit - 24) ** (1 / 2)					)

    UpperCamelCase__         =    set(range(3 ,	prime_square_limit + 1 ,	2					)					)
    primes.add(2					)
    for p in range(3 ,	prime_square_limit + 1 ,	2					):
        if p not in primes:
            continue
        primes.difference_update(set(range(p * p ,	prime_square_limit + 1 ,	SCREAMING_SNAKE_CASE					)					)					)

    for primea in primes:
        UpperCamelCase__         =    primea * primea
        for primea in primes:
            UpperCamelCase__         =    primea * primea * primea
            if square + cube >= limit - 16:
                break
            for primea in primes:
                UpperCamelCase__         =    primea * primea * primea * primea
                UpperCamelCase__         =    square + cube + tetr
                if total >= limit:
                    break
                ret.add(SCREAMING_SNAKE_CASE					)

    return len(SCREAMING_SNAKE_CASE					)


if __name__ == "__main__":
  print(F"""{solution() = }""")




