


'''simple docstring'''


class 					lowercase__						:





							'''simple docstring'''


							def __init__(					self					,      __snake_case						):
											_SCREAMING_SNAKE_CASE				: Union[str, Any]  	=   val
											# Number of nodes in left subtree
											_SCREAMING_SNAKE_CASE				: Any  	=   0
											_SCREAMING_SNAKE_CASE				: List[str]  	=   None
											_SCREAMING_SNAKE_CASE				: Union[str, Any]  	=   None
											_SCREAMING_SNAKE_CASE				: str  	=   None






							def UpperCAmelCase_			(					self					,      __snake_case						):
											assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

											if self.val < other.val:
															_SCREAMING_SNAKE_CASE				: str  	=   self.right
															_SCREAMING_SNAKE_CASE				: Any  	=   None
															if self.right:
																			_SCREAMING_SNAKE_CASE				: Optional[Any]  	=   other
															_SCREAMING_SNAKE_CASE				: str  	=   other
															_SCREAMING_SNAKE_CASE				: str  	=   self.left_tree_size * 2 + 1
															return self
											else:
															_SCREAMING_SNAKE_CASE				: Union[str, Any]  	=   other.right
															_SCREAMING_SNAKE_CASE				: Union[str, Any]  	=   None
															if other.right:
																			_SCREAMING_SNAKE_CASE				: Tuple  	=   self
															_SCREAMING_SNAKE_CASE				: Dict  	=   self
															_SCREAMING_SNAKE_CASE				: Tuple  	=   other.left_tree_size * 2 + 1
															return other





class 					lowercase__						:





							'''simple docstring'''


							def __init__(					self					,      __snake_case=None					,      __snake_case=None					,      __snake_case=0						):
											_SCREAMING_SNAKE_CASE				: List[Any]  	=   heap_size
											_SCREAMING_SNAKE_CASE				: List[Any]  	=   bottom_root
											_SCREAMING_SNAKE_CASE				: Optional[Any]  	=   min_node






							def UpperCAmelCase_			(					self					,      __snake_case						):

											# Empty heaps corner cases
											if other.size == 0:
															return None
											if self.size == 0:
															_SCREAMING_SNAKE_CASE				: Dict  	=   other.size
															_SCREAMING_SNAKE_CASE				: Dict  	=   other.bottom_root
															_SCREAMING_SNAKE_CASE				: int  	=   other.min_node
															return None
											# Update size
											_SCREAMING_SNAKE_CASE				: Any  	=   self.size + other.size

											# Update min.node
											if self.min_node.val > other.min_node.val:
															_SCREAMING_SNAKE_CASE				: int  	=   other.min_node
											# Merge

											# Order roots by left_subtree_size
											_SCREAMING_SNAKE_CASE				: List[str]  	=   []
											_SCREAMING_SNAKE_CASE	, _SCREAMING_SNAKE_CASE				: Dict  	=   self.bottom_root, other.bottom_root
											while i or j:
															if i and ((not j) or i.left_tree_size < j.left_tree_size):
																			combined_roots_list.append((i, True)						)
																			_SCREAMING_SNAKE_CASE				: str  	=   i.parent
															else:
																			combined_roots_list.append((j, False)						)
																			_SCREAMING_SNAKE_CASE				: Dict  	=   j.parent
        # Insert links between them
											for i in range(len(__snake_case						) - 1						):
															if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
																			_SCREAMING_SNAKE_CASE				: Any  	=   combined_roots_list[i + 1][0]
																			_SCREAMING_SNAKE_CASE				: Optional[Any]  	=   combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
											_SCREAMING_SNAKE_CASE				: Tuple  	=   combined_roots_list[0][0]
											while i.parent:
															if (
															    (i.left_tree_size == i.parent.left_tree_size) and (not i.parent.parent)
															) or (
															    i.left_tree_size == i.parent.left_tree_size
															    and i.left_tree_size != i.parent.parent.left_tree_size
															):
																			# Neighbouring Nodes
																			_SCREAMING_SNAKE_CASE				: Any  	=   i.left
																			_SCREAMING_SNAKE_CASE				: Dict  	=   i.parent.parent

																			# Merging trees
																			_SCREAMING_SNAKE_CASE				: Tuple  	=   i.merge_trees(i.parent						)

																			# Updating links
																			_SCREAMING_SNAKE_CASE				: Any  	=   previous_node
																			_SCREAMING_SNAKE_CASE				: List[str]  	=   next_node
																			if previous_node:
																							_SCREAMING_SNAKE_CASE				: List[Any]  	=   i
																			if next_node:
																							_SCREAMING_SNAKE_CASE				: str  	=   i
															else:
																			_SCREAMING_SNAKE_CASE				: Any  	=   i.parent
        # Updating self.bottom_root
											while i.left:
															_SCREAMING_SNAKE_CASE				: Optional[int]  	=   i.left
											_SCREAMING_SNAKE_CASE				: str  	=   i

											# Update other
											_SCREAMING_SNAKE_CASE				: Union[str, Any]  	=   self.size
											_SCREAMING_SNAKE_CASE				: Union[str, Any]  	=   self.bottom_root
											_SCREAMING_SNAKE_CASE				: Any  	=   self.min_node

											# Return the merged heap
											return self






							def UpperCAmelCase_			(					self					,      __snake_case						):
											if self.size == 0:
															_SCREAMING_SNAKE_CASE				: Optional[Any]  	=   Node(__snake_case						)
															_SCREAMING_SNAKE_CASE				: Optional[Any]  	=   1
															_SCREAMING_SNAKE_CASE				: Optional[int]  	=   self.bottom_root
											else:
															# Create new node
															_SCREAMING_SNAKE_CASE				: Tuple  	=   Node(__snake_case						)

															# Update size
															self.size += 1

															# update min_node
															if val < self.min_node.val:
																			_SCREAMING_SNAKE_CASE				: Optional[Any]  	=   new_node
															# Put new_node as a bottom_root in heap
															_SCREAMING_SNAKE_CASE				: Tuple  	=   new_node
															_SCREAMING_SNAKE_CASE				: str  	=   self.bottom_root
															_SCREAMING_SNAKE_CASE				: Optional[Any]  	=   new_node

															# Consecutively merge roots with same left_tree_size
															while (
															    self.bottom_root.parent
															    and self.bottom_root.left_tree_size
															    == self.bottom_root.parent.left_tree_size
															):
																			# Next node
																			_SCREAMING_SNAKE_CASE				: Union[str, Any]  	=   self.bottom_root.parent.parent

																			# Merge
																			_SCREAMING_SNAKE_CASE				: Any  	=   self.bottom_root.merge_trees(self.bottom_root.parent						)

																			# Update Links
																			_SCREAMING_SNAKE_CASE				: Optional[Any]  	=   next_node
																			_SCREAMING_SNAKE_CASE				: Dict  	=   None
																			if next_node:
																							_SCREAMING_SNAKE_CASE				: List[str]  	=   self.bottom_root






							def UpperCAmelCase_			(					self						):
											return self.min_node.val






							def UpperCAmelCase_			(					self						):
											return self.size == 0






							def UpperCAmelCase_			(					self						):
											_SCREAMING_SNAKE_CASE				: str  	=   self.min_node.val

											# Last element in heap corner case
											if self.size == 1:
															# Update size
															_SCREAMING_SNAKE_CASE				: Any  	=   0

															# Update bottom root
															_SCREAMING_SNAKE_CASE				: List[Any]  	=   None

															# Update min_node
															_SCREAMING_SNAKE_CASE				: Any  	=   None

															return min_value
											# No right subtree corner case
											# The structure of the tree implies that this should be the bottom root
											# and there is at least one other root
											if self.min_node.right is None:
															# Update size
															self.size -= 1

															# Update bottom root
															_SCREAMING_SNAKE_CASE				: Union[str, Any]  	=   self.bottom_root.parent
															_SCREAMING_SNAKE_CASE				: Tuple  	=   None

															# Update min_node
															_SCREAMING_SNAKE_CASE				: Tuple  	=   self.bottom_root
															_SCREAMING_SNAKE_CASE				: str  	=   self.bottom_root.parent
															while i:
																			if i.val < self.min_node.val:
																							_SCREAMING_SNAKE_CASE				: Any  	=   i
																			_SCREAMING_SNAKE_CASE				: List[str]  	=   i.parent
															return min_value
											# General case
											# Find the BinomialHeap of the right subtree of min_node
											_SCREAMING_SNAKE_CASE				: Optional[Any]  	=   self.min_node.right
											_SCREAMING_SNAKE_CASE				: List[str]  	=   None
											_SCREAMING_SNAKE_CASE				: Dict  	=   bottom_of_new
											_SCREAMING_SNAKE_CASE				: Union[str, Any]  	=   1

											# Size, min_node and bottom_root
											while bottom_of_new.left:
															_SCREAMING_SNAKE_CASE				: Union[str, Any]  	=   size_of_new * 2 + 1
															_SCREAMING_SNAKE_CASE				: List[str]  	=   bottom_of_new.left
															if bottom_of_new.val < min_of_new.val:
																			_SCREAMING_SNAKE_CASE				: Optional[int]  	=   bottom_of_new
        # Corner case of single root on top left path
											if (not self.min_node.left) and (not self.min_node.parent):
															_SCREAMING_SNAKE_CASE				: List[str]  	=   size_of_new
															_SCREAMING_SNAKE_CASE				: Union[str, Any]  	=   bottom_of_new
															_SCREAMING_SNAKE_CASE				: List[Any]  	=   min_of_new
															# print("Single root, multiple nodes case")
															return min_value
											# Remaining cases
											# Construct heap of right subtree
											_SCREAMING_SNAKE_CASE				: Tuple  	=   BinomialHeap(
											    bottom_root=__snake_case					,      min_node=__snake_case					,      heap_size=__snake_case						)

											# Update size
											_SCREAMING_SNAKE_CASE				: Optional[int]  	=   self.size - 1 - size_of_new

											# Neighbour nodes
											_SCREAMING_SNAKE_CASE				: Optional[int]  	=   self.min_node.left
											_SCREAMING_SNAKE_CASE				: str  	=   self.min_node.parent

											# Initialize new bottom_root and min_node
											_SCREAMING_SNAKE_CASE				: Union[str, Any]  	=   previous_node or next_node
											_SCREAMING_SNAKE_CASE				: Optional[Any]  	=   next_node

											# Update links of previous_node and search below for new min_node and
											# bottom_root
											if previous_node:
															_SCREAMING_SNAKE_CASE				: Any  	=   next_node

															# Update bottom_root and search for min_node below
															_SCREAMING_SNAKE_CASE				: List[Any]  	=   previous_node
															_SCREAMING_SNAKE_CASE				: Dict  	=   previous_node
															while self.bottom_root.left:
																			_SCREAMING_SNAKE_CASE				: Dict  	=   self.bottom_root.left
																			if self.bottom_root.val < self.min_node.val:
																							_SCREAMING_SNAKE_CASE				: List[str]  	=   self.bottom_root
											if next_node:
															_SCREAMING_SNAKE_CASE				: int  	=   previous_node

															# Search for new min_node above min_node
															_SCREAMING_SNAKE_CASE				: Tuple  	=   next_node
															while i:
																			if i.val < self.min_node.val:
																							_SCREAMING_SNAKE_CASE				: str  	=   i
																			_SCREAMING_SNAKE_CASE				: Optional[int]  	=   i.parent
        # Merge heaps
											self.merge_heaps(__snake_case						)

											return min_value






							def UpperCAmelCase_			(					self						):
											_SCREAMING_SNAKE_CASE				: Optional[int]  	=   self.bottom_root
											while top_root.parent:
															_SCREAMING_SNAKE_CASE				: Any  	=   top_root.parent
											# preorder
											_SCREAMING_SNAKE_CASE				: Tuple  	=   []
											self.__traversal(__snake_case					,      __snake_case						)
											return heap_pre_order






							def UpperCAmelCase_			(					self					,      __snake_case					,      __snake_case					,      __snake_case=0						):
											if curr_node:
															preorder.append((curr_node.val, level)						)
															self.__traversal(curr_node.left					,      __snake_case					,      level + 1						)
															self.__traversal(curr_node.right					,      __snake_case					,      level + 1						)
											else:
															preorder.append(("""#""", level)						)






							def __str__(					self						):
											if self.is_empty():
															return ""
											_SCREAMING_SNAKE_CASE				: List[str]  	=   self.pre_order()

											return "\n".join(("""-""" * level + str(__snake_case						)) for value, level in preorder_heap						)


# Unit Tests
if __name__ == "__main__":
				import doctest

				doctest.testmod()








'''simple docstring'''


def     snake_case_     (						SCREAMING_SNAKE_CASE__							,   SCREAMING_SNAKE_CASE__  ):







				"""simple docstring"""





				return (input_a, input_a).count(0  ) % 2







def     snake_case_     (						):







				"""simple docstring"""





				assert xor_gate(0							,   0  ) == 0
				assert xor_gate(0							,   1  ) == 1
				assert xor_gate(1							,   0  ) == 1
				assert xor_gate(1							,   1  ) == 0


if __name__ == "__main__":
				print(xor_gate(0, 0))
				print(xor_gate(0, 1))




