from __future__ import annotations

import math





def 					lowerCAmelCase_			(	__a     ,   __a		)					->		list:







  """simple docstring"""





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





def 					lowerCAmelCase_			(	__a     ,   __a		)					->		Tuple:







  """simple docstring"""





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





def 					lowerCAmelCase_			(	__a		)					->		tuple[list, list, list, list]:







  """simple docstring"""





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

  lowerCamelCase__:				List[Any]        =len(__a		)
  lowerCamelCase__:				List[str]        =matrix_length // 2

  lowerCamelCase__:				Tuple        =[[a[i][j] for j in range(__a     ,   __a		)] for i in range(__a		)]
  lowerCamelCase__:				int        =[
      [a[i][j] for j in range(__a     ,   __a		)] for i in range(__a     ,   __a		)
  ]

  lowerCamelCase__:				Tuple        =[[a[i][j] for j in range(__a		)] for i in range(__a		)]
  lowerCamelCase__:				Any        =[[a[i][j] for j in range(__a		)] for i in range(__a     ,   __a		)]

  return top_left, top_right, bot_left, bot_right





def 					lowerCAmelCase_			(	__a		)					->		tuple[int, int]:







  """simple docstring"""





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





def 					lowerCAmelCase_			(	__a		)					->		None:







  """simple docstring"""





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





def 					lowerCAmelCase_			(	__a     ,   __a		)					->		list:







  """simple docstring"""





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

  lowerCamelCase__:				List[Any]        =split_matrix(__a		)
  lowerCamelCase__:				Optional[int]        =split_matrix(__a		)

  lowerCamelCase__:				str        =actual_strassen(__a     ,   matrix_subtraction(__a     ,   __a		)		)
  lowerCamelCase__:				Optional[Any]        =actual_strassen(matrix_addition(__a     ,   __a		)     ,   __a		)
  lowerCamelCase__:				Dict        =actual_strassen(matrix_addition(__a     ,   __a		)     ,   __a		)
  lowerCamelCase__:				Union[str, Any]        =actual_strassen(__a     ,   matrix_subtraction(__a     ,   __a		)		)
  lowerCamelCase__:				List[Any]        =actual_strassen(matrix_addition(__a     ,   __a		)     ,   matrix_addition(__a     ,   __a		)		)
  lowerCamelCase__:				str        =actual_strassen(matrix_subtraction(__a     ,   __a		)     ,   matrix_addition(__a     ,   __a		)		)
  lowerCamelCase__:				Tuple        =actual_strassen(matrix_subtraction(__a     ,   __a		)     ,   matrix_addition(__a     ,   __a		)		)

  lowerCamelCase__:				List[str]        =matrix_addition(matrix_subtraction(matrix_addition(__a     ,   __a		)     ,   __a		)     ,   __a		)
  lowerCamelCase__:				Tuple        =matrix_addition(__a     ,   __a		)
  lowerCamelCase__:				List[Any]        =matrix_addition(__a     ,   __a		)
  lowerCamelCase__:				List[Any]        =matrix_subtraction(matrix_subtraction(matrix_addition(__a     ,   __a		)     ,   __a		)     ,   __a		)

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





def 					lowerCAmelCase_			(	__a     ,   __a		)					->		list:







  """simple docstring"""





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

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

  lowerCamelCase__:				str        =max(*__a     ,   *__a		)
  lowerCamelCase__:				Tuple        =int(math.pow(2     ,   math.ceil(math.loga(__a		)		)		)		)
  lowerCamelCase__:				Optional[Any]        =matrixa
  lowerCamelCase__:				Tuple        =matrixa

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

  lowerCamelCase__:				List[str]        =actual_strassen(__a     ,   __a		)

  # Removing the additional zeros
  for i in range(0     ,   __a		):
    if i < dimensiona[0]:
      for _ in range(dimensiona[1]     ,   __a		):
        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))








def 					lowerCAmelCase_			(	__a     ,   __a		)					->		Tuple:







  """simple docstring"""





  assert x is not None
  assert y is not None

  lowerCamelCase__:				Any        =len(__a		)
  lowerCamelCase__:				int        =len(__a		)

  # declaring the array for storing the dp values
  lowerCamelCase__:				List[Any]        =[[0] * (n + 1) for _ in range(m + 1		)]  # noqa: E741

  for i in range(1     ,   m + 1		):
    for j in range(1     ,   n + 1		):
      lowerCamelCase__:				str        =1 if x[i - 1] == y[j - 1] else 0

      lowerCamelCase__:				str        =max(l[i - 1][j]     ,   l[i][j - 1]     ,   l[i - 1][j - 1] + match		)

  lowerCamelCase__:				Any        =""
  lowerCamelCase__  , lowerCamelCase__:				str        =m, n
  while i > 0 and j > 0:
    lowerCamelCase__:				Union[str, Any]        =1 if x[i - 1] == y[j - 1] else 0

    if l[i][j] == l[i - 1][j - 1] + match:
      if match == 1:
        lowerCamelCase__:				Any        =x[i - 1] + seq
      i -= 1
      j -= 1
    elif l[i][j] == l[i - 1][j]:
      i -= 1
    else:
      j -= 1

  return l[m][n], seq


if __name__ == "__main__":
     __A     =    "AGGTAB"
     __A     =    "GXTXAYB"
     __A     =    4
     __A     =    "GTAB"

     __A ,     __A     =    longest_common_subsequence(a, b)
     print("len =", ln, ", sub-sequence =", subseq)
     import doctest

     doctest.testmod()

