from __future__ import annotations

import math



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: list				,  __UpperCamelCase					: list			)							->      list:







  """simple docstring"""





  if len(__UpperCamelCase			) != 2 or len(a[0]			) != 2 or len(__UpperCamelCase			) != 2 or len(b[0]			) != 2:
    raise Exception("""Matrices are not 2x2"""			)
  SCREAMING_SNAKE_CASE__    							=   [
      [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
      [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]],
  ]
  return new_matrix



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: list				,  __UpperCamelCase					: list			)							->      Optional[int]:







  """simple docstring"""





  return [
      [matrix_a[row][col] + matrix_b[row][col] for col in range(len(matrix_a[row]			)			)]
      for row in range(len(__UpperCamelCase			)			)
  ]



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: list				,  __UpperCamelCase					: list			)							->      List[str]:







  """simple docstring"""





  return [
      [matrix_a[row][col] - matrix_b[row][col] for col in range(len(matrix_a[row]			)			)]
      for row in range(len(__UpperCamelCase			)			)
  ]



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: list			)							->      tuple[list, list, list, list]:







  """simple docstring"""





  if len(__UpperCamelCase			) % 2 != 0 or len(a[0]			) % 2 != 0:
    raise Exception("""Odd matrices are not supported!"""			)

  SCREAMING_SNAKE_CASE__    							=   len(__UpperCamelCase			)
  SCREAMING_SNAKE_CASE__    							=   matrix_length // 2

  SCREAMING_SNAKE_CASE__    							=   [[a[i][j] for j in range(__UpperCamelCase				,  __UpperCamelCase			)] for i in range(__UpperCamelCase			)]
  SCREAMING_SNAKE_CASE__    							=   [
      [a[i][j] for j in range(__UpperCamelCase				,  __UpperCamelCase			)] for i in range(__UpperCamelCase				,  __UpperCamelCase			)
  ]

  SCREAMING_SNAKE_CASE__    							=   [[a[i][j] for j in range(__UpperCamelCase			)] for i in range(__UpperCamelCase			)]
  SCREAMING_SNAKE_CASE__    							=   [[a[i][j] for j in range(__UpperCamelCase			)] for i in range(__UpperCamelCase				,  __UpperCamelCase			)]

  return top_left, top_right, bot_left, bot_right



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: list			)							->      tuple[int, int]:







  """simple docstring"""





  return len(__UpperCamelCase			), len(matrix[0]			)



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: list			)							->      None:







  """simple docstring"""





  print("""\n""".join(str(__UpperCamelCase			) for line in matrix			)			)



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: list				,  __UpperCamelCase					: list			)							->      list:







  """simple docstring"""





  if matrix_dimensions(__UpperCamelCase			) == (2, 2):
    return default_matrix_multiplication(__UpperCamelCase				,  __UpperCamelCase			)

  SCREAMING_SNAKE_CASE__							,  SCREAMING_SNAKE_CASE__							,  SCREAMING_SNAKE_CASE__							,  SCREAMING_SNAKE_CASE__    							=   split_matrix(__UpperCamelCase			)
  SCREAMING_SNAKE_CASE__							,  SCREAMING_SNAKE_CASE__							,  SCREAMING_SNAKE_CASE__							,  SCREAMING_SNAKE_CASE__    							=   split_matrix(__UpperCamelCase			)

  SCREAMING_SNAKE_CASE__    							=   actual_strassen(__UpperCamelCase				,  matrix_subtraction(__UpperCamelCase				,  __UpperCamelCase			)			)
  SCREAMING_SNAKE_CASE__    							=   actual_strassen(matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)				,  __UpperCamelCase			)
  SCREAMING_SNAKE_CASE__    							=   actual_strassen(matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)				,  __UpperCamelCase			)
  SCREAMING_SNAKE_CASE__    							=   actual_strassen(__UpperCamelCase				,  matrix_subtraction(__UpperCamelCase				,  __UpperCamelCase			)			)
  SCREAMING_SNAKE_CASE__    							=   actual_strassen(matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)				,  matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)			)
  SCREAMING_SNAKE_CASE__    							=   actual_strassen(matrix_subtraction(__UpperCamelCase				,  __UpperCamelCase			)				,  matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)			)
  SCREAMING_SNAKE_CASE__    							=   actual_strassen(matrix_subtraction(__UpperCamelCase				,  __UpperCamelCase			)				,  matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)			)

  SCREAMING_SNAKE_CASE__    							=   matrix_addition(matrix_subtraction(matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)				,  __UpperCamelCase			)				,  __UpperCamelCase			)
  SCREAMING_SNAKE_CASE__    							=   matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)
  SCREAMING_SNAKE_CASE__    							=   matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)
  SCREAMING_SNAKE_CASE__    							=   matrix_subtraction(matrix_subtraction(matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)				,  __UpperCamelCase			)				,  __UpperCamelCase			)

  # construct the new matrix from our 4 quadrants
  SCREAMING_SNAKE_CASE__    							=   []
  for i in range(len(__UpperCamelCase			)			):
    new_matrix.append(top_left[i] + top_right[i]			)
  for i in range(len(__UpperCamelCase			)			):
    new_matrix.append(bot_left[i] + bot_right[i]			)
  return new_matrix



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: list				,  __UpperCamelCase					: list			)							->      list:







  """simple docstring"""





  if matrix_dimensions(__UpperCamelCase			)[1] != matrix_dimensions(__UpperCamelCase			)[0]:
    SCREAMING_SNAKE_CASE__    							=   (
        """Unable to multiply these matrices, please check the dimensions.\n"""
        f"""Matrix A: {matrixa}\n"""
        f"""Matrix B: {matrixa}"""
    )
    raise Exception(__UpperCamelCase			)
  SCREAMING_SNAKE_CASE__    							=   matrix_dimensions(__UpperCamelCase			)
  SCREAMING_SNAKE_CASE__    							=   matrix_dimensions(__UpperCamelCase			)

  if dimensiona[0] == dimensiona[1] and dimensiona[0] == dimensiona[1]:
    return [matrixa, matrixa]

  SCREAMING_SNAKE_CASE__    							=   max(*__UpperCamelCase				,  *__UpperCamelCase			)
  SCREAMING_SNAKE_CASE__    							=   int(math.pow(2				,  math.ceil(math.loga(__UpperCamelCase			)			)			)			)
  SCREAMING_SNAKE_CASE__    							=   matrixa
  SCREAMING_SNAKE_CASE__    							=   matrixa

  # Adding zeros to the matrices so that the arrays dimensions are the same and also
  # power of 2
  for i in range(0				,  __UpperCamelCase			):
    if i < dimensiona[0]:
      for _ in range(dimensiona[1]				,  __UpperCamelCase			):
        new_matrixa[i].append(0			)
    else:
      new_matrixa.append([0] * maxim			)
    if i < dimensiona[0]:
      for _ in range(dimensiona[1]				,  __UpperCamelCase			):
        new_matrixa[i].append(0			)
    else:
      new_matrixa.append([0] * maxim			)

  SCREAMING_SNAKE_CASE__    							=   actual_strassen(__UpperCamelCase				,  __UpperCamelCase			)

  # Removing the additional zeros
  for i in range(0				,  __UpperCamelCase			):
    if i < dimensiona[0]:
      for _ in range(dimensiona[1]				,  __UpperCamelCase			):
        final_matrix[i].pop()
    else:
      final_matrix.pop()
  return final_matrix


if __name__ == "__main__":
   __lowerCamelCase    :				int							     =	[
       [2, 3, 4, 5],
       [6, 4, 3, 1],
       [2, 3, 6, 7],
       [3, 1, 2, 4],
       [2, 3, 4, 5],
       [6, 4, 3, 1],
       [2, 3, 6, 7],
       [3, 1, 2, 4],
       [2, 3, 4, 5],
       [6, 2, 3, 1],
   ]
   __lowerCamelCase    :				Tuple							     =	[[0, 2, 1, 1], [16, 2, 3, 3], [2, 2, 7, 7], [13, 11, 22, 4]]
   print(strassen(matrixa, matrixa))

from collections.abc import Iterator, MutableMapping
from dataclasses import dataclass
from typing import Generic, TypeVar

__lowerCamelCase    :				List[str]							     =	TypeVar('''KEY''')
__lowerCamelCase    :				int							     =	TypeVar('''VAL''')







@dataclass(frozen=lowerCamelCase_     ,	slots=lowerCamelCase_	)
class __snake_case       (		Generic[KEY, VAL]	):
   lowerCAmelCase_														=							42
   lowerCAmelCase_														=							42







class __snake_case       (		_Item	):




   def __init__(					self    :       List[Any]   ):



     """simple docstring"""






     super().__init__(_lowercase ,			_lowercase   )




   def __bool__(					self    :       List[str]   ):



     """simple docstring"""






     return False





__lowerCamelCase    :				str							     =	_DeletedItem()







class __snake_case       (		MutableMapping[KEY, VAL]	):




   def __init__(					self    :       Optional[int] ,			_lowercase    :       int = 8 ,			_lowercase    :       float = 0.75   ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__    							=   initial_block_size
     SCREAMING_SNAKE_CASE__    							=   [None] * initial_block_size
     assert 0.0 < capacity_factor < 1.0
     SCREAMING_SNAKE_CASE__    							=   capacity_factor
     SCREAMING_SNAKE_CASE__    							=   0




   def 			__a		(					self    :       Union[str, Any] ,			_lowercase    :       KEY   ):



     """simple docstring"""






     return hash(_lowercase   ) % len(self._buckets   )




   def 			__a		(					self    :       List[str] ,			_lowercase    :       int   ):



     """simple docstring"""






     return (ind + 1) % len(self._buckets   )




   def 			__a		(					self    :       Union[str, Any] ,			_lowercase    :       int ,			_lowercase    :       KEY ,			_lowercase    :       VAL   ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__    							=   self._buckets[ind]
     if not stored:
       SCREAMING_SNAKE_CASE__    							=   _Item(_lowercase ,			_lowercase   )
       self._len += 1
       return True
     elif stored.key == key:
       SCREAMING_SNAKE_CASE__    							=   _Item(_lowercase ,			_lowercase   )
       return True
     else:
       return False




   def 			__a		(					self    :       List[Any]   ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__    							=   len(self._buckets   ) * self._capacity_factor
     return len(self   ) >= int(_lowercase   )




   def 			__a		(					self    :       Dict   ):



     """simple docstring"""






     if len(self._buckets   ) <= self._initial_block_size:
       return False
     SCREAMING_SNAKE_CASE__    							=   len(self._buckets   ) * self._capacity_factor / 2
     return len(self   ) < limit




   def 			__a		(					self    :       List[Any] ,			_lowercase    :       int   ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__    							=   self._buckets
     SCREAMING_SNAKE_CASE__    							=   [None] * new_size
     SCREAMING_SNAKE_CASE__    							=   0
     for item in old_buckets:
       if item:
         self._add_item(item.key ,			item.val   )




   def 			__a		(					self    :       Tuple   ):



     """simple docstring"""






     self._resize(len(self._buckets   ) * 2   )




   def 			__a		(					self    :       Tuple   ):



     """simple docstring"""






     self._resize(len(self._buckets   ) // 2   )




   def 			__a		(					self    :       List[str] ,			_lowercase    :       KEY   ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__    							=   self._get_bucket_index(_lowercase   )
     for _ in range(len(self._buckets   )   ):
       yield ind
       SCREAMING_SNAKE_CASE__    							=   self._get_next_ind(_lowercase   )




   def 			__a		(					self    :       List[str] ,			_lowercase    :       KEY ,			_lowercase    :       VAL   ):



     """simple docstring"""






     for ind in self._iterate_buckets(_lowercase   ):
       if self._try_set(_lowercase ,			_lowercase ,			_lowercase   ):
         break




   def __setitem__(					self    :       List[str] ,			_lowercase    :       KEY ,			_lowercase    :       VAL   ):



     """simple docstring"""






     if self._is_full():
       self._size_up()

     self._add_item(_lowercase ,			_lowercase   )




   def __delitem__(					self    :       Tuple ,			_lowercase    :       KEY   ):



     """simple docstring"""






     for ind in self._iterate_buckets(_lowercase   ):
       SCREAMING_SNAKE_CASE__    							=   self._buckets[ind]
       if item is None:
         raise KeyError(_lowercase   )
       if item is _deleted:
         continue
       if item.key == key:
         SCREAMING_SNAKE_CASE__    							=   _deleted
         self._len -= 1
         break
     if self._is_sparse():
       self._size_down()




   def __getitem__(					self    :       Tuple ,			_lowercase    :       KEY   ):



     """simple docstring"""






     for ind in self._iterate_buckets(_lowercase   ):
       SCREAMING_SNAKE_CASE__    							=   self._buckets[ind]
       if item is None:
         break
       if item is _deleted:
         continue
       if item.key == key:
         return item.val
     raise KeyError(_lowercase   )




   def __len__(					self    :       List[Any]   ):



     """simple docstring"""






     return self._len




   def __iter__(					self    :       List[str]   ):



     """simple docstring"""






     yield from (item.key for item in self._buckets if item)




   def __repr__(					self    :       Optional[Any]   ):



     """simple docstring"""






     SCREAMING_SNAKE_CASE__    							=   """ ,""".join(
         f"""{item.key}: {item.val}""" for item in self._buckets if item   )
     return f"""HashMap({val_string})"""
