




def 							_UpperCAmelCase  (UpperCamelCase_ : int      ,    UpperCamelCase_ : int      ,    UpperCamelCase_ : list[list[int]]       ):

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

								_lowerCAmelCase    :    List[Any]										=      update_area_of_max_square(snake_case_      ,    col + 1       )
								_lowerCAmelCase    :    Optional[int]										=      update_area_of_max_square(row + 1      ,    col + 1       )
								_lowerCAmelCase    :    int										=      update_area_of_max_square(row + 1      ,    snake_case_       )

								if mat[row][col]:
												_lowerCAmelCase    :    Optional[int]										=      1 + min([right, diagonal, down]       )
												_lowerCAmelCase    :    Any										=      max(largest_square_area[0]      ,    snake_case_       )
												return sub_problem_sol
								else:
												return 0

				_lowerCAmelCase    :    str										=      [0]
				update_area_of_max_square(0      ,    0       )
				return largest_square_area[0]




def 							_UpperCAmelCase  (UpperCamelCase_ : int      ,    UpperCamelCase_ : int      ,    UpperCamelCase_ : list[list[int]]       ):

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

								_lowerCAmelCase    :    Tuple										=      update_area_of_max_square_using_dp_array(snake_case_      ,    col + 1      ,    snake_case_       )
								_lowerCAmelCase    :    List[str]										=      update_area_of_max_square_using_dp_array(row + 1      ,    col + 1      ,    snake_case_       )
								_lowerCAmelCase    :    List[Any]										=      update_area_of_max_square_using_dp_array(row + 1      ,    snake_case_      ,    snake_case_       )

								if mat[row][col]:
												_lowerCAmelCase    :    str										=      1 + min([right, diagonal, down]       )
												_lowerCAmelCase    :    Union[str, Any]										=      max(largest_square_area[0]      ,    snake_case_       )
												_lowerCAmelCase    :    int										=      sub_problem_sol
												return sub_problem_sol
								else:
												return 0

				_lowerCAmelCase    :    List[Any]										=      [0]
				_lowerCAmelCase    :    Dict										=      [[-1] * cols for _ in range(snake_case_       )]
				update_area_of_max_square_using_dp_array(0      ,    0      ,    snake_case_       )

				return largest_square_area[0]




def 							_UpperCAmelCase  (UpperCamelCase_ : int      ,    UpperCamelCase_ : int      ,    UpperCamelCase_ : list[list[int]]       ):
				_lowerCAmelCase    :    Tuple										=      [[0] * (cols + 1) for _ in range(rows + 1       )]
				_lowerCAmelCase    :    List[Any]										=      0
				for row in range(rows - 1      ,    -1      ,    -1       ):
								for col in range(cols - 1      ,    -1      ,    -1       ):
												_lowerCAmelCase    :    int										=      dp_array[row][col + 1]
												_lowerCAmelCase    :    Optional[Any]										=      dp_array[row + 1][col + 1]
												_lowerCAmelCase    :    List[Any]										=      dp_array[row + 1][col]

												if mat[row][col] == 1:
																_lowerCAmelCase    :    Dict										=      1 + min(snake_case_      ,    snake_case_      ,    snake_case_       )
																_lowerCAmelCase    :    Any										=      max(dp_array[row][col]      ,    snake_case_       )
												else:
																_lowerCAmelCase    :    List[Any]										=      0

				return largest_square_area




def 							_UpperCAmelCase  (UpperCamelCase_ : int      ,    UpperCamelCase_ : int      ,    UpperCamelCase_ : list[list[int]]       ):
				_lowerCAmelCase    :    List[Any]										=      [0] * (cols + 1)
				_lowerCAmelCase    :    str										=      [0] * (cols + 1)
				_lowerCAmelCase    :    Tuple										=      0
				for row in range(rows - 1      ,    -1      ,    -1       ):
								for col in range(cols - 1      ,    -1      ,    -1       ):
												_lowerCAmelCase    :    Dict										=      current_row[col + 1]
												_lowerCAmelCase    :    Optional[int]										=      next_row[col + 1]
												_lowerCAmelCase    :    List[str]										=      next_row[col]

												if mat[row][col] == 1:
																_lowerCAmelCase    :    Dict										=      1 + min(snake_case_      ,    snake_case_      ,    snake_case_       )
																_lowerCAmelCase    :    List[str]										=      max(current_row[col]      ,    snake_case_       )
												else:
																_lowerCAmelCase    :    int										=      0
								_lowerCAmelCase    :    Union[str, Any]										=      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]]))







def 							_UpperCAmelCase  (UpperCamelCase_ : str       ):
				'''simple docstring'''
				_lowerCAmelCase    :    List[str]										=      [int(UpperCamelCase_       ) for i in ip_va_address.split("""."""       ) if i.isdigit()]
				return len(UpperCamelCase_       ) == 4 and all(0 <= int(UpperCamelCase_       ) <= 254 for octet in octets       )


if __name__ == "__main__":
	_lowerCamelCase      :  List[str]      						=						input().strip()
	_lowerCamelCase      :  int      						=						"valid" if is_ip_va_address_valid(ip) else "invalid"
	print(F'''{ip} is a {valid_or_invalid} IP v4 address.''')

