'''simple docstring'''




from __future__ import annotations





def 	_UpperCAmelCase       (				_UpperCamelCase       :      list[int]  )      -> list[int]:
    if not list_of_ints:
        return []

    if min(_UpperCamelCase  ) < 0:
        raise ValueError('''All numbers must be positive'''  )

    A_      =  max(len(bin(_UpperCamelCase  )[2:]  ) for x in list_of_ints  )
    return _msd_radix_sort(_UpperCamelCase,  _UpperCamelCase  )





def 	_UpperCAmelCase       (				_UpperCamelCase       :      list[int],  _UpperCamelCase       :      int  )      -> list[int]:
    if bit_position == 0 or len(_UpperCamelCase  ) in [0, 1]:
        return list_of_ints

    A_      =  []
    A_      =  []
    # Split numbers based on bit at bit_position from the right
    for number in list_of_ints:
        if (number >> (bit_position - 1)) & 1:
            # number has a one at bit bit_position
            ones.append(_UpperCamelCase  )
        else:
            # number has a zero at bit bit_position
            zeros.append(_UpperCamelCase  )

    # recursively split both lists further
    A_      =  _msd_radix_sort(_UpperCamelCase,  bit_position - 1  )
    A_      =  _msd_radix_sort(_UpperCamelCase,  bit_position - 1  )

    # recombine lists
    A_      =  zeros
    res.extend(_UpperCamelCase  )

    return res





def 	_UpperCAmelCase       (				_UpperCamelCase       :      list[int]  )      -> Optional[Any]:
    A_      =  len(_UpperCamelCase  )
    if not list_of_ints or length == 1:
        return

    if min(_UpperCamelCase  ) < 0:
        raise ValueError('''All numbers must be positive'''  )

    A_      =  max(len(bin(_UpperCamelCase  )[2:]  ) for x in list_of_ints  )
    _msd_radix_sort_inplace(_UpperCamelCase,  _UpperCamelCase,  0,  _UpperCamelCase  )





def 	_UpperCAmelCase       (				_UpperCamelCase       :      list[int],  _UpperCamelCase       :      int,  _UpperCamelCase       :      int,  _UpperCamelCase       :      int  )      -> Tuple:
    if bit_position == 0 or end_index - begin_index <= 1:
        return

    bit_position -= 1

    A_      =  begin_index
    A_      =  end_index - 1
    while i <= j:
        A_      =  False
        if not (list_of_ints[i] >> bit_position) & 1:
            # found zero at the beginning
            i += 1
            A_      =  True
        if (list_of_ints[j] >> bit_position) & 1:
            # found one at the end
            j -= 1
            A_      =  True

        if changed:
            continue

        A_  ,A_      =  list_of_ints[j], list_of_ints[i]
        j -= 1
        if j != i:
            i += 1

    _msd_radix_sort_inplace(_UpperCamelCase,  _UpperCamelCase,  _UpperCamelCase,  _UpperCamelCase  )
    _msd_radix_sort_inplace(_UpperCamelCase,  _UpperCamelCase,  _UpperCamelCase,  _UpperCamelCase  )


if __name__ == "__main__":
  import doctest

  doctest.testmod()







'''simple docstring'''




def 	_UpperCAmelCase       (				_UpperCamelCase       :      list[list[int]],  _UpperCamelCase       :      list[list[int]]  )      -> list[list[int]]:
    A_      =  []
    A_      =  len(_UpperCamelCase  )
    for i in range(_UpperCamelCase  ):
        A_      =  []
        for j in range(_UpperCamelCase  ):
            A_      =  0
            for k in range(_UpperCamelCase  ):
                A_      =  val + matrix_a[i][k] * matrix_b[k][j]
            list_a.append(_UpperCamelCase  )
        matrix_c.append(_UpperCamelCase  )
    return matrix_c





def 	_UpperCAmelCase       (				_UpperCamelCase       :      int  )      -> list[list[int]]:
    return [[int(row == column  ) for column in range(_UpperCamelCase  )] for row in range(_UpperCamelCase  )]





def 	_UpperCAmelCase       (				_UpperCamelCase       :      int  )      -> int:
    if n <= 1:
        return n
    A_      =  identity(2  )
    A_      =  [[1, 1], [1, 0]]
    A_      =  n - 1
    while n > 0:
        if n % 2 == 1:
            A_      =  multiply(_UpperCamelCase,  _UpperCamelCase  )
        A_      =  multiply(_UpperCamelCase,  _UpperCamelCase  )
        A_      =  int(n / 2  )
    return res_matrix[0][0]





def 	_UpperCAmelCase       (				_UpperCamelCase       :      int  )      -> int:
    if n <= 1:
        return n
    A_      =  0
    A_      =  1
    for _ in range(2,  n + 1  ):
        A_  ,A_      =  fiba, fiba + fiba
    return fiba





def 	_UpperCAmelCase       (				)      -> None:
    for ordinal in "0th 1st 2nd 3rd 10th 100th 1000th".split():
        A_      =  int(''''''.join(c for c in ordinal if c in '''0123456789'''  )  )  # 1000th --> 1000
        print(
            F'''{ordinal} fibonacci number using matrix exponentiation is '''
            F'''{nth_fibonacci_matrix(_UpperCamelCase  )} and using bruteforce is '''
            F'''{nth_fibonacci_bruteforce(_UpperCamelCase  )}\n'''  )
    # from timeit import timeit
    # print(timeit("nth_fibonacci_matrix(1000000)",
    #              "from main import nth_fibonacci_matrix", number=5))
    # print(timeit("nth_fibonacci_bruteforce(1000000)",
    #              "from main import nth_fibonacci_bruteforce", number=5))
    # 2.3342058970001744
    # 57.256506615000035


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  main()






