






from __future__ import annotations

import math




def       _SCREAMING_SNAKE_CASE (							__snake_case   ,      __snake_case )				->						list:
       if len(__snake_case ) != 2 or len(a[0] ) != 2 or len(__snake_case ) != 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       _SCREAMING_SNAKE_CASE (							__snake_case   ,      __snake_case )				->						Optional[int]:
       return [
           [matrix_a[row][col] + matrix_b[row][col] for col in range(len(matrix_a[row] ) )]
           for row in range(len(__snake_case ) )
       ]




def       _SCREAMING_SNAKE_CASE (							__snake_case   ,      __snake_case )				->						Any:
       return [
           [matrix_a[row][col] - matrix_b[row][col] for col in range(len(matrix_a[row] ) )]
           for row in range(len(__snake_case ) )
       ]




def       _SCREAMING_SNAKE_CASE (							__snake_case )				->						tuple[list, list, list, list]:
       if len(__snake_case ) % 2 != 0 or len(a[0] ) % 2 != 0:
              raise Exception("""Odd matrices are not supported!""" )

       _UpperCAmelCase							=    len(__snake_case )
       _UpperCAmelCase							=    matrix_length // 2

       _UpperCAmelCase							=    [[a[i][j] for j in range(__snake_case   ,      __snake_case )] for i in range(__snake_case )]
       _UpperCAmelCase							=    [
           [a[i][j] for j in range(__snake_case   ,      __snake_case )] for i in range(__snake_case   ,      __snake_case )
       ]

       _UpperCAmelCase							=    [[a[i][j] for j in range(__snake_case )] for i in range(__snake_case )]
       _UpperCAmelCase							=    [[a[i][j] for j in range(__snake_case )] for i in range(__snake_case   ,      __snake_case )]

       return top_left, top_right, bot_left, bot_right




def       _SCREAMING_SNAKE_CASE (							__snake_case )				->						tuple[int, int]:
       return len(__snake_case ), len(matrix[0] )




def       _SCREAMING_SNAKE_CASE (							__snake_case )				->						None:
       print("""\n""".join(str(__snake_case ) for line in matrix ) )




def       _SCREAMING_SNAKE_CASE (							__snake_case   ,      __snake_case )				->						list:
       if matrix_dimensions(__snake_case ) == (2, 2):
              return default_matrix_multiplication(__snake_case   ,      __snake_case )

       _UpperCAmelCase	,			_UpperCAmelCase	,			_UpperCAmelCase	,			_UpperCAmelCase							=    split_matrix(__snake_case )
       _UpperCAmelCase	,			_UpperCAmelCase	,			_UpperCAmelCase	,			_UpperCAmelCase							=    split_matrix(__snake_case )

       _UpperCAmelCase							=    actual_strassen(__snake_case   ,      matrix_subtraction(__snake_case   ,      __snake_case ) )
       _UpperCAmelCase							=    actual_strassen(matrix_addition(__snake_case   ,      __snake_case )   ,      __snake_case )
       _UpperCAmelCase							=    actual_strassen(matrix_addition(__snake_case   ,      __snake_case )   ,      __snake_case )
       _UpperCAmelCase							=    actual_strassen(__snake_case   ,      matrix_subtraction(__snake_case   ,      __snake_case ) )
       _UpperCAmelCase							=    actual_strassen(matrix_addition(__snake_case   ,      __snake_case )   ,      matrix_addition(__snake_case   ,      __snake_case ) )
       _UpperCAmelCase							=    actual_strassen(matrix_subtraction(__snake_case   ,      __snake_case )   ,      matrix_addition(__snake_case   ,      __snake_case ) )
       _UpperCAmelCase							=    actual_strassen(matrix_subtraction(__snake_case   ,      __snake_case )   ,      matrix_addition(__snake_case   ,      __snake_case ) )

       _UpperCAmelCase							=    matrix_addition(matrix_subtraction(matrix_addition(__snake_case   ,      __snake_case )   ,      __snake_case )   ,      __snake_case )
       _UpperCAmelCase							=    matrix_addition(__snake_case   ,      __snake_case )
       _UpperCAmelCase							=    matrix_addition(__snake_case   ,      __snake_case )
       _UpperCAmelCase							=    matrix_subtraction(matrix_subtraction(matrix_addition(__snake_case   ,      __snake_case )   ,      __snake_case )   ,      __snake_case )

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




def       _SCREAMING_SNAKE_CASE (							__snake_case   ,      __snake_case )				->						list:
       if matrix_dimensions(__snake_case )[1] != matrix_dimensions(__snake_case )[0]:
              _UpperCAmelCase							=    (
                  """Unable to multiply these matrices, please check the dimensions.\n"""
                  f"""Matrix A: {matrixa}\n"""
                  f"""Matrix B: {matrixa}"""
              )
              raise Exception(__snake_case )
       _UpperCAmelCase							=    matrix_dimensions(__snake_case )
       _UpperCAmelCase							=    matrix_dimensions(__snake_case )

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

       _UpperCAmelCase							=    max(*__snake_case   ,      *__snake_case )
       _UpperCAmelCase							=    int(math.pow(2   ,      math.ceil(math.loga(__snake_case ) ) ) )
       _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   ,      __snake_case ):
              if i < dimensiona[0]:
                     for _ in range(dimensiona[1]   ,      __snake_case ):
                            new_matrixa[i].append(0 )
              else:
                     new_matrixa.append([0] * maxim )
              if i < dimensiona[0]:
                     for _ in range(dimensiona[1]   ,      __snake_case ):
                            new_matrixa[i].append(0 )
              else:
                     new_matrixa.append([0] * maxim )

       _UpperCAmelCase							=    actual_strassen(__snake_case   ,      __snake_case )

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


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







import os
import sys
import unittest


__a:     Optional[int]   					=					os.path.abspath(os.path.dirname(os.path.dirname(os.path.dirname(__file__))))
sys.path.append(os.path.join(git_repo_path, '''utils'''))

import get_test_info  # noqa: E402
from get_test_info import (  # noqa: E402
    get_model_to_test_mapping,
    get_model_to_tester_mapping,
    get_test_to_tester_mapping,
)


__a:     Dict   					=					os.path.join('''tests''', '''models''', '''bert''', '''test_modeling_bert.py''')
__a:     Union[str, Any]   					=					os.path.join('''tests''', '''models''', '''blip''', '''test_modeling_blip.py''')
class 		SCREAMING_SNAKE_CASE__	(  unittest.TestCase     ):

  '''simple docstring'''







  def  lowerCamelCase       (      self		:			str							)						->	Dict:


         """simple docstring"""
         _UpperCAmelCase							=    get_test_to_tester_mapping(lowerCamelCase							)
         _UpperCAmelCase							=    get_test_to_tester_mapping(lowerCamelCase							)

         _UpperCAmelCase							=    {"""BertModelTest""": """BertModelTester"""}

         _UpperCAmelCase							=    {
             """BlipModelTest""": """BlipModelTester""",
             """BlipTextImageModelTest""": """BlipTextImageModelsModelTester""",
             """BlipTextModelTest""": """BlipTextModelTester""",
             """BlipTextRetrievalModelTest""": """BlipTextRetrievalModelTester""",
             """BlipVQAModelTest""": """BlipVQAModelTester""",
             """BlipVisionModelTest""": """BlipVisionModelTester""",
         }

         self.assertEqual(get_test_info.to_json(lowerCamelCase							)       ,				lowerCamelCase							)
         self.assertEqual(get_test_info.to_json(lowerCamelCase							)       ,				lowerCamelCase							)


  def  lowerCamelCase       (      self		:			Optional[int]							)						->	str:


         """simple docstring"""
         _UpperCAmelCase							=    get_model_to_test_mapping(lowerCamelCase							)
         _UpperCAmelCase							=    get_model_to_test_mapping(lowerCamelCase							)

         _UpperCAmelCase							=    {
             """BertForMaskedLM""": ["""BertModelTest"""],
             """BertForMultipleChoice""": ["""BertModelTest"""],
             """BertForNextSentencePrediction""": ["""BertModelTest"""],
             """BertForPreTraining""": ["""BertModelTest"""],
             """BertForQuestionAnswering""": ["""BertModelTest"""],
             """BertForSequenceClassification""": ["""BertModelTest"""],
             """BertForTokenClassification""": ["""BertModelTest"""],
             """BertLMHeadModel""": ["""BertModelTest"""],
             """BertModel""": ["""BertModelTest"""],
         }

         _UpperCAmelCase							=    {
             """BlipForConditionalGeneration""": ["""BlipTextImageModelTest"""],
             """BlipForImageTextRetrieval""": ["""BlipTextRetrievalModelTest"""],
             """BlipForQuestionAnswering""": ["""BlipVQAModelTest"""],
             """BlipModel""": ["""BlipModelTest"""],
             """BlipTextModel""": ["""BlipTextModelTest"""],
             """BlipVisionModel""": ["""BlipVisionModelTest"""],
         }

         self.assertEqual(get_test_info.to_json(lowerCamelCase							)       ,				lowerCamelCase							)
         self.assertEqual(get_test_info.to_json(lowerCamelCase							)       ,				lowerCamelCase							)





  def  lowerCamelCase       (      self		:			int							)						->	Any:


         """simple docstring"""
         _UpperCAmelCase							=    get_model_to_tester_mapping(lowerCamelCase							)
         _UpperCAmelCase							=    get_model_to_tester_mapping(lowerCamelCase							)

         _UpperCAmelCase							=    {
             """BertForMaskedLM""": ["""BertModelTester"""],
             """BertForMultipleChoice""": ["""BertModelTester"""],
             """BertForNextSentencePrediction""": ["""BertModelTester"""],
             """BertForPreTraining""": ["""BertModelTester"""],
             """BertForQuestionAnswering""": ["""BertModelTester"""],
             """BertForSequenceClassification""": ["""BertModelTester"""],
             """BertForTokenClassification""": ["""BertModelTester"""],
             """BertLMHeadModel""": ["""BertModelTester"""],
             """BertModel""": ["""BertModelTester"""],
         }

         _UpperCAmelCase							=    {
             """BlipForConditionalGeneration""": ["""BlipTextImageModelsModelTester"""],
             """BlipForImageTextRetrieval""": ["""BlipTextRetrievalModelTester"""],
             """BlipForQuestionAnswering""": ["""BlipVQAModelTester"""],
             """BlipModel""": ["""BlipModelTester"""],
             """BlipTextModel""": ["""BlipTextModelTester"""],
             """BlipVisionModel""": ["""BlipVisionModelTester"""],
         }

         self.assertEqual(get_test_info.to_json(lowerCamelCase							)       ,				lowerCamelCase							)
         self.assertEqual(get_test_info.to_json(lowerCamelCase							)       ,				lowerCamelCase							)