


def 			_a  (				):







 """simple docstring"""



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


__UpperCamelCase       :       Any						       =				generate_large_matrix()
__UpperCamelCase       :       List[Any]						       =				(
    [[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 			_a  (				SCREAMING_SNAKE_CASE	:				List[Any]     ):







 """simple docstring"""



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

def 			_a  (				SCREAMING_SNAKE_CASE	:				List[str]     ):







 """simple docstring"""



 UpperCamelCase__					:    List[Any]          =   0
 UpperCamelCase__					:    List[str]          =   len(lowerCamelCase_     ) - 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:
  UpperCamelCase__					:    int          =   (left + right) // 2
  UpperCamelCase__					:    int          =   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:
   UpperCamelCase__					:    Union[str, Any]          =   mid + 1
  else:
   UpperCamelCase__					:    int          =   mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
 return len(lowerCamelCase_     )

def 			_a  (				SCREAMING_SNAKE_CASE	:				Any     ):







 """simple docstring"""



 UpperCamelCase__					:    Dict          =   0
 UpperCamelCase__					:    Tuple          =   len(grid[0]     )

 for i in range(len(lowerCamelCase_     )     ):
  UpperCamelCase__					:    Dict          =   find_negative_index(grid[i][:bound]     )
  total += bound
 return (len(lowerCamelCase_     ) * len(grid[0]     )) - total

def 			_a  (				SCREAMING_SNAKE_CASE	:				Union[str, Any]     ):







 """simple docstring"""



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

def 			_a  (				SCREAMING_SNAKE_CASE	:				List[str]     ):







 """simple docstring"""



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

def 			_a  (				):







 """simple docstring"""



 from timeit import timeit

 print('''Running benchmarks'''     )
 UpperCamelCase__					:    Optional[int]          =   (
     '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
 ):
  UpperCamelCase__					:    Any          =   timeit(F"{func}(grid=grid)"    , setup=lowerCamelCase_    , number=500     )
  print(F"{func}() took {time:0.4f} seconds"     )


if __name__ == "__main__":
      import doctest

      doctest.testmod()
      benchmark()






__UpperCamelCase       :       List[Any]						       =				256
# Modulus to hash a string
__UpperCamelCase       :       Union[str, Any]						       =				100_0003

def 			_a  (				SCREAMING_SNAKE_CASE	:				str    , SCREAMING_SNAKE_CASE	:				str     ):







 """simple docstring"""



 UpperCamelCase__					:    Optional[int]          =   len(SCREAMING_SNAKE_CASE     )
 UpperCamelCase__					:    List[Any]          =   len(SCREAMING_SNAKE_CASE     )
 if p_len > t_len:
  return False

 UpperCamelCase__					:    Any          =   0
 UpperCamelCase__					:    str          =   0
 UpperCamelCase__					:    List[Any]          =   1

 # Calculating the hash of pattern and substring of text
 for i in range(SCREAMING_SNAKE_CASE     ):
  UpperCamelCase__					:    Any          =   (ord(pattern[i]     ) + p_hash * alphabet_size) % modulus
  UpperCamelCase__					:    List[str]          =   (ord(text[i]     ) + text_hash * alphabet_size) % modulus
  if i == p_len - 1:
   continue
  UpperCamelCase__					:    Dict          =   (modulus_power * alphabet_size) % modulus

 for i in range(0    , t_len - p_len + 1     ):
  if text_hash == p_hash and text[i : i + p_len] == pattern:
   return True
  if i == t_len - p_len:
   continue
  # Calculate the https://en.wikipedia.org/wiki/Rolling_hash
  UpperCamelCase__					:    Optional[int]          =   (
      (text_hash - ord(text[i]     ) * modulus_power) * alphabet_size
      + ord(text[i + p_len]     )
  ) % modulus
 return False

def 			_a  (				):







 """simple docstring"""



 UpperCamelCase__					:    Tuple          =   '''abc1abc12'''
 UpperCamelCase__					:    Dict          =   '''alskfjaldsabc1abc1abc12k23adsfabcabc'''
 UpperCamelCase__					:    List[str]          =   '''alskfjaldsk23adsfabcabc'''
 assert rabin_karp(SCREAMING_SNAKE_CASE    , SCREAMING_SNAKE_CASE     ) and not rabin_karp(SCREAMING_SNAKE_CASE    , SCREAMING_SNAKE_CASE     )

 # Test 2)
 UpperCamelCase__					:    Optional[int]          =   '''ABABX'''
 UpperCamelCase__					:    int          =   '''ABABZABABYABABX'''
 assert rabin_karp(SCREAMING_SNAKE_CASE    , SCREAMING_SNAKE_CASE     )

 # Test 3)
 UpperCamelCase__					:    int          =   '''AAAB'''
 UpperCamelCase__					:    str          =   '''ABAAAAAB'''
 assert rabin_karp(SCREAMING_SNAKE_CASE    , SCREAMING_SNAKE_CASE     )

 # Test 4)
 UpperCamelCase__					:    Union[str, Any]          =   '''abcdabcy'''
 UpperCamelCase__					:    List[str]          =   '''abcxabcdabxabcdabcdabcy'''
 assert rabin_karp(SCREAMING_SNAKE_CASE    , SCREAMING_SNAKE_CASE     )

 # Test 5)
 UpperCamelCase__					:    Tuple          =   '''Lü'''
 UpperCamelCase__					:    Any          =   '''Lüsai'''
 assert rabin_karp(SCREAMING_SNAKE_CASE    , SCREAMING_SNAKE_CASE     )
 UpperCamelCase__					:    Dict          =   '''Lue'''
 assert not rabin_karp(SCREAMING_SNAKE_CASE    , SCREAMING_SNAKE_CASE     )
 print('''Success.'''     )


if __name__ == "__main__":
       test_rabin_karp()


