




from __future__ import annotations

import queue
class     a__					:






						def __init__(     self	,    _A    ):




											"""simple docstring"""



											__lowerCAmelCase            = data
											__lowerCAmelCase            = None
											__lowerCAmelCase            = None







def 			_a   (		):
					print("\n********Press N to stop entering at any point of time********\n"  )
					__lowerCAmelCase            = input("Enter the value of the root node: "  ).strip().lower()
					__lowerCAmelCase            = queue.Queue()
					__lowerCAmelCase            = TreeNode(int(SCREAMING_SNAKE_CASE_  )  )
					q.put(SCREAMING_SNAKE_CASE_  )
					while not q.empty():
										__lowerCAmelCase            = q.get()
										__lowerCAmelCase            = F"""Enter the left node of {node_found.data}: """
										__lowerCAmelCase            = input(SCREAMING_SNAKE_CASE_  ).strip().lower() or "n"
										if check == "n":
															return tree_node
										__lowerCAmelCase            = TreeNode(int(SCREAMING_SNAKE_CASE_  )  )
										__lowerCAmelCase            = left_node
										q.put(SCREAMING_SNAKE_CASE_  )
										__lowerCAmelCase            = F"""Enter the right node of {node_found.data}: """
										__lowerCAmelCase            = input(SCREAMING_SNAKE_CASE_  ).strip().lower() or "n"
										if check == "n":
															return tree_node
										__lowerCAmelCase            = TreeNode(int(SCREAMING_SNAKE_CASE_  )  )
										__lowerCAmelCase            = right_node
										q.put(SCREAMING_SNAKE_CASE_  )
					raise







def 			_a   (		SCREAMING_SNAKE_CASE_							:       Optional[Any]  ):
					if not isinstance(SCREAMING_SNAKE_CASE_   ,   SCREAMING_SNAKE_CASE_  ) or not node:
										return
					print(node.data   ,   end=","  )
					pre_order(node.left  )
					pre_order(node.right  )







def 			_a   (		SCREAMING_SNAKE_CASE_							:       Any  ):
					if not isinstance(SCREAMING_SNAKE_CASE_   ,   SCREAMING_SNAKE_CASE_  ) or not node:
										return
					in_order(node.left  )
					print(node.data   ,   end=","  )
					in_order(node.right  )







def 			_a   (		SCREAMING_SNAKE_CASE_							:       str  ):
					if not isinstance(SCREAMING_SNAKE_CASE_   ,   SCREAMING_SNAKE_CASE_  ) or not node:
										return
					post_order(node.left  )
					post_order(node.right  )
					print(node.data   ,   end=","  )







def 			_a   (		SCREAMING_SNAKE_CASE_							:       int  ):
					if not isinstance(SCREAMING_SNAKE_CASE_   ,   SCREAMING_SNAKE_CASE_  ) or not node:
										return
					__lowerCAmelCase            = queue.Queue()
					q.put(SCREAMING_SNAKE_CASE_  )
					while not q.empty():
										__lowerCAmelCase            = q.get()
										print(node_dequeued.data   ,   end=","  )
										if node_dequeued.left:
															q.put(node_dequeued.left  )
										if node_dequeued.right:
															q.put(node_dequeued.right  )







def 			_a   (		SCREAMING_SNAKE_CASE_							:       List[Any]  ):
					if not isinstance(SCREAMING_SNAKE_CASE_   ,   SCREAMING_SNAKE_CASE_  ) or not node:
										return
					__lowerCAmelCase            = queue.Queue()
					q.put(SCREAMING_SNAKE_CASE_  )
					while not q.empty():
										__lowerCAmelCase            = []
										while not q.empty():
															__lowerCAmelCase            = q.get()
															print(node_dequeued.data   ,   end=","  )
															if node_dequeued.left:
																				list_.append(node_dequeued.left  )
															if node_dequeued.right:
																				list_.append(node_dequeued.right  )
										print()
										for node in list_:
															q.put(SCREAMING_SNAKE_CASE_  )







def 			_a   (		SCREAMING_SNAKE_CASE_							:       List[str]  ):
					if not isinstance(SCREAMING_SNAKE_CASE_   ,   SCREAMING_SNAKE_CASE_  ) or not node:
										return
					__lowerCAmelCase            = []
					__lowerCAmelCase            = node
					while n or stack:
										while n:  # start from root node, find its left child
															print(n.data   ,   end=","  )
															stack.append(SCREAMING_SNAKE_CASE_  )
															__lowerCAmelCase            = n.left
										# end of while means current node doesn't have left child
										__lowerCAmelCase            = stack.pop()
										# start to traverse its right child
										__lowerCAmelCase            = n.right







def 			_a   (		SCREAMING_SNAKE_CASE_							:       Tuple  ):
					if not isinstance(SCREAMING_SNAKE_CASE_   ,   SCREAMING_SNAKE_CASE_  ) or not node:
										return
					__lowerCAmelCase            = []
					__lowerCAmelCase            = node
					while n or stack:
										while n:
															stack.append(SCREAMING_SNAKE_CASE_  )
															__lowerCAmelCase            = n.left
										__lowerCAmelCase            = stack.pop()
										print(n.data   ,   end=","  )
										__lowerCAmelCase            = n.right







def 			_a   (		SCREAMING_SNAKE_CASE_							:       Tuple  ):
					if not isinstance(SCREAMING_SNAKE_CASE_   ,   SCREAMING_SNAKE_CASE_  ) or not node:
										return
					__lowerCAmelCase     ,							__lowerCAmelCase            = [], []
					__lowerCAmelCase            = node
					stacka.append(SCREAMING_SNAKE_CASE_  )
					while stacka:  # to find the reversed order of post order, store it in stack2
										__lowerCAmelCase            = stacka.pop()
										if n.left:
															stacka.append(n.left  )
										if n.right:
															stacka.append(n.right  )
										stacka.append(SCREAMING_SNAKE_CASE_  )
					while stacka:  # pop up from stack2 will be the post order
										print(stacka.pop().data   ,   end=","  )







def 			_a   (		SCREAMING_SNAKE_CASE_							:       Optional[Any] = ""   ,   SCREAMING_SNAKE_CASE_							:       str=50   ,   SCREAMING_SNAKE_CASE_							:       str="*"  ):
					if not s:
										return "\n" + width * char
					__lowerCAmelCase     ,							__lowerCAmelCase            = divmod(width - len(SCREAMING_SNAKE_CASE_  ) - 2   ,   2  )
					return F"""{left * char} {s} {(left + extra) * char}"""


if __name__ == "__main__":
					import doctest

					doctest.testmod()
					print(prompt("""Binary Tree Traversals"""))

					UpperCamelCase__					    =    build_tree()
					print(prompt("""Pre Order Traversal"""))
					pre_order(node)
					print(prompt() + """\n""")

					print(prompt("""In Order Traversal"""))
					in_order(node)
					print(prompt() + """\n""")

					print(prompt("""Post Order Traversal"""))
					post_order(node)
					print(prompt() + """\n""")

					print(prompt("""Level Order Traversal"""))
					level_order(node)
					print(prompt() + """\n""")

					print(prompt("""Actual Level Order Traversal"""))
					level_order_actual(node)
					print("""*""" * 50 + """\n""")

					print(prompt("""Pre Order Traversal - Iteration Version"""))
					pre_order_iter(node)
					print(prompt() + """\n""")

					print(prompt("""In Order Traversal - Iteration Version"""))
					in_order_iter(node)
					print(prompt() + """\n""")

					print(prompt("""Post Order Traversal - Iteration Version"""))
					post_order_iter(node)
					print(prompt())










from math import ceil, sqrt







def 			_a   (		SCREAMING_SNAKE_CASE_							:       int = 1_00_00_00  ):
					__lowerCAmelCase            = 0

					for outer_width in range(3   ,   (limit // 4) + 2  ):
										if outer_width**2 > limit:
															__lowerCAmelCase            = max(ceil(sqrt(outer_width**2 - limit  )  )   ,   1  )
										else:
															__lowerCAmelCase            = 1
										if (outer_width - hole_width_lower_bound) % 2:
															hole_width_lower_bound += 1

										answer += (outer_width - hole_width_lower_bound - 2) // 2 + 1

					return answer


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




