from __future__ import annotations
class     lowerCAmelCase_     :







							def __init__(   self      :     Optional[Any] ,			_A      :     list[list[int]]		):
												_UpperCamelCase			     =     TypeError(
												    '''Matrices must be formed from a list of zero or more lists containing at '''
												    '''least one and the same number of values, each of which must be of type '''
												    '''int or float.'''		)
												if len(_A		) != 0:
																	_UpperCamelCase			     =     len(rows[0]		)
																	if cols == 0:
																						raise error
																	for row in rows:
																						if len(_A		) != cols:
																											raise error
																						for value in row:
																											if not isinstance(_A ,			(int, float)		):
																																raise error
																	_UpperCamelCase			     =     rows
												else:
																	_UpperCamelCase			     =     []







							def  UpperCamelCase_						(   self      :     Optional[Any]		):
												return [[row[i] for row in self.rows] for i in range(len(self.rows[0]		)		)]







							@property
							def  UpperCamelCase_						(   self      :     List[Any]		):
												return len(self.rows		)







							@property
							def  UpperCamelCase_						(   self      :     List[Any]		):
												return len(self.rows[0]		)







							@property
							def  UpperCamelCase_						(   self      :     Optional[Any]		):
												return (self.num_rows, self.num_columns)







							@property
							def  UpperCamelCase_						(   self      :     Tuple		):
												return self.order[0] == self.order[1]







							def  UpperCamelCase_						(   self      :     Dict		):
												_UpperCamelCase			     =     [
												    [0 if column_num != row_num else 1 for column_num in range(self.num_rows		)]
												    for row_num in range(self.num_rows		)
												]
												return Matrix(_A		)







							def  UpperCamelCase_						(   self      :     List[str]		):
												if not self.is_square:
																	return 0
												if self.order == (0, 0):
																	return 1
												if self.order == (1, 1):
																	return int(self.rows[0][0]		)
												if self.order == (2, 2):
																	return int(
																	    (self.rows[0][0] * self.rows[1][1])
																	    - (self.rows[0][1] * self.rows[1][0])		)
												else:
																	return sum(
																	    self.rows[0][column] * self.cofactors().rows[0][column]
																	    for column in range(self.num_columns		)		)







							def  UpperCamelCase_						(   self      :     Optional[Any]		):
												return bool(self.determinant()		)







							def  UpperCamelCase_						(   self      :     str ,			_A      :     int ,			_A      :     int		):
												_UpperCamelCase			     =     [
												    [
												        self.rows[other_row][other_column]
												        for other_column in range(self.num_columns		)
												        if other_column != column
												    ]
												    for other_row in range(self.num_rows		)
												    if other_row != row
												]
												return Matrix(_A		).determinant()







							def  UpperCamelCase_						(   self      :     Optional[int] ,			_A      :     int ,			_A      :     int		):
												if (row + column) % 2 == 0:
																	return self.get_minor(_A ,			_A		)
												return -1 * self.get_minor(_A ,			_A		)







							def  UpperCamelCase_						(   self      :     List[str]		):
												return Matrix(
												    [
												        [self.get_minor(_A ,			_A		) for column in range(self.num_columns		)]
												        for row in range(self.num_rows		)
												    ]		)







							def  UpperCamelCase_						(   self      :     Optional[int]		):
												return Matrix(
												    [
												        [
												            self.minors().rows[row][column]
												            if (row + column) % 2 == 0
												            else self.minors().rows[row][column] * -1
												            for column in range(self.minors().num_columns		)
												        ]
												        for row in range(self.minors().num_rows		)
												    ]		)







							def  UpperCamelCase_						(   self      :     Optional[int]		):
												_UpperCamelCase			     =     [
												    [self.cofactors().rows[column][row] for column in range(self.num_columns		)]
												    for row in range(self.num_rows		)
												]
												return Matrix(_A		)







							def  UpperCamelCase_						(   self      :     Tuple		):
												_UpperCamelCase			     =     self.determinant()
												if not determinant:
																	raise TypeError('''Only matrices with a non-zero determinant have an inverse'''		)
												return self.adjugate() * (1 / determinant)







							def __repr__(   self      :     List[Any]		):
												return str(self.rows		)







							def __str__(   self      :     List[Any]		):
												if self.num_rows == 0:
																	return "[]"
												if self.num_rows == 1:
																	return "[[" + ". ".join(str(self.rows[0]		)		) + "]]"
												return (
												    "["
												    + "\n ".join(
												        [
												            '''[''' + '''. '''.join([str(_A		) for value in row]		) + '''.]'''
												            for row in self.rows
												        ]		)
												    + "]"
												)







							def  UpperCamelCase_						(   self      :     List[str] ,			_A      :     list[int] ,			_A      :     int | None = None		):
												_UpperCamelCase			     =     TypeError('''Row must be a list containing all ints and/or floats'''		)
												if not isinstance(_A ,			_A		):
																	raise type_error
												for value in row:
																	if not isinstance(_A ,			(int, float)		):
																						raise type_error
												if len(_A		) != self.num_columns:
																	raise ValueError(
																	    '''Row must be equal in length to the other rows in the matrix'''		)
												if position is None:
																	self.rows.append(_A		)
												else:
																	_UpperCamelCase			     =     self.rows[0:position] + [row] + self.rows[position:]







							def  UpperCamelCase_						(   self      :     Optional[int] ,			_A      :     list[int] ,			_A      :     int | None = None		):
												_UpperCamelCase			     =     TypeError(
												    '''Column must be a list containing all ints and/or floats'''		)
												if not isinstance(_A ,			_A		):
																	raise type_error
												for value in column:
																	if not isinstance(_A ,			(int, float)		):
																						raise type_error
												if len(_A		) != self.num_rows:
																	raise ValueError(
																	    '''Column must be equal in length to the other columns in the matrix'''		)
												if position is None:
																	_UpperCamelCase			     =     [self.rows[i] + [column[i]] for i in range(self.num_rows		)]
												else:
																	_UpperCamelCase			     =     [
																	    self.rows[i][0:position] + [column[i]] + self.rows[i][position:]
																	    for i in range(self.num_rows		)
																	]







							def __eq__(   self      :     List[Any] ,			_A      :     object		):
												if not isinstance(_A ,			_A		):
																	return NotImplemented
												return self.rows == other.rows







							def __ne__(   self      :     List[str] ,			_A      :     object		):
												return not self == other







							def __neg__(   self      :     Any		):
												return self * -1







							def __add__(   self      :     Union[str, Any] ,			_A      :     Matrix		):
												if self.order != other.order:
																	raise ValueError('''Addition requires matrices of the same order'''		)
												return Matrix(
												    [
												        [self.rows[i][j] + other.rows[i][j] for j in range(self.num_columns		)]
												        for i in range(self.num_rows		)
												    ]		)







							def __sub__(   self      :     Union[str, Any] ,			_A      :     Matrix		):
												if self.order != other.order:
																	raise ValueError('''Subtraction requires matrices of the same order'''		)
												return Matrix(
												    [
												        [self.rows[i][j] - other.rows[i][j] for j in range(self.num_columns		)]
												        for i in range(self.num_rows		)
												    ]		)







							def __mul__(   self      :     Tuple ,			_A      :     Matrix | int | float		):
												if isinstance(_A ,			(int, float)		):
																	return Matrix(
																	    [[int(element * other		) for element in row] for row in self.rows]		)
												elif isinstance(_A ,			_A		):
																	if self.num_columns != other.num_rows:
																						raise ValueError(
																						    '''The number of columns in the first matrix must '''
																						    '''be equal to the number of rows in the second'''		)
																	return Matrix(
																	    [
																	        [Matrix.dot_product(_A ,			_A		) for column in other.columns()]
																	        for row in self.rows
																	    ]		)
												else:
																	raise TypeError(
																	    '''A Matrix can only be multiplied by an int, float, or another matrix'''		)







							def __pow__(   self      :     List[Any] ,			_A      :     int		):
												if not isinstance(_A ,			_A		):
																	raise TypeError('''A Matrix can only be raised to the power of an int'''		)
												if not self.is_square:
																	raise ValueError('''Only square matrices can be raised to a power'''		)
												if other == 0:
																	return self.identity()
												if other < 0:
																	if self.is_invertable():
																						return self.inverse() ** (-other)
																	raise ValueError(
																	    '''Only invertable matrices can be raised to a negative power'''		)
												_UpperCamelCase			     =     self
												for _ in range(other - 1		):
																	result *= self
												return result







							@classmethod
							def  UpperCamelCase_						(   cls      :     Union[str, Any] ,			_A      :     list[int] ,			_A      :     list[int]		):
												return sum(row[i] * column[i] for i in range(len(_A		)		)		)


if __name__ == "__main__":
					import doctest

					doctest.testmod()







from __future__ import annotations

# This is the precision for this function which can be altered.
# It is recommended for users to keep this number greater than or equal to 10.
UpperCamelCase__           =			10





def      _UpperCamelCase  (a__ :int ,      a__ :int ,      a__ :list[int] ,      a__ :int							):






							"""simple docstring"""





							for i in range(a__ ,      a__							):
														if array[i] == target:
																					return i
							return -1





def      _UpperCamelCase  (a__ :list[int] ,      a__ :int							):






							"""simple docstring"""





							UpperCamelCase__					  =      0
							UpperCamelCase__					  =      len(a__							)
							while left <= right:
														if right - left < precision:
																					return lin_search(a__ ,      a__ ,      a__ ,      a__							)

														UpperCamelCase__					  =      (left + right) // 3 + 1
														UpperCamelCase__					  =      2 * (left + right) // 3 + 1

														if array[one_third] == target:
																					return one_third
														elif array[two_third] == target:
																					return two_third

														elif target < array[one_third]:
																					UpperCamelCase__					  =      one_third - 1
														elif array[two_third] < target:
																					UpperCamelCase__					  =      two_third + 1

														else:
																					UpperCamelCase__					  =      one_third + 1
																					UpperCamelCase__					  =      two_third - 1
							else:
														return -1





def      _UpperCamelCase  (a__ :int ,      a__ :int ,      a__ :list[int] ,      a__ :int							):






							"""simple docstring"""





							if left < right:
														if right - left < precision:
																					return lin_search(a__ ,      a__ ,      a__ ,      a__							)
														UpperCamelCase__					  =      (left + right) // 3 + 1
														UpperCamelCase__					  =      2 * (left + right) // 3 + 1

														if array[one_third] == target:
																					return one_third
														elif array[two_third] == target:
																					return two_third

														elif target < array[one_third]:
																					return rec_ternary_search(a__ ,      one_third - 1 ,      a__ ,      a__							)
														elif array[two_third] < target:
																					return rec_ternary_search(two_third + 1 ,      a__ ,      a__ ,      a__							)
														else:
																					return rec_ternary_search(one_third + 1 ,      two_third - 1 ,      a__ ,      a__							)
							else:
														return -1


if __name__ == "__main__":
					import doctest

					doctest.testmod()

					UpperCamelCase__           =			input("Enter numbers separated by comma:\n").strip()
					UpperCamelCase__           =			[int(item.strip()) for item in user_input.split(",")]
					assert collection == sorted(collection), f"List must be ordered.\n{collection}."
					UpperCamelCase__           =			int(input("Enter the number to be found in the list:\n").strip())
					UpperCamelCase__           =			ite_ternary_search(collection, target)
					UpperCamelCase__           =			rec_ternary_search(0, len(collection) - 1, collection, target)
					if resulta != -1:
										print(f"""Iterative search: {target} found at positions: {resulta}""")
										print(f"""Recursive search: {target} found at positions: {resulta}""")
					else:
										print("Not found")




