





'''simple docstring'''






def        UpperCamelCase__		(						)				->			list[list[int]]:
 '''simple docstring'''






 return [list(range(10_00 - i		,       -10_00 - i		,       -1      )      ) for i in range(10_00      )]


A_		:  Any		 =						generate_large_matrix()
A_		:  str		 =						(
    [[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]],
    [[3, 2], [1, 0]],
    [[7, 7, 6]],
    [[7, 7, 6], [-1, -2, -3]],
    grid,
)



def        UpperCamelCase__		(						__magic_name__  :   list[list[int]]      )				->			None:
 '''simple docstring'''






 assert all(row == sorted(__magic_name__		,       reverse=__magic_name__      ) for row in grid      )
 assert all(list(__magic_name__      ) == sorted(__magic_name__		,       reverse=__magic_name__      ) for col in zip(*__magic_name__      )      )



def        UpperCamelCase__		(						__magic_name__  :   list[int]      )				->			int:
 '''simple docstring'''






 snake_case__     :					Dict    =  0
 snake_case__     :					Tuple    =  len(__magic_name__      ) - 1

 # Edge cases such as no values or all numbers are negative.
 if not array or array[0] < 0:
  return 0

 while right + 1 > left:
  snake_case__     :					Optional[Any]    =  (left + right) // 2
  snake_case__     :					List[Any]    =  array[mid]

  # Num must be negative and the index must be greater than or equal to 0.
  if num < 0 and array[mid - 1] >= 0:
   return mid

  if num >= 0:
   snake_case__     :					str    =  mid + 1
  else:
   snake_case__     :					str    =  mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
 return len(__magic_name__      )



def        UpperCamelCase__		(						__magic_name__  :   list[list[int]]      )				->			int:
 '''simple docstring'''






 snake_case__     :					Dict    =  0
 snake_case__     :					Any    =  len(grid[0]      )

 for i in range(len(__magic_name__      )      ):
  snake_case__     :					int    =  find_negative_index(grid[i][:bound]      )
  total += bound
 return (len(__magic_name__      ) * len(grid[0]      )) - total



def        UpperCamelCase__		(						__magic_name__  :   list[list[int]]      )				->			int:
 '''simple docstring'''






 return len([number for row in grid for number in row if number < 0]      )



def        UpperCamelCase__		(						__magic_name__  :   list[list[int]]      )				->			int:
 '''simple docstring'''






 snake_case__     :					List[str]    =  0
 for row in grid:
  for i, number in enumerate(__magic_name__      ):
   if number < 0:
    total += len(__magic_name__      ) - i
    break
 return total



def        UpperCamelCase__		(						)				->			None:
 '''simple docstring'''






 from timeit import timeit

 print("""Running benchmarks"""      )
 snake_case__     :					Tuple    =  (
     """from __main__ import count_negatives_binary_search, """
     """count_negatives_brute_force, count_negatives_brute_force_with_break, grid"""
 )
 for func in (
     "count_negatives_binary_search",  # took 0.7727 seconds
     "count_negatives_brute_force_with_break",  # took 4.6505 seconds
     "count_negatives_brute_force",  # took 12.8160 seconds
 ):
  snake_case__     :					Union[str, Any]    =  timeit(f"{func}(grid=grid)"		,       setup=__magic_name__		,       number=5_00      )
  print(f"{func}() took {time:0.4f} seconds"      )


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    benchmark()











class     A     :
			'''simple docstring'''




			def __init__(     self  :       Optional[int]  )      ->      Dict:







					"""simple docstring"""






					A__     =  {}






			def   a_			(     self  :       Any  )      ->      None:







					"""simple docstring"""






					print(self.vertex  )
					for i in self.vertex:
							print(__lowerCAmelCase				,      """ -> """				,      """ -> """.join([str(__lowerCAmelCase  ) for j in self.vertex[i]]  )  )






			def   a_			(     self  :       Optional[int]				,      __lowerCAmelCase  :       int				,      __lowerCAmelCase  :       int  )      ->      None:







					"""simple docstring"""






					if from_vertex in self.vertex:
							self.vertex[from_vertex].append(__lowerCAmelCase  )
					else:
							# else make a new vertex
							A__     =  [to_vertex]






			def   a_			(     self  :       List[str]  )      ->      None:







					"""simple docstring"""






					A__     =  [False] * len(self.vertex  )

					# call the recursive helper function
					for i in range(len(self.vertex  )  ):
							if not visited[i]:
									self.dfs_recursive(__lowerCAmelCase				,      __lowerCAmelCase  )







			def   a_			(     self  :       List[str]				,      __lowerCAmelCase  :       int				,      __lowerCAmelCase  :       list  )      ->      None:







					"""simple docstring"""






					A__     =  True

					print(__lowerCAmelCase				,      end=""" """  )

					# Recur for all the vertices that are adjacent to this node
					for i in self.vertex:
							if not visited[i]:
									self.dfs_recursive(__lowerCAmelCase				,      __lowerCAmelCase  )


if __name__ == "__main__":
					A       :   Tuple					= Graph()
					g.add_edge(0, 1)
					g.add_edge(0, 2)
					g.add_edge(1, 2)
					g.add_edge(2, 0)
					g.add_edge(2, 3)
					g.add_edge(3, 3)

					g.print_graph()
					print('''DFS:''')
					g.dfs()

					# OUTPUT:
					# 0  ->  1 -> 2
					# 1  ->  2
					# 2  ->  0 -> 3
					# 3  ->  3
					# DFS:
					#  0 1 2 3



