

'''simple docstring'''

from __future__ import annotations

def 			__UpperCamelCase							(		lowercase__  :					list[list[int]],   lowercase__  :					int,   lowercase__  :					int,   lowercase__  :					int | float	):






     '''simple docstring'''





     __lowercase						,       __lowercase     						=m - 1, 0
     while i >= 0 and j < n:
          if key == mat[i][j]:
               print(F'''Key {key} found at row- {i + 1} column- {j + 1}'''	)
               return
          if key < mat[i][j]:
               i -= 1
          else:
               j += 1
     print(F'''Key {key} not found'''	)

def 			__UpperCamelCase							(		):






     '''simple docstring'''





     __lowercase     						=[[2, 5, 7], [4, 8, 13], [9, 11, 15], [12, 17, 20]]
     __lowercase     						=int(input('Enter the element to be searched:'	)	)
     print(lowercase__	)
     search_in_a_sorted_matrix(lowercase__,   len(lowercase__	),   len(mat[0]	),   lowercase__	)


if __name__ == "__main__":
       import doctest

       doctest.testmod()
       main()





'''simple docstring'''

from __future__ import annotations

def 			__UpperCamelCase							(		lowercase__  :					list[int]	):






     '''simple docstring'''





     if not list_of_ints:
          return []

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

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

def 			__UpperCamelCase							(		lowercase__  :					list[int],   lowercase__  :					int	):






     '''simple docstring'''





     if bit_position == 0 or len(lowercase__	) in [0, 1]:
          return list_of_ints

     __lowercase     						=[]
     __lowercase     						=[]
     # 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(lowercase__	)
          else:
               # number has a zero at bit bit_position
               zeros.append(lowercase__	)

    # recursively split both lists further
     __lowercase     						=_msd_radix_sort(lowercase__,   bit_position - 1	)
     __lowercase     						=_msd_radix_sort(lowercase__,   bit_position - 1	)

     # recombine lists
     __lowercase     						=zeros
     res.extend(lowercase__	)

     return res

def 			__UpperCamelCase							(		lowercase__  :					list[int]	):






     '''simple docstring'''





     __lowercase     						=len(lowercase__	)
     if not list_of_ints or length == 1:
          return

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

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

def 			__UpperCamelCase							(		lowercase__  :					list[int],   lowercase__  :					int,   lowercase__  :					int,   lowercase__  :					int	):






     '''simple docstring'''





     if bit_position == 0 or end_index - begin_index <= 1:
          return

     bit_position -= 1

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

          if changed:
               continue

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

     _msd_radix_sort_inplace(lowercase__,   lowercase__,   lowercase__,   lowercase__	)
     _msd_radix_sort_inplace(lowercase__,   lowercase__,   lowercase__,   lowercase__	)


if __name__ == "__main__":
       import doctest

       doctest.testmod()


