





'''simple docstring'''


import timeit

class 				lowerCAmelCase_						:




 def __init__(		self     ,       _lowerCAmelCase						)      ->							Dict:
     if isinstance(_lowerCAmelCase     ,       _lowerCAmelCase						):  # Initializes a matrix identical to the one provided.
         _lowerCAmelCase		     = arg
         _lowerCAmelCase		     = len(_lowerCAmelCase						)
     else:  # Initializes a square matrix of the given size and set values to zero.
         _lowerCAmelCase		     = arg
         _lowerCAmelCase		     = [[0 for _ in range(self.n						)] for _ in range(self.n						)]





 def __mul__(		self     ,       _lowerCAmelCase						)      ->							Any:
     _lowerCAmelCase		     = Matrix(self.n						)
     for i in range(self.n						):
         for j in range(self.n						):
             for k in range(self.n						):
                 matrix.t[i][j] += self.t[i][k] * b.t[k][j]
     return matrix







def 		__a(SCREAMING_SNAKE_CASE_					:   Any						,    SCREAMING_SNAKE_CASE_					:   Tuple      ):



    '''simple docstring'''





    _lowerCAmelCase		     = Matrix([[1, 0], [0, 1]]      )
    while b > 0:
        if b & 1:
            matrix *= a
        a *= a
        b >>= 1
    return matrix


def 		__a(SCREAMING_SNAKE_CASE_					:   Optional[Any]						,    SCREAMING_SNAKE_CASE_					:   int						,    SCREAMING_SNAKE_CASE_					:   Tuple      ):



    '''simple docstring'''





    if n == 1:
        return fa
    elif n == 2:
        return fa
    _lowerCAmelCase		     = Matrix([[1, 1], [1, 0]]      )
    _lowerCAmelCase		     = modular_exponentiation(SCREAMING_SNAKE_CASE_						,    n - 2      )
    return fa * matrix.t[0][0] + fa * matrix.t[0][1]


def 		__a(SCREAMING_SNAKE_CASE_					:   List[str]						,    SCREAMING_SNAKE_CASE_					:   Any						,    SCREAMING_SNAKE_CASE_					:   Any      ):



    '''simple docstring'''





    if n == 1:
        return fa
    elif n == 2:
        return fa

    _lowerCAmelCase		     = fa
    _lowerCAmelCase		     = fa
    n -= 2

    while n > 0:
        _lowerCAmelCase     ,     _lowerCAmelCase		     = fn_a + fn_a, fn_a
        n -= 1

    return fn_a


def 		__a():



    '''simple docstring'''





    _lowerCAmelCase		     = "\nfrom random import randint\nfrom __main__ import fibonacci_with_matrix_exponentiation\n"
    _lowerCAmelCase		     = "fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"
    _lowerCAmelCase		     = timeit.timeit(setup=SCREAMING_SNAKE_CASE_						,    stmt=SCREAMING_SNAKE_CASE_						,    number=100      )
    print("With matrix exponentiation the average execution time is "						,    exec_time / 100      )
    return exec_time


def 		__a():



    '''simple docstring'''





    _lowerCAmelCase		     = "\nfrom random import randint\nfrom __main__ import simple_fibonacci\n"
    _lowerCAmelCase		     = "simple_fibonacci(randint(1,70000), 1, 1)"
    _lowerCAmelCase		     = timeit.timeit(setup=SCREAMING_SNAKE_CASE_						,    stmt=SCREAMING_SNAKE_CASE_						,    number=100      )
    print(
        "Without matrix exponentiation the average execution time is "						,    exec_time / 100      )
    return exec_time


def 		__a():



    '''simple docstring'''





    matrix_exponentiation_time()
    simple_fibonacci_time()


if __name__ == "__main__":
       main()









'''simple docstring'''


from __future__ import annotations

from collections.abc import Iterable, Iterator
from typing import Any, Generic, TypeVar

_SCREAMING_SNAKE_CASE			=							TypeVar("T", bound=bool)

class 				lowerCAmelCase_						(						Generic[T]						):




 def __init__(		self     ,       _lowerCAmelCase						)      ->							None:
     _lowerCAmelCase		     = value
     _lowerCAmelCase		     = None
     _lowerCAmelCase		     = None




 @property
 def 							_snake_case				(		self						)      ->							T:
     return self._value





 @staticmethod
 def 							_snake_case				(		_lowerCAmelCase     ,       _lowerCAmelCase						)      ->							SkewNode[T] | None:
     if not roota:
         return roota

     if not roota:
         return roota

     if roota.value > roota.value:
         _lowerCAmelCase     ,     _lowerCAmelCase		     = roota, roota

     _lowerCAmelCase		     = roota
     _lowerCAmelCase		     = roota.right
     _lowerCAmelCase		     = roota.left
     _lowerCAmelCase		     = SkewNode.merge(_lowerCAmelCase     ,       _lowerCAmelCase						)

     return result







class 				lowerCAmelCase_						(						Generic[T]						):




 def __init__(		self     ,       _lowerCAmelCase = ()						)      ->							None:
     _lowerCAmelCase		     = None
     if data:
         for item in data:
             self.insert(_lowerCAmelCase						)




 def __bool__(		self						)      ->							bool:
     return self._root is not None




 def __iter__(		self						)      ->							Iterator[T]:
     _lowerCAmelCase		     = []
     while self:
         result.append(self.pop()						)

     # Pushing items back to the heap not to clear it.
     for item in result:
         self.insert(_lowerCAmelCase						)

     return iter(_lowerCAmelCase						)




 def 							_snake_case				(		self     ,       _lowerCAmelCase						)      ->							None:
     _lowerCAmelCase		     = SkewNode.merge(self._root     ,       SkewNode(_lowerCAmelCase						)						)




 def 							_snake_case				(		self						)      ->							T | None:
     _lowerCAmelCase		     = self.top()
     _lowerCAmelCase		     = (
         SkewNode.merge(self._root.left     ,       self._root.right						) if self._root else None
     )

     return result




 def 							_snake_case				(		self						)      ->							T:
     if not self._root:
         raise IndexError("Can't get top element for the empty heap."						)
     return self._root.value





 def 							_snake_case				(		self						)      ->							None:
     _lowerCAmelCase		     = None


if __name__ == "__main__":
       import doctest

       doctest.testmod()


