






'''simple docstring'''



from __future__ import annotations

import math
import random
from typing import Any
class UpperCAmelCase_					:




      """simple docstring"""




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


       '''simple docstring'''

       lowercase					:   list[Any]				  =[]
       lowercase					:   int				  =0
       lowercase					:   int				  =0






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


       '''simple docstring'''

       return self.head == self.tail






      def 				A__      ( self			:		Any     ,      UpperCAmelCase			:		Optional[int]		)  ->  Any:


       '''simple docstring'''

       self.data.append(UpperCamelCase_		)
       lowercase					:   str				  =self.tail + 1






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


       '''simple docstring'''

       lowercase					:   str				  =self.data[self.head]
       lowercase					:   Tuple				  =self.head + 1
       return ret






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


       '''simple docstring'''

       return self.tail - self.head






      def 				A__      ( self			:		Tuple		)  ->  Union[str, Any]:


       '''simple docstring'''

       print(self.data		)
       print('''**************'''		)
       print(self.data[self.head : self.tail]		)





class UpperCAmelCase_					:




      """simple docstring"""




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


       '''simple docstring'''

       lowercase					:   int				  =data
       lowercase					:   MyNode | None				  =None
       lowercase					:   MyNode | None				  =None
       lowercase					:   int				  =1






      def 				A__      ( self			:		str		)  ->  int:


       '''simple docstring'''

       return self.data






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


       '''simple docstring'''

       return self.left






      def 				A__      ( self			:		Tuple		)  ->  Tuple:


       '''simple docstring'''

       return self.right






      def 				A__      ( self			:		Optional[int]		)  ->  Optional[Any]:


       '''simple docstring'''

       return self.height






      def 				A__      ( self			:		Dict     ,      UpperCAmelCase			:		Optional[Any]		)  ->  Optional[int]:


       '''simple docstring'''

       lowercase					:   Tuple				  =data






      def 				A__      ( self			:		Dict     ,      UpperCAmelCase			:		Optional[Any]		)  ->  Optional[Any]:


       '''simple docstring'''

       lowercase					:   List[Any]				  =node






      def 				A__      ( self			:		int     ,      UpperCAmelCase			:		Dict		)  ->  int:


       '''simple docstring'''

       lowercase					:   int				  =node






      def 				A__      ( self			:		Tuple     ,      UpperCAmelCase			:		Union[str, Any]		)  ->  List[str]:


       '''simple docstring'''

       lowercase					:   int				  =height





def 							lowercase_				(    __A :       List[str]			)       ->      int:



 """simple docstring"""




 if node is None:
  return 0
 return node.get_height()


def 							lowercase_				(    __A :       Union[str, Any]					,      __A :       int			)       ->      int:



 """simple docstring"""




 if a > b:
  return a
 return b


def 							lowercase_				(    __A :       Union[str, Any]			)       ->      MyNode:



 """simple docstring"""




 print('''left rotation node:'''					,      node.get_data()			)
 lowercase					:   Union[str, Any]				  =node.get_left()
 assert ret is not None
 node.set_left(ret.get_right()			)
 ret.set_right(lowerCamelCase__			)
 lowercase					:   Optional[int]				  =my_max(get_height(node.get_right()			)					,      get_height(node.get_left()			)			) + 1
 node.set_height(lowerCamelCase__			)
 lowercase					:   Optional[int]				  =my_max(get_height(ret.get_right()			)					,      get_height(ret.get_left()			)			) + 1
 ret.set_height(lowerCamelCase__			)
 return ret


def 							lowercase_				(    __A :       int			)       ->      MyNode:



 """simple docstring"""




 print('''right rotation node:'''					,      node.get_data()			)
 lowercase					:   Union[str, Any]				  =node.get_right()
 assert ret is not None
 node.set_right(ret.get_left()			)
 ret.set_left(lowerCamelCase__			)
 lowercase					:   Tuple				  =my_max(get_height(node.get_right()			)					,      get_height(node.get_left()			)			) + 1
 node.set_height(lowerCamelCase__			)
 lowercase					:   Optional[Any]				  =my_max(get_height(ret.get_right()			)					,      get_height(ret.get_left()			)			) + 1
 ret.set_height(lowerCamelCase__			)
 return ret


def 							lowercase_				(    __A :       List[str]			)       ->      MyNode:



 """simple docstring"""




 lowercase					:   Dict				  =node.get_left()
 assert left_child is not None
 node.set_left(left_rotation(lowerCamelCase__			)			)
 return right_rotation(lowerCamelCase__			)


def 							lowercase_				(    __A :       Any			)       ->      MyNode:



 """simple docstring"""




 lowercase					:   List[str]				  =node.get_right()
 assert right_child is not None
 node.set_right(right_rotation(lowerCamelCase__			)			)
 return left_rotation(lowerCamelCase__			)


def 							lowercase_				(    __A :       Optional[int]					,      __A :       Union[str, Any]			)       ->      MyNode | None:



 """simple docstring"""




 if node is None:
  return MyNode(lowerCamelCase__			)
 if data < node.get_data():
  node.set_left(insert_node(node.get_left()					,      lowerCamelCase__			)			)
  if (
      get_height(node.get_left()			) - get_height(node.get_right()			) == 2
  ):  # an unbalance detected
   lowercase					:   Optional[Any]				  =node.get_left()
   assert left_child is not None
   if (
       data < left_child.get_data()
   ):  # new node is the left child of the left child
    lowercase					:   Dict				  =right_rotation(lowerCamelCase__			)
   else:
    lowercase					:   Union[str, Any]				  =lr_rotation(lowerCamelCase__			)
 else:
  node.set_right(insert_node(node.get_right()					,      lowerCamelCase__			)			)
  if get_height(node.get_right()			) - get_height(node.get_left()			) == 2:
   lowercase					:   Any				  =node.get_right()
   assert right_child is not None
   if data < right_child.get_data():
    lowercase					:   Union[str, Any]				  =rl_rotation(lowerCamelCase__			)
   else:
    lowercase					:   Any				  =left_rotation(lowerCamelCase__			)
 lowercase					:   int				  =my_max(get_height(node.get_right()			)					,      get_height(node.get_left()			)			) + 1
 node.set_height(lowerCamelCase__			)
 return node


def 							lowercase_				(    __A :       Dict			)       ->      Any:



 """simple docstring"""




 while True:
  lowercase					:   Tuple				  =root.get_right()
  if right_child is None:
   break
  lowercase					:   List[Any]				  =right_child
 return root.get_data()


def 							lowercase_				(    __A :       Dict			)       ->      Any:



 """simple docstring"""




 while True:
  lowercase					:   Optional[int]				  =root.get_left()
  if left_child is None:
   break
  lowercase					:   List[Any]				  =left_child
 return root.get_data()


def 							lowercase_				(    __A :       List[str]					,      __A :       int			)       ->      MyNode | None:



 """simple docstring"""




 lowercase					:   int				  =root.get_left()
 lowercase					:   Tuple				  =root.get_right()
 if root.get_data() == data:
  if left_child is not None and right_child is not None:
   lowercase					:   List[Any]				  =get_left_most(lowerCamelCase__			)
   root.set_data(lowerCamelCase__			)
   root.set_right(del_node(lowerCamelCase__					,      lowerCamelCase__			)			)
  elif left_child is not None:
   lowercase					:   Tuple				  =left_child
  elif right_child is not None:
   lowercase					:   Optional[int]				  =right_child
  else:
   return None
 elif root.get_data() > data:
  if left_child is None:
   print('''No such data'''			)
   return root
  else:
   root.set_left(del_node(lowerCamelCase__					,      lowerCamelCase__			)			)
 else:  # root.get_data() < data
  if right_child is None:
   return root
  else:
   root.set_right(del_node(lowerCamelCase__					,      lowerCamelCase__			)			)

 if get_height(lowerCamelCase__			) - get_height(lowerCamelCase__			) == 2:
  assert right_child is not None
  if get_height(right_child.get_right()			) > get_height(right_child.get_left()			):
   lowercase					:   int				  =left_rotation(lowerCamelCase__			)
  else:
   lowercase					:   Dict				  =rl_rotation(lowerCamelCase__			)
 elif get_height(lowerCamelCase__			) - get_height(lowerCamelCase__			) == -2:
  assert left_child is not None
  if get_height(left_child.get_left()			) > get_height(left_child.get_right()			):
   lowercase					:   Optional[int]				  =right_rotation(lowerCamelCase__			)
  else:
   lowercase					:   int				  =lr_rotation(lowerCamelCase__			)
 lowercase					:   int				  =my_max(get_height(root.get_right()			)					,      get_height(root.get_left()			)			) + 1
 root.set_height(lowerCamelCase__			)
 return root
class UpperCAmelCase_					:




      """simple docstring"""




      def __init__( self			:		Optional[Any]		)  ->  Tuple:


       '''simple docstring'''

       lowercase					:   MyNode | None				  =None






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


       '''simple docstring'''

       return get_height(self.root		)






      def 				A__      ( self			:		str     ,      UpperCAmelCase			:		str		)  ->  Tuple:


       '''simple docstring'''

       print('''insert:''' + str(UpperCamelCase_		)		)
       lowercase					:   List[Any]				  =insert_node(self.root     ,      UpperCamelCase_		)






      def 				A__      ( self			:		Any     ,      UpperCAmelCase			:		Union[str, Any]		)  ->  Any:


       '''simple docstring'''

       print('''delete:''' + str(UpperCamelCase_		)		)
       if self.root is None:
        print('''Tree is empty!'''		)
        return
       lowercase					:   List[Any]				  =del_node(self.root     ,      UpperCamelCase_		)






      def __str__( self			:		Dict     ,      )  ->  int:  # a level traversale, gives a more intuitive look on the tree


       '''simple docstring'''

       lowercase					:   List[str]				  =""
       lowercase					:   int				  =MyQueue()
       q.push(self.root		)
       lowercase					:   Optional[Any]				  =self.get_height()
       if layer == 0:
        return output
       lowercase					:   Union[str, Any]				  =0
       while not q.is_empty():
        lowercase					:   List[Any]				  =q.pop()
        lowercase					:   Optional[Any]				  =" " * int(math.pow(2     ,      layer - 1		)		)
        output += space
        if node is None:
         output += "*"
         q.push(UpperCamelCase_		)
         q.push(UpperCamelCase_		)
        else:
         output += str(node.get_data()		)
         q.push(node.get_left()		)
         q.push(node.get_right()		)
        output += space
        lowercase					:   List[Any]				  =cnt + 1
        for i in range(100		):
         if cnt == math.pow(2     ,      UpperCamelCase_		) - 1:
          lowercase					:   Dict				  =layer - 1
          if layer == 0:
           output += "\n*************************************"
           return output
          output += "\n"
          break
       output += "\n*************************************"
       return output





def 							lowercase_				(    )       ->      None:



 """simple docstring"""




 import doctest

 doctest.testmod()


if __name__ == "__main__":
     _test()
     SCREAMING_SNAKE_CASE						=	AVLtree()
     SCREAMING_SNAKE_CASE						=	list(range(10))
     random.shuffle(lst)
     for i in lst:
          t.insert(i)
          print(str(t))
     random.shuffle(lst)
     for i in lst:
          t.del_node(i)
          print(str(t))











'''simple docstring'''



from __future__ import annotations

import math


def 							lowercase_				(    __A :       float					,      __A :       int			)       ->      float:



 """simple docstring"""




 lowercase					:   str				  =u
 for i in range(1					,      __A			):
  lowercase					:   Any				  =temp * (u - i)
 return temp


def 							lowercase_				(    )       ->      None:



 """simple docstring"""




 lowercase					:   List[str]				  =int(input('''enter the numbers of values: '''			)			)
 lowercase					:   list[list[float]]				  =[]
 for _ in range(__A			):
  y.append([]			)
 for i in range(__A			):
  for j in range(__A			):
   y[i].append(__A			)
   lowercase					:   List[Any]				  =0

 print('''enter the values of parameters in a list: '''			)
 lowercase					:   Optional[int]				  =list(map(__A					,      input().split()			)			)

 print('''enter the values of corresponding parameters: '''			)
 for i in range(__A			):
  lowercase					:   str				  =float(input()			)

 lowercase					:   int				  =int(input('''enter the value to interpolate: '''			)			)
 lowercase					:   Union[str, Any]				  =(value - x[0]) / (x[1] - x[0])

 # for calculating forward difference table

 for i in range(1					,      __A			):
  for j in range(n - i			):
   lowercase					:   str				  =y[j + 1][i - 1] - y[j][i - 1]

 lowercase					:   Any				  =y[0][0]
 for i in range(1					,      __A			):
  summ += (ucal(__A					,      __A			) * y[0][i]) / math.factorial(__A			)

 print(F'the value at {value} is {summ}'			)


if __name__ == "__main__":
      main()



