
'''simple docstring'''



from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_tf_available,
    is_tokenizers_available,
    is_torch_available,
)


_lowercase    =		{
    """configuration_deberta""": ["""DEBERTA_PRETRAINED_CONFIG_ARCHIVE_MAP""", """DebertaConfig""", """DebertaOnnxConfig"""],
    """tokenization_deberta""": ["""DebertaTokenizer"""],
}

try:
						if not is_tokenizers_available():
												raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
						pass
else:
						_lowercase    =		["""DebertaTokenizerFast"""]

try:
						if not is_torch_available():
												raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
						pass
else:
						_lowercase    =		[
						    """DEBERTA_PRETRAINED_MODEL_ARCHIVE_LIST""",
						    """DebertaForMaskedLM""",
						    """DebertaForQuestionAnswering""",
						    """DebertaForSequenceClassification""",
						    """DebertaForTokenClassification""",
						    """DebertaModel""",
						    """DebertaPreTrainedModel""",
						]

try:
						if not is_tf_available():
												raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
						pass
else:
						_lowercase    =		[
						    """TF_DEBERTA_PRETRAINED_MODEL_ARCHIVE_LIST""",
						    """TFDebertaForMaskedLM""",
						    """TFDebertaForQuestionAnswering""",
						    """TFDebertaForSequenceClassification""",
						    """TFDebertaForTokenClassification""",
						    """TFDebertaModel""",
						    """TFDebertaPreTrainedModel""",
						]


if TYPE_CHECKING:
						from .configuration_deberta import DEBERTA_PRETRAINED_CONFIG_ARCHIVE_MAP, DebertaConfig, DebertaOnnxConfig
						from .tokenization_deberta import DebertaTokenizer

						try:
												if not is_tokenizers_available():
																		raise OptionalDependencyNotAvailable()
						except OptionalDependencyNotAvailable:
												pass
						else:
												from .tokenization_deberta_fast import DebertaTokenizerFast

						try:
												if not is_torch_available():
																		raise OptionalDependencyNotAvailable()
						except OptionalDependencyNotAvailable:
												pass
						else:
												from .modeling_deberta import (
												    DEBERTA_PRETRAINED_MODEL_ARCHIVE_LIST,
												    DebertaForMaskedLM,
												    DebertaForQuestionAnswering,
												    DebertaForSequenceClassification,
												    DebertaForTokenClassification,
												    DebertaModel,
												    DebertaPreTrainedModel,
												)

						try:
												if not is_tf_available():
																		raise OptionalDependencyNotAvailable()
						except OptionalDependencyNotAvailable:
												pass
						else:
												from .modeling_tf_deberta import (
												    TF_DEBERTA_PRETRAINED_MODEL_ARCHIVE_LIST,
												    TFDebertaForMaskedLM,
												    TFDebertaForQuestionAnswering,
												    TFDebertaForSequenceClassification,
												    TFDebertaForTokenClassification,
												    TFDebertaModel,
												    TFDebertaPreTrainedModel,
												)


else:
						import sys

						_lowercase    =		_LazyModule(__name__, globals()["""__file__"""], _import_structure, module_spec=__spec__)


'''simple docstring'''



from __future__ import annotations

import math


def A				(__lowerCamelCase				:list			,     __lowerCamelCase				:list		):
						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 A				(__lowerCamelCase				:list			,     __lowerCamelCase				:list		):
						return [
						    [matrix_a[row][col] + matrix_b[row][col] for col in range(len(matrix_a[row]		)		)]
						    for row in range(len(__lowerCamelCase		)		)
						]


def A				(__lowerCamelCase				:list			,     __lowerCamelCase				:list		):
						return [
						    [matrix_a[row][col] - matrix_b[row][col] for col in range(len(matrix_a[row]		)		)]
						    for row in range(len(__lowerCamelCase		)		)
						]


def A				(__lowerCamelCase				:list		):
						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 A				(__lowerCamelCase				:list		):
						return len(__lowerCamelCase		), len(matrix[0]		)


def A				(__lowerCamelCase				:list		):
						print("""\n""".join(str(__lowerCamelCase		) for line in matrix		)		)


def A				(__lowerCamelCase				:list			,     __lowerCamelCase				:list		):
						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 A				(__lowerCamelCase				:list			,     __lowerCamelCase				:list		):
						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__":
						_lowercase    =		[
						    [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],
						]
						_lowercase    =		[[0, 2, 1, 1], [16, 2, 3, 3], [2, 2, 7, 7], [13, 11, 22, 4]]
						print(strassen(matrixa, matrixa))
