


"""simple docstring"""


def _lowerCamelCase	(		_UpperCamelCase    , _UpperCamelCase    , _UpperCamelCase      ):

			'''simple docstring'''




			def update_area_of_max_square(_UpperCamelCase    , _UpperCamelCase      ) -> int:
						# BASE CASE
						if row >= rows or col >= cols:
									return 0

						__lowerCAmelCase				    =			update_area_of_max_square(_UpperCamelCase    , col + 1      )
						__lowerCAmelCase				    =			update_area_of_max_square(row + 1    , col + 1      )
						__lowerCAmelCase				    =			update_area_of_max_square(row + 1    , _UpperCamelCase      )

						if mat[row][col]:
									__lowerCAmelCase				    =			1 + min([right, diagonal, down]      )
									__lowerCAmelCase				    =			max(largest_square_area[0]    , _UpperCamelCase      )
									return sub_problem_sol
						else:
									return 0

			__lowerCAmelCase				    =			[0]
			update_area_of_max_square(0    , 0      )
			return largest_square_area[0]


def _lowerCamelCase	(		_UpperCamelCase    , _UpperCamelCase    , _UpperCamelCase      ):

			'''simple docstring'''




			def update_area_of_max_square_using_dp_array(
			    _UpperCamelCase    , _UpperCamelCase    , _UpperCamelCase      ) -> int:
						if row >= rows or col >= cols:
									return 0
						if dp_array[row][col] != -1:
									return dp_array[row][col]

						__lowerCAmelCase				    =			update_area_of_max_square_using_dp_array(_UpperCamelCase    , col + 1    , _UpperCamelCase      )
						__lowerCAmelCase				    =			update_area_of_max_square_using_dp_array(row + 1    , col + 1    , _UpperCamelCase      )
						__lowerCAmelCase				    =			update_area_of_max_square_using_dp_array(row + 1    , _UpperCamelCase    , _UpperCamelCase      )

						if mat[row][col]:
									__lowerCAmelCase				    =			1 + min([right, diagonal, down]      )
									__lowerCAmelCase				    =			max(largest_square_area[0]    , _UpperCamelCase      )
									__lowerCAmelCase				    =			sub_problem_sol
									return sub_problem_sol
						else:
									return 0

			__lowerCAmelCase				    =			[0]
			__lowerCAmelCase				    =			[[-1] * cols for _ in range(_UpperCamelCase      )]
			update_area_of_max_square_using_dp_array(0    , 0    , _UpperCamelCase      )

			return largest_square_area[0]


def _lowerCamelCase	(		_UpperCamelCase    , _UpperCamelCase    , _UpperCamelCase      ):

			'''simple docstring'''




			__lowerCAmelCase				    =			[[0] * (cols + 1) for _ in range(rows + 1      )]
			__lowerCAmelCase				    =			0
			for row in range(rows - 1    , -1    , -1      ):
						for col in range(cols - 1    , -1    , -1      ):
									__lowerCAmelCase				    =			dp_array[row][col + 1]
									__lowerCAmelCase				    =			dp_array[row + 1][col + 1]
									__lowerCAmelCase				    =			dp_array[row + 1][col]

									if mat[row][col] == 1:
												__lowerCAmelCase				    =			1 + min(_UpperCamelCase    , _UpperCamelCase    , _UpperCamelCase      )
												__lowerCAmelCase				    =			max(dp_array[row][col]    , _UpperCamelCase      )
									else:
												__lowerCAmelCase				    =			0

			return largest_square_area


def _lowerCamelCase	(		_UpperCamelCase    , _UpperCamelCase    , _UpperCamelCase      ):

			'''simple docstring'''




			__lowerCAmelCase				    =			[0] * (cols + 1)
			__lowerCAmelCase				    =			[0] * (cols + 1)
			__lowerCAmelCase				    =			0
			for row in range(rows - 1    , -1    , -1      ):
						for col in range(cols - 1    , -1    , -1      ):
									__lowerCAmelCase				    =			current_row[col + 1]
									__lowerCAmelCase				    =			next_row[col + 1]
									__lowerCAmelCase				    =			next_row[col]

									if mat[row][col] == 1:
												__lowerCAmelCase				    =			1 + min(_UpperCamelCase    , _UpperCamelCase    , _UpperCamelCase      )
												__lowerCAmelCase				    =			max(current_row[col]    , _UpperCamelCase      )
									else:
												__lowerCAmelCase				    =			0
						__lowerCAmelCase				    =			current_row

			return largest_square_area


if __name__ == "__main__":
	import doctest

	doctest.testmod()
	print(largest_square_area_in_matrix_bottom_up(2, 2, [[1, 1], [1, 1]]))








"""simple docstring"""


def _lowerCamelCase	(		_UpperCamelCase      ):

			'''simple docstring'''




			__lowerCAmelCase				    =			False
			while is_sorted is False:  # Until all the indices are traversed keep looping
						__lowerCAmelCase				    =			True
						for i in range(0    , len(_UpperCamelCase      ) - 1    , 2      ):  # iterating over all even indices
									if input_list[i] > input_list[i + 1]:
												__lowerCAmelCase    ,	__lowerCAmelCase				    =			input_list[i + 1], input_list[i]
												# swapping if elements not in order
												__lowerCAmelCase				    =			False

						for i in range(1    , len(_UpperCamelCase      ) - 1    , 2      ):  # iterating over all odd indices
									if input_list[i] > input_list[i + 1]:
												__lowerCAmelCase    ,	__lowerCAmelCase				    =			input_list[i + 1], input_list[i]
												# swapping if elements not in order
												__lowerCAmelCase				    =			False
			return input_list


if __name__ == "__main__":
	print("Enter list to be sorted")
	A     :   Union[str, Any]			    =			[int(x) for x in input().split()]
	# inputing elements of the list in one line
	A     :   str			    =			odd_even_sort(input_list)
	print("The sorted list is")
	print(sorted_list)




