"""simple docstring"""
class   lowerCAmelCase_    :



				"""simple docstring"""

				def __init__(				self		,    lowerCAmelCase = ""		,    lowerCAmelCase = False    ):






										"""simple docstring"""

										snake_case								=			{}

										# A node will be a leaf if the tree contains its word
										snake_case								=			is_leaf

										snake_case								=			prefix

				def 		snake_case (				self		,    lowerCAmelCase    ):






										"""simple docstring"""

										snake_case								=			0
										for q, w in zip(self.prefix		,    lowerCAmelCase    ):
																if q != w:
																						break

																x += 1

										return self.prefix[:x], self.prefix[x:], word[x:]

				def 		snake_case (				self		,    lowerCAmelCase    ):






										"""simple docstring"""

										for word in words:
																self.insert(lowerCAmelCase    )

				def 		snake_case (				self		,    lowerCAmelCase    ):






										"""simple docstring"""

										if self.prefix == word:
																snake_case								=			True

										# Case 2: The node has no edges that have a prefix to the word
										# Solution: We create an edge from the current node to a new one
										# containing the word
										elif word[0] not in self.nodes:
																snake_case								=			RadixNode(prefix=lowerCAmelCase		,    is_leaf=lowerCAmelCase    )

										else:
																snake_case								=			self.nodes[word[0]]
																snake_case					,snake_case					,snake_case								=			incoming_node.match(
																    lowerCAmelCase    )

																# Case 3: The node prefix is equal to the matching
																# Solution: We insert remaining word on the next node
																if remaining_prefix == "":
																						self.nodes[matching_string[0]].insert(lowerCAmelCase    )

																# Case 4: The word is greater equal to the matching
																# Solution: Create a node in between both nodes, change
																# prefixes and add the new node for the remaining word
																else:
																						snake_case								=			remaining_prefix

																						snake_case								=			self.nodes[matching_string[0]]
																						snake_case								=			RadixNode(lowerCAmelCase		,    lowerCAmelCase    )
																						snake_case								=			aux_node

																						if remaining_word == "":
																												snake_case								=			True
																						else:
																												self.nodes[matching_string[0]].insert(lowerCAmelCase    )

				def 		snake_case (				self		,    lowerCAmelCase    ):






										"""simple docstring"""

										snake_case								=			self.nodes.get(word[0]		,    lowerCAmelCase    )
										if not incoming_node:
																return False
										else:
																snake_case					,snake_case					,snake_case								=			incoming_node.match(
																    lowerCAmelCase    )
																# If there is remaining prefix, the word can't be on the tree
																if remaining_prefix != "":
																						return False
																# This applies when the word and the prefix are equal
																elif remaining_word == "":
																						return incoming_node.is_leaf
																# We have word remaining so we check the next node
																else:
																						return incoming_node.find(lowerCAmelCase    )

				def 		snake_case (				self		,    lowerCAmelCase    ):






										"""simple docstring"""

										snake_case								=			self.nodes.get(word[0]		,    lowerCAmelCase    )
										if not incoming_node:
																return False
										else:
																snake_case					,snake_case					,snake_case								=			incoming_node.match(
																    lowerCAmelCase    )
																# If there is remaining prefix, the word can't be on the tree
																if remaining_prefix != "":
																						return False
																# We have word remaining so we check the next node
																elif remaining_word != "":
																						return incoming_node.delete(lowerCAmelCase    )
																else:
																						# If it is not a leaf, we don't have to delete
																						if not incoming_node.is_leaf:
																												return False
																						else:
																												# We delete the nodes if no edges go from it
																												if len(incoming_node.nodes    ) == 0:
																																		del self.nodes[word[0]]
																																		# We merge the current node with its only child
																																		if len(self.nodes    ) == 1 and not self.is_leaf:
																																								snake_case								=			list(self.nodes.values()    )[0]
																																								snake_case								=			merging_node.is_leaf
																																								self.prefix += merging_node.prefix
																																								snake_case								=			merging_node.nodes
                    # If there is more than 1 edge, we just mark it as non-leaf
																												elif len(incoming_node.nodes    ) > 1:
																																		snake_case								=			False
																												# If there is 1 edge, we merge it with its child
																												else:
																																		snake_case								=			list(incoming_node.nodes.values()    )[0]
																																		snake_case								=			merging_node.is_leaf
																																		incoming_node.prefix += merging_node.prefix
																																		snake_case								=			merging_node.nodes

																												return True

				def 		snake_case (				self		,    lowerCAmelCase = 0    ):






										"""simple docstring"""

										if self.prefix != "":
																print('-' * height		,    self.prefix		,    '  (leaf)' if self.is_leaf else ''    )

										for value in self.nodes.values():
																value.print_tree(height + 1    )





def    lowerCAmelCase__    (			)					->				bool:





						"""simple docstring"""






						snake_case								=			'banana bananas bandana band apple all beast'.split()
						snake_case								=			RadixNode()
						root.insert_many(_UpperCamelCase					)

						assert all(root.find(_UpperCamelCase					) for word in words					)
						assert not root.find('bandanas'					)
						assert not root.find('apps'					)
						root.delete('all'					)
						assert not root.find('all'					)
						root.delete('banana'					)
						assert not root.find('banana'					)
						assert root.find('bananas'					)

						return True





def    lowerCAmelCase__    (			)					->				None:





						"""simple docstring"""






						assert test_trie()





def    lowerCAmelCase__    (			)					->				None:





						"""simple docstring"""






						snake_case								=			RadixNode()
						snake_case								=			'banana bananas bandanas bandana band apple all beast'.split()
						root.insert_many(_UpperCamelCase					)

						print('Words:' ,			_UpperCamelCase					)
						print('Tree:'					)
						root.print_tree()


if __name__ == "__main__":
					main()



"""simple docstring"""
def    lowerCAmelCase__    (			_UpperCamelCase       :				int ,			_UpperCamelCase       :				int					)					->				int:





						"""simple docstring"""






						return int((input_a, input_a).count(0					) == 0					)





def    lowerCAmelCase__    (			)					->				None:





						"""simple docstring"""






						assert and_gate(0 ,			0					) == 0
						assert and_gate(0 ,			1					) == 0
						assert and_gate(1 ,			0					) == 0
						assert and_gate(1 ,			1					) == 1


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


