
import os
import string
import sys


__snake_case								=  1 << 8

__snake_case								=  {
    """tab""": ord("""\t"""),
    """newline""": ord("""\r"""),
    """esc""": 27,
    """up""": 65 + ARROW_KEY_FLAG,
    """down""": 66 + ARROW_KEY_FLAG,
    """right""": 67 + ARROW_KEY_FLAG,
    """left""": 68 + ARROW_KEY_FLAG,
    """mod_int""": 91,
    """undefined""": sys.maxsize,
    """interrupt""": 3,
    """insert""": 50,
    """delete""": 51,
    """pg_up""": 53,
    """pg_down""": 54,
}

__snake_case								=  KEYMAP["""up"""]
__snake_case								=  KEYMAP["""left"""]

if sys.platform == "win32":
				__snake_case								=  []
				__snake_case								=  {
				    b"""\xe0H""": KEYMAP["""up"""] - ARROW_KEY_FLAG,
				    b"""\x00H""": KEYMAP["""up"""] - ARROW_KEY_FLAG,
				    b"""\xe0P""": KEYMAP["""down"""] - ARROW_KEY_FLAG,
				    b"""\x00P""": KEYMAP["""down"""] - ARROW_KEY_FLAG,
				    b"""\xe0M""": KEYMAP["""right"""] - ARROW_KEY_FLAG,
				    b"""\x00M""": KEYMAP["""right"""] - ARROW_KEY_FLAG,
				    b"""\xe0K""": KEYMAP["""left"""] - ARROW_KEY_FLAG,
				    b"""\x00K""": KEYMAP["""left"""] - ARROW_KEY_FLAG,
				}

for i in range(10):
				__snake_case								=  ord(str(i))






def 							_lowercase							(     )		->		List[Any]:
					'''simple docstring'''


					if os.name == "nt":
										import msvcrt

										SCREAMING_SNAKE_CASE__													= 'mbcs'
										# Flush the keyboard buffer
										while msvcrt.kbhit():
															msvcrt.getch()
										if len(UpperCamelCase_		) == 0:
															# Read the keystroke
															SCREAMING_SNAKE_CASE__													= msvcrt.getch()

															# If it is a prefix char, get second part
															if ch in (b"\x00", b"\xe0"):
																				SCREAMING_SNAKE_CASE__													= ch + msvcrt.getch()
																				# Translate actual Win chars to bullet char types
																				try:
																									SCREAMING_SNAKE_CASE__													= chr(WIN_KEYMAP[cha]		)
																									WIN_CH_BUFFER.append(chr(KEYMAP['mod_int']		)		)
																									WIN_CH_BUFFER.append(UpperCamelCase_		)
																									if ord(UpperCamelCase_		) in (
																									    KEYMAP["insert"] - 1 << 9,
																									    KEYMAP["delete"] - 1 << 9,
																									    KEYMAP["pg_up"] - 1 << 9,
																									    KEYMAP["pg_down"] - 1 << 9,
																									):
																														WIN_CH_BUFFER.append(chr(126		)		)
																									SCREAMING_SNAKE_CASE__													= chr(KEYMAP['esc']		)
																				except KeyError:
																									SCREAMING_SNAKE_CASE__													= cha[1]
															else:
																				SCREAMING_SNAKE_CASE__													= ch.decode(UpperCamelCase_		)
										else:
															SCREAMING_SNAKE_CASE__													= WIN_CH_BUFFER.pop(0		)
					elif os.name == "posix":
										import termios
										import tty

										SCREAMING_SNAKE_CASE__													= sys.stdin.fileno()
										SCREAMING_SNAKE_CASE__													= termios.tcgetattr(UpperCamelCase_		)
										try:
															tty.setraw(UpperCamelCase_		)
															SCREAMING_SNAKE_CASE__													= sys.stdin.read(1		)
										finally:
															termios.tcsetattr(UpperCamelCase_	,	termios.TCSADRAIN	,	UpperCamelCase_		)
					return ch






def 							_lowercase							(     )		->		Dict:
					'''simple docstring'''


					SCREAMING_SNAKE_CASE__													= get_raw_chars()
					if ord(UpperCamelCase_		) in [KEYMAP["interrupt"], KEYMAP["newline"]]:
										return char

					elif ord(UpperCamelCase_		) == KEYMAP["esc"]:
										SCREAMING_SNAKE_CASE__													= get_raw_chars()
										if ord(UpperCamelCase_		) == KEYMAP["mod_int"]:
															SCREAMING_SNAKE_CASE__													= get_raw_chars()
															if ord(UpperCamelCase_		) >= KEYMAP["arrow_begin"] - ARROW_KEY_FLAG and ord(UpperCamelCase_		) <= KEYMAP["arrow_end"] - ARROW_KEY_FLAG:
																				return chr(ord(UpperCamelCase_		) + ARROW_KEY_FLAG		)
															else:
																				return KEYMAP["undefined"]
										else:
															return get_raw_chars()

					else:
										if char in string.printable:
															return char
										else:
															return KEYMAP["undefined"]







def 							_lowercase							(     UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)		->		int:
					'''simple docstring'''


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

										SCREAMING_SNAKE_CASE__													= update_area_of_max_square(UpperCamelCase_	,	col + 1		)
										SCREAMING_SNAKE_CASE__													= update_area_of_max_square(row + 1	,	col + 1		)
										SCREAMING_SNAKE_CASE__													= update_area_of_max_square(row + 1	,	UpperCamelCase_		)

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

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






def 							_lowercase							(     UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)		->		int:
					'''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]

										SCREAMING_SNAKE_CASE__													= update_area_of_max_square_using_dp_array(UpperCamelCase_	,	col + 1	,	UpperCamelCase_		)
										SCREAMING_SNAKE_CASE__													= update_area_of_max_square_using_dp_array(row + 1	,	col + 1	,	UpperCamelCase_		)
										SCREAMING_SNAKE_CASE__													= update_area_of_max_square_using_dp_array(row + 1	,	UpperCamelCase_	,	UpperCamelCase_		)

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

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

					return largest_square_area[0]






def 							_lowercase							(     UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)		->		int:
					'''simple docstring'''


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

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

					return largest_square_area






def 							_lowercase							(     UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)		->		int:
					'''simple docstring'''


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

															if mat[row][col] == 1:
																				SCREAMING_SNAKE_CASE__													= 1 + min(UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)
																				SCREAMING_SNAKE_CASE__													= max(current_row[col]	,	UpperCamelCase_		)
															else:
																				SCREAMING_SNAKE_CASE__													= 0
										SCREAMING_SNAKE_CASE__													= 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]]))





