'''simple docstring'''


from __future__ import annotations

import math





def       lowerCAmelCase					(		UpperCamelCase__				:   list    ,					UpperCamelCase__				:   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'''       )
	__UpperCAmelCase							=			[
	    [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					(		UpperCamelCase__				:   list    ,					UpperCamelCase__				:   list       ):


	"""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       lowerCAmelCase					(		UpperCamelCase__				:   list    ,					UpperCamelCase__				:   list       ):


	"""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       lowerCAmelCase					(		UpperCamelCase__				:   list       ):


	"""simple docstring"""




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

	__UpperCAmelCase							=			len(UpperCamelCase__       )
	__UpperCAmelCase							=			matrix_length // 2

	__UpperCAmelCase							=			[[a[i][j] for j in range(UpperCamelCase__    ,					UpperCamelCase__       )] for i in range(UpperCamelCase__       )]
	__UpperCAmelCase							=			[
	    [a[i][j] for j in range(UpperCamelCase__    ,					UpperCamelCase__       )] for i in range(UpperCamelCase__    ,					UpperCamelCase__       )
	]

	__UpperCAmelCase							=			[[a[i][j] for j in range(UpperCamelCase__       )] for i in range(UpperCamelCase__       )]
	__UpperCAmelCase							=			[[a[i][j] for j in range(UpperCamelCase__       )] for i in range(UpperCamelCase__    ,					UpperCamelCase__       )]

	return top_left, top_right, bot_left, bot_right





def       lowerCAmelCase					(		UpperCamelCase__				:   list       ):


	"""simple docstring"""
	return len(UpperCamelCase__       ), len(matrix[0]       )





def       lowerCAmelCase					(		UpperCamelCase__				:   list       ):


	"""simple docstring"""
	print('''\n'''.join(str(UpperCamelCase__       ) for line in matrix       )       )





def       lowerCAmelCase					(		UpperCamelCase__				:   list    ,					UpperCamelCase__				:   list       ):


	"""simple docstring"""




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

	__UpperCAmelCase				,			__UpperCAmelCase				,			__UpperCAmelCase				,			__UpperCAmelCase							=			split_matrix(UpperCamelCase__       )
	__UpperCAmelCase				,			__UpperCAmelCase				,			__UpperCAmelCase				,			__UpperCAmelCase							=			split_matrix(UpperCamelCase__       )

	__UpperCAmelCase							=			actual_strassen(UpperCamelCase__    ,					matrix_subtraction(UpperCamelCase__    ,					UpperCamelCase__       )       )
	__UpperCAmelCase							=			actual_strassen(matrix_addition(UpperCamelCase__    ,					UpperCamelCase__       )    ,					UpperCamelCase__       )
	__UpperCAmelCase							=			actual_strassen(matrix_addition(UpperCamelCase__    ,					UpperCamelCase__       )    ,					UpperCamelCase__       )
	__UpperCAmelCase							=			actual_strassen(UpperCamelCase__    ,					matrix_subtraction(UpperCamelCase__    ,					UpperCamelCase__       )       )
	__UpperCAmelCase							=			actual_strassen(matrix_addition(UpperCamelCase__    ,					UpperCamelCase__       )    ,					matrix_addition(UpperCamelCase__    ,					UpperCamelCase__       )       )
	__UpperCAmelCase							=			actual_strassen(matrix_subtraction(UpperCamelCase__    ,					UpperCamelCase__       )    ,					matrix_addition(UpperCamelCase__    ,					UpperCamelCase__       )       )
	__UpperCAmelCase							=			actual_strassen(matrix_subtraction(UpperCamelCase__    ,					UpperCamelCase__       )    ,					matrix_addition(UpperCamelCase__    ,					UpperCamelCase__       )       )

	__UpperCAmelCase							=			matrix_addition(matrix_subtraction(matrix_addition(UpperCamelCase__    ,					UpperCamelCase__       )    ,					UpperCamelCase__       )    ,					UpperCamelCase__       )
	__UpperCAmelCase							=			matrix_addition(UpperCamelCase__    ,					UpperCamelCase__       )
	__UpperCAmelCase							=			matrix_addition(UpperCamelCase__    ,					UpperCamelCase__       )
	__UpperCAmelCase							=			matrix_subtraction(matrix_subtraction(matrix_addition(UpperCamelCase__    ,					UpperCamelCase__       )    ,					UpperCamelCase__       )    ,					UpperCamelCase__       )

	# construct the new matrix from our 4 quadrants
	__UpperCAmelCase							=			[]
	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       lowerCAmelCase					(		UpperCamelCase__				:   list    ,					UpperCamelCase__				:   list       ):


	"""simple docstring"""




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

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

	__UpperCAmelCase							=			max(*UpperCamelCase__    ,					*UpperCamelCase__       )
	__UpperCAmelCase							=			int(math.pow(2    ,					math.ceil(math.loga(UpperCamelCase__       )       )       )       )
	__UpperCAmelCase							=			matrixa
	__UpperCAmelCase							=			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       )

	__UpperCAmelCase							=			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	:       Tuple						       =	[
					    [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	:       Any						       =	[[0, 2, 1, 1], [16, 2, 3, 3], [2, 2, 7, 7], [13, 11, 22, 4]]
					print(strassen(matrixa, matrixa))

'''simple docstring'''


from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_speech_available, is_torch_available


__lowerCAmelCase	:       List[Any]						       =	{
    "configuration_audio_spectrogram_transformer": [
        "AUDIO_SPECTROGRAM_TRANSFORMER_PRETRAINED_CONFIG_ARCHIVE_MAP",
        "ASTConfig",
    ]
}

try:
					if not is_torch_available():
										raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
					pass
else:
					__lowerCAmelCase	:       str						       =	[
					    "AUDIO_SPECTROGRAM_TRANSFORMER_PRETRAINED_MODEL_ARCHIVE_LIST",
					    "ASTForAudioClassification",
					    "ASTModel",
					    "ASTPreTrainedModel",
					]

try:
					if not is_speech_available():
										raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
					pass
else:
					__lowerCAmelCase	:       Union[str, Any]						       =	["ASTFeatureExtractor"]

if TYPE_CHECKING:
					from .configuration_audio_spectrogram_transformer import (
					    AUDIO_SPECTROGRAM_TRANSFORMER_PRETRAINED_CONFIG_ARCHIVE_MAP,
					    ASTConfig,
					)

					try:
										if not is_torch_available():
															raise OptionalDependencyNotAvailable()
					except OptionalDependencyNotAvailable:
										pass
					else:
										from .modeling_audio_spectrogram_transformer import (
										    AUDIO_SPECTROGRAM_TRANSFORMER_PRETRAINED_MODEL_ARCHIVE_LIST,
										    ASTForAudioClassification,
										    ASTModel,
										    ASTPreTrainedModel,
										)

					try:
										if not is_speech_available():
															raise OptionalDependencyNotAvailable()
					except OptionalDependencyNotAvailable:
										pass
					else:
										from .feature_extraction_audio_spectrogram_transformer import ASTFeatureExtractor


else:
					import sys

					__lowerCAmelCase	:       Optional[Any]						       =	_LazyModule(__name__, globals()["__file__"], _import_structure, module_spec=__spec__)
