"""simple docstring"""


import functools
import logging
import os
import sys
import threading
from logging import (
    CRITICAL,  # NOQA
    DEBUG,  # NOQA
    ERROR,  # NOQA
    FATAL,  # NOQA
    INFO,  # NOQA
    NOTSET,  # NOQA
    WARN,  # NOQA
    WARNING,  # NOQA
)
from typing import Optional

import huggingface_hub.utils as hf_hub_utils
from tqdm import auto as tqdm_lib


a				=threading.Lock()
a				=None

a				={
    'debug': logging.DEBUG,
    'info': logging.INFO,
    'warning': logging.WARNING,
    'error': logging.ERROR,
    'critical': logging.CRITICAL,
}

a				=logging.WARNING

a				=True





def      lowerCamelCase_					(   )				->   List[Any]:




						'''simple docstring'''



						lowerCamelCase__   =os.getenv("TRANSFORMERS_VERBOSITY"  ,       __lowerCAmelCase							)
						if env_level_str:
												if env_level_str in log_levels:
																		return log_levels[env_level_str]
												else:
																		logging.getLogger().warning(
																		    F'''Unknown option TRANSFORMERS_VERBOSITY={env_level_str}, '''
																		    F'''has to be one of: { ', '.join(log_levels.keys()							) }'''							)
						return _default_log_level





def      lowerCamelCase_					(   )				->   str:




						'''simple docstring'''



						return __name__.split("."							)[0]





def      lowerCamelCase_					(   )				->   logging.Logger:




						'''simple docstring'''



						return logging.getLogger(_get_library_name()							)





def      lowerCamelCase_					(   )				->   None:




						'''simple docstring'''



						global _default_handler

						with _lock:
												if _default_handler:
																		# This library has already configured the library root logger.
																		return
												lowerCamelCase__   =logging.StreamHandler()  # Set sys.stderr as stream.
												lowerCamelCase__   =sys.stderr.flush

												# Apply our default configuration to the library root logger.
												lowerCamelCase__   =_get_library_root_logger()
												library_root_logger.addHandler(_default_handler							)
												library_root_logger.setLevel(_get_default_logging_level()							)
												lowerCamelCase__   =False





def      lowerCamelCase_					(   )				->   None:




						'''simple docstring'''



						global _default_handler

						with _lock:
												if not _default_handler:
																		return

												lowerCamelCase__   =_get_library_root_logger()
												library_root_logger.removeHandler(_default_handler							)
												library_root_logger.setLevel(logging.NOTSET							)
												lowerCamelCase__   =None





def      lowerCamelCase_					(   )				->   Tuple:




						'''simple docstring'''



						return log_levels





def      lowerCamelCase_					(   __lowerCAmelCase = None							)				->   logging.Logger:




						'''simple docstring'''



						if name is None:
												lowerCamelCase__   =_get_library_name()

						_configure_library_root_logger()
						return logging.getLogger(__lowerCAmelCase							)





def      lowerCamelCase_					(   )				->   int:




						'''simple docstring'''



						_configure_library_root_logger()
						return _get_library_root_logger().getEffectiveLevel()





def      lowerCamelCase_					(   __lowerCAmelCase							)				->   None:




						'''simple docstring'''



						_configure_library_root_logger()
						_get_library_root_logger().setLevel(__lowerCAmelCase							)





def      lowerCamelCase_					(   )				->   List[Any]:




						'''simple docstring'''



						return set_verbosity(__lowerCAmelCase							)





def      lowerCamelCase_					(   )				->   Any:




						'''simple docstring'''



						return set_verbosity(__lowerCAmelCase							)





def      lowerCamelCase_					(   )				->   Tuple:




						'''simple docstring'''



						return set_verbosity(__lowerCAmelCase							)





def      lowerCamelCase_					(   )				->   Optional[int]:




						'''simple docstring'''



						return set_verbosity(__lowerCAmelCase							)





def      lowerCamelCase_					(   )				->   None:




						'''simple docstring'''



						_configure_library_root_logger()

						assert _default_handler is not None
						_get_library_root_logger().removeHandler(_default_handler							)





def      lowerCamelCase_					(   )				->   None:




						'''simple docstring'''



						_configure_library_root_logger()

						assert _default_handler is not None
						_get_library_root_logger().addHandler(_default_handler							)





def      lowerCamelCase_					(   __lowerCAmelCase							)				->   None:




						'''simple docstring'''



						_configure_library_root_logger()

						assert handler is not None
						_get_library_root_logger().addHandler(__lowerCAmelCase							)





def      lowerCamelCase_					(   __lowerCAmelCase							)				->   None:




						'''simple docstring'''



						_configure_library_root_logger()

						assert handler is not None and handler not in _get_library_root_logger().handlers
						_get_library_root_logger().removeHandler(__lowerCAmelCase							)





def      lowerCamelCase_					(   )				->   None:




						'''simple docstring'''



						_configure_library_root_logger()
						lowerCamelCase__   =False





def      lowerCamelCase_					(   )				->   None:




						'''simple docstring'''



						_configure_library_root_logger()
						lowerCamelCase__   =True





def      lowerCamelCase_					(   )				->   None:




						'''simple docstring'''



						lowerCamelCase__   =_get_library_root_logger().handlers

						for handler in handlers:
												lowerCamelCase__   =logging.Formatter("[%(levelname)s|%(filename)s:%(lineno)s] %(asctime)s >> %(message)s"							)
												handler.setFormatter(__lowerCAmelCase							)





def      lowerCamelCase_					(   )				->   None:




						'''simple docstring'''



						lowerCamelCase__   =_get_library_root_logger().handlers

						for handler in handlers:
												handler.setFormatter(__lowerCAmelCase							)





def      lowerCamelCase_					(   self  ,       *__lowerCAmelCase  ,       **__lowerCAmelCase							)				->   int:




						'''simple docstring'''



						lowerCamelCase__   =os.getenv("TRANSFORMERS_NO_ADVISORY_WARNINGS"  ,       __lowerCAmelCase							)
						if no_advisory_warnings:
												return
						self.warning(*__lowerCAmelCase  ,       **__lowerCAmelCase							)


a				=warning_advice





@functools.lru_cache(__lowerCAmelCase							)
def      lowerCamelCase_					(   self  ,       *__lowerCAmelCase  ,       **__lowerCAmelCase							)				->   Tuple:




						'''simple docstring'''



						self.warning(*__lowerCAmelCase  ,       **__lowerCAmelCase							)


a				=warning_once






class   __UpperCAmelCase		:

				def __init__( self      ,					*_lowerCamelCase      ,					**_lowerCamelCase ):  # pylint: disable=unused-argument
										lowerCamelCase__   =args[0] if args else None

				def __iter__( self ):
										return iter(self._iterator )

				def __getattr__( self      ,					_lowerCamelCase ):

										def empty_fn(*_lowerCamelCase      ,					**_lowerCamelCase ):  # pylint: disable=unused-argument
																return

										return empty_fn

				def __enter__( self ):
										return self






				def __exit__( self      ,					_lowerCamelCase      ,					_lowerCamelCase      ,					_lowerCamelCase ):
										return






class   __UpperCAmelCase		:

				def __call__( self      ,					*_lowerCamelCase      ,					**_lowerCamelCase ):
										if _tqdm_active:
																return tqdm_lib.tqdm(*_lowerCamelCase      ,					**_lowerCamelCase )
										else:
																return EmptyTqdm(*_lowerCamelCase      ,					**_lowerCamelCase )

				def 						_a      ( self      ,					*_lowerCamelCase      ,					**_lowerCamelCase ):
										lowerCamelCase__   =None
										if _tqdm_active:
																return tqdm_lib.tqdm.set_lock(*_lowerCamelCase      ,					**_lowerCamelCase )






				def 						_a      ( self ):
										if _tqdm_active:
																return tqdm_lib.tqdm.get_lock()





a				=_tqdm_cls()





def      lowerCamelCase_					(   )				->   bool:




						'''simple docstring'''



						global _tqdm_active
						return bool(_tqdm_active							)





def      lowerCamelCase_					(   )				->   Tuple:




						'''simple docstring'''



						global _tqdm_active
						lowerCamelCase__   =True
						hf_hub_utils.enable_progress_bars()





def      lowerCamelCase_					(   )				->   int:




						'''simple docstring'''



						global _tqdm_active
						lowerCamelCase__   =False
						hf_hub_utils.disable_progress_bars()



"""simple docstring"""


from __future__ import annotations

import math





def      lowerCamelCase_					(   __lowerCAmelCase  ,       __lowerCAmelCase							)				->   list:




						'''simple docstring'''



						if len(__lowerCAmelCase							) != 2 or len(a[0]							) != 2 or len(__lowerCAmelCase							) != 2 or len(b[0]							) != 2:
												raise Exception("Matrices are not 2x2"							)
						lowerCamelCase__   =[
						    [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      lowerCamelCase_					(   __lowerCAmelCase  ,       __lowerCAmelCase							)				->   Dict:




						'''simple docstring'''



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





def      lowerCamelCase_					(   __lowerCAmelCase  ,       __lowerCAmelCase							)				->   List[Any]:




						'''simple docstring'''



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





def      lowerCamelCase_					(   __lowerCAmelCase							)				->   tuple[list, list, list, list]:




						'''simple docstring'''



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

						lowerCamelCase__   =len(__lowerCAmelCase							)
						lowerCamelCase__   =matrix_length // 2

						lowerCamelCase__   =[[a[i][j] for j in range(__lowerCAmelCase  ,       __lowerCAmelCase							)] for i in range(__lowerCAmelCase							)]
						lowerCamelCase__   =[
						    [a[i][j] for j in range(__lowerCAmelCase  ,       __lowerCAmelCase							)] for i in range(__lowerCAmelCase  ,       __lowerCAmelCase							)
						]

						lowerCamelCase__   =[[a[i][j] for j in range(__lowerCAmelCase							)] for i in range(__lowerCAmelCase							)]
						lowerCamelCase__   =[[a[i][j] for j in range(__lowerCAmelCase							)] for i in range(__lowerCAmelCase  ,       __lowerCAmelCase							)]

						return top_left, top_right, bot_left, bot_right





def      lowerCamelCase_					(   __lowerCAmelCase							)				->   tuple[int, int]:




						'''simple docstring'''



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





def      lowerCamelCase_					(   __lowerCAmelCase							)				->   None:




						'''simple docstring'''



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





def      lowerCamelCase_					(   __lowerCAmelCase  ,       __lowerCAmelCase							)				->   list:




						'''simple docstring'''



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

						lowerCamelCase__   , lowerCamelCase__   , lowerCamelCase__   , lowerCamelCase__   =split_matrix(__lowerCAmelCase							)
						lowerCamelCase__   , lowerCamelCase__   , lowerCamelCase__   , lowerCamelCase__   =split_matrix(__lowerCAmelCase							)

						lowerCamelCase__   =actual_strassen(__lowerCAmelCase  ,       matrix_subtraction(__lowerCAmelCase  ,       __lowerCAmelCase							)							)
						lowerCamelCase__   =actual_strassen(matrix_addition(__lowerCAmelCase  ,       __lowerCAmelCase							)  ,       __lowerCAmelCase							)
						lowerCamelCase__   =actual_strassen(matrix_addition(__lowerCAmelCase  ,       __lowerCAmelCase							)  ,       __lowerCAmelCase							)
						lowerCamelCase__   =actual_strassen(__lowerCAmelCase  ,       matrix_subtraction(__lowerCAmelCase  ,       __lowerCAmelCase							)							)
						lowerCamelCase__   =actual_strassen(matrix_addition(__lowerCAmelCase  ,       __lowerCAmelCase							)  ,       matrix_addition(__lowerCAmelCase  ,       __lowerCAmelCase							)							)
						lowerCamelCase__   =actual_strassen(matrix_subtraction(__lowerCAmelCase  ,       __lowerCAmelCase							)  ,       matrix_addition(__lowerCAmelCase  ,       __lowerCAmelCase							)							)
						lowerCamelCase__   =actual_strassen(matrix_subtraction(__lowerCAmelCase  ,       __lowerCAmelCase							)  ,       matrix_addition(__lowerCAmelCase  ,       __lowerCAmelCase							)							)

						lowerCamelCase__   =matrix_addition(matrix_subtraction(matrix_addition(__lowerCAmelCase  ,       __lowerCAmelCase							)  ,       __lowerCAmelCase							)  ,       __lowerCAmelCase							)
						lowerCamelCase__   =matrix_addition(__lowerCAmelCase  ,       __lowerCAmelCase							)
						lowerCamelCase__   =matrix_addition(__lowerCAmelCase  ,       __lowerCAmelCase							)
						lowerCamelCase__   =matrix_subtraction(matrix_subtraction(matrix_addition(__lowerCAmelCase  ,       __lowerCAmelCase							)  ,       __lowerCAmelCase							)  ,       __lowerCAmelCase							)

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





def      lowerCamelCase_					(   __lowerCAmelCase  ,       __lowerCAmelCase							)				->   list:




						'''simple docstring'''



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

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

						lowerCamelCase__   =max(*__lowerCAmelCase  ,       *__lowerCAmelCase							)
						lowerCamelCase__   =int(math.pow(2  ,       math.ceil(math.loga(__lowerCAmelCase							)							)							)							)
						lowerCamelCase__   =matrixa
						lowerCamelCase__   =matrixa

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

						lowerCamelCase__   =actual_strassen(__lowerCAmelCase  ,       __lowerCAmelCase							)

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


if __name__ == "__main__":
	a				=[
	    [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],
	]
	a				=[[0, 2, 1, 1], [16, 2, 3, 3], [2, 2, 7, 7], [13, 11, 22, 4]]
	print(strassen(matrixa, matrixa))


