from __future__ import annotations

import math



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: list				,  __UpperCamelCase					: list			)							->      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"""			)
  SCREAMING_SNAKE_CASE__    							=   [
      [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						(      __UpperCamelCase					: list				,  __UpperCamelCase					: list			)							->      Optional[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(__UpperCamelCase			)			)
  ]



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: list				,  __UpperCamelCase					: list			)							->      List[str]:







  """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 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: list			)							->      tuple[list, list, list, list]:







  """simple docstring"""





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

  SCREAMING_SNAKE_CASE__    							=   len(__UpperCamelCase			)
  SCREAMING_SNAKE_CASE__    							=   matrix_length // 2

  SCREAMING_SNAKE_CASE__    							=   [[a[i][j] for j in range(__UpperCamelCase				,  __UpperCamelCase			)] for i in range(__UpperCamelCase			)]
  SCREAMING_SNAKE_CASE__    							=   [
      [a[i][j] for j in range(__UpperCamelCase				,  __UpperCamelCase			)] for i in range(__UpperCamelCase				,  __UpperCamelCase			)
  ]

  SCREAMING_SNAKE_CASE__    							=   [[a[i][j] for j in range(__UpperCamelCase			)] for i in range(__UpperCamelCase			)]
  SCREAMING_SNAKE_CASE__    							=   [[a[i][j] for j in range(__UpperCamelCase			)] for i in range(__UpperCamelCase				,  __UpperCamelCase			)]

  return top_left, top_right, bot_left, bot_right



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: list			)							->      tuple[int, int]:







  """simple docstring"""





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



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: list			)							->      None:







  """simple docstring"""





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



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: list				,  __UpperCamelCase					: list			)							->      list:







  """simple docstring"""





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

  SCREAMING_SNAKE_CASE__							,  SCREAMING_SNAKE_CASE__							,  SCREAMING_SNAKE_CASE__							,  SCREAMING_SNAKE_CASE__    							=   split_matrix(__UpperCamelCase			)
  SCREAMING_SNAKE_CASE__							,  SCREAMING_SNAKE_CASE__							,  SCREAMING_SNAKE_CASE__							,  SCREAMING_SNAKE_CASE__    							=   split_matrix(__UpperCamelCase			)

  SCREAMING_SNAKE_CASE__    							=   actual_strassen(__UpperCamelCase				,  matrix_subtraction(__UpperCamelCase				,  __UpperCamelCase			)			)
  SCREAMING_SNAKE_CASE__    							=   actual_strassen(matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)				,  __UpperCamelCase			)
  SCREAMING_SNAKE_CASE__    							=   actual_strassen(matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)				,  __UpperCamelCase			)
  SCREAMING_SNAKE_CASE__    							=   actual_strassen(__UpperCamelCase				,  matrix_subtraction(__UpperCamelCase				,  __UpperCamelCase			)			)
  SCREAMING_SNAKE_CASE__    							=   actual_strassen(matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)				,  matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)			)
  SCREAMING_SNAKE_CASE__    							=   actual_strassen(matrix_subtraction(__UpperCamelCase				,  __UpperCamelCase			)				,  matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)			)
  SCREAMING_SNAKE_CASE__    							=   actual_strassen(matrix_subtraction(__UpperCamelCase				,  __UpperCamelCase			)				,  matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)			)

  SCREAMING_SNAKE_CASE__    							=   matrix_addition(matrix_subtraction(matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)				,  __UpperCamelCase			)				,  __UpperCamelCase			)
  SCREAMING_SNAKE_CASE__    							=   matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)
  SCREAMING_SNAKE_CASE__    							=   matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)
  SCREAMING_SNAKE_CASE__    							=   matrix_subtraction(matrix_subtraction(matrix_addition(__UpperCamelCase				,  __UpperCamelCase			)				,  __UpperCamelCase			)				,  __UpperCamelCase			)

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







  """simple docstring"""





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

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

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

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

import os

__lowerCamelCase    :				Union[str, Any]							     =	{'''I''': 1, '''V''': 5, '''X''': 10, '''L''': 50, '''C''': 100, '''D''': 500, '''M''': 1000}



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: str			)							->      int:







  """simple docstring"""





  SCREAMING_SNAKE_CASE__    							=   0

  SCREAMING_SNAKE_CASE__    							=   0
  while index < len(__UpperCamelCase			) - 1:
    SCREAMING_SNAKE_CASE__    							=   SYMBOLS[numerals[index]]
    SCREAMING_SNAKE_CASE__    							=   SYMBOLS[numerals[index + 1]]
    if current_value < next_value:
      total_value -= current_value
    else:
      total_value += current_value
    index += 1
  total_value += SYMBOLS[numerals[index]]

  return total_value



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: int			)							->      str:







  """simple docstring"""





  SCREAMING_SNAKE_CASE__    							=   """"""

  SCREAMING_SNAKE_CASE__    							=   num // 10_00
  numerals += m_count * "M"
  num %= 10_00

  SCREAMING_SNAKE_CASE__    							=   num // 1_00
  if c_count == 9:
    numerals += "CM"
    c_count -= 9
  elif c_count == 4:
    numerals += "CD"
    c_count -= 4
  if c_count >= 5:
    numerals += "D"
    c_count -= 5
  numerals += c_count * "C"
  num %= 1_00

  SCREAMING_SNAKE_CASE__    							=   num // 10
  if x_count == 9:
    numerals += "XC"
    x_count -= 9
  elif x_count == 4:
    numerals += "XL"
    x_count -= 4
  if x_count >= 5:
    numerals += "L"
    x_count -= 5
  numerals += x_count * "X"
  num %= 10

  if num == 9:
    numerals += "IX"
    num -= 9
  elif num == 4:
    numerals += "IV"
    num -= 4
  if num >= 5:
    numerals += "V"
    num -= 5
  numerals += num * "I"

  return numerals



def 			__SCREAMING_SNAKE_CASE						(      __UpperCamelCase					: str = "/p089_roman.txt"			)							->      int:







  """simple docstring"""





  SCREAMING_SNAKE_CASE__    							=   0

  with open(os.path.dirname(__UpperCamelCase			) + roman_numerals_filename			) as filea:
    SCREAMING_SNAKE_CASE__    							=   filea.readlines()

  for line in lines:
    SCREAMING_SNAKE_CASE__    							=   line.strip()
    SCREAMING_SNAKE_CASE__    							=   parse_roman_numerals(__UpperCamelCase			)
    SCREAMING_SNAKE_CASE__    							=   generate_roman_numerals(__UpperCamelCase			)
    savings += len(__UpperCamelCase			) - len(__UpperCamelCase			)

  return savings


if __name__ == "__main__":
   print(F"""{solution() = }""")
