



_A       =					[
    ["ab-e1", "ac-e3", "ad-e5", "bc-e4", "bd-e2", "be-e6", "bh-e12", "cd-e2", "ce-e4",
     "de-e1", "df-e8", "dg-e5", "dh-e10", "ef-e3", "eg-e2", "fg-e6", "gh-e6", "hi-e3"],
    ["ab-e1", "ac-e3", "ad-e5", "bc-e4", "bd-e2", "be-e6", "cd-e2", "de-e1", "df-e8",
     "ef-e3", "eg-e2", "fg-e6"],
    ["ab-e1", "ac-e3", "bc-e4", "bd-e2", "de-e1", "df-e8", "dg-e5", "ef-e3", "eg-e2",
     "eh-e12", "fg-e6", "fh-e10", "gh-e6"],
    ["ab-e1", "ac-e3", "bc-e4", "bd-e2", "bh-e12", "cd-e2", "df-e8", "dh-e10"],
    ["ab-e1", "ac-e3", "ad-e5", "bc-e4", "bd-e2", "cd-e2", "ce-e4", "de-e1", "df-e8",
     "dg-e5", "ef-e3", "eg-e2", "fg-e6"]
]






def        lowerCamelCase__    (    __lowerCAmelCase  :  Optional[Any]    ):




			"""simple docstring"""


			lowerCAmelCase_      =     set()
			for row in edge_array:
						for item in row:
									distinct_edge.add(item[0]    )
			return list(__A    )






def        lowerCamelCase__    (    __lowerCAmelCase  :  Dict   ,							__lowerCAmelCase  :  Tuple    ):




			"""simple docstring"""


			lowerCAmelCase_      =     ["0"] * len(__A    )
			for i, row in enumerate(__A    ):
						for item in row:
									if distinct_edge in item[0]:
												lowerCAmelCase_      =     "1"
												break
			return "".join(__A    )






def        lowerCamelCase__    (    __lowerCAmelCase  :  List[str]    ):




			"""simple docstring"""


			lowerCAmelCase_      =     get_distinct_edge(__A    )
			lowerCAmelCase_      =     {}

			for item in distinct_edge:
						lowerCAmelCase_      =     get_bitcode(__A   ,							__A    )
						# print('bit',bit)
						# bt=''.join(bit)
						lowerCAmelCase_      =     bit.count("1"    )
						lowerCAmelCase_      =     [s, bit]
			# Store [Distinct edge, WT(Bitcode), Bitcode] in descending order
			lowerCAmelCase_      =     [
			    [k, v[0], v[1]]
			    for k, v in sorted(frequency_table.items()   ,							key=lambda __lowerCAmelCase    : v[1][0]   ,							reverse=__A    )
			]
			return sorted_frequency_table






def        lowerCamelCase__    (    __lowerCAmelCase  :  Dict    ):




			"""simple docstring"""


			lowerCAmelCase_      =     {}
			for _, item in enumerate(__A    ):
						nodes.setdefault(item[2]   ,							[]    ).append(item[0]    )
			return nodes






def        lowerCamelCase__    (    __lowerCAmelCase  :  int    ):




			"""simple docstring"""


			lowerCAmelCase_      =     {}
			for key, value in nodes.items():
						lowerCAmelCase_      =     value
			return cluster






def        lowerCamelCase__    (    __lowerCAmelCase  :  Tuple    ):




			"""simple docstring"""


			return [i * 100 / len(__A    ) for i in cluster]






def        lowerCamelCase__    (    ):




			"""simple docstring"""


			print("\nNodes\n"    )
			for key, value in nodes.items():
						print(__A   ,							__A    )
			print("\nSupport\n"    )
			print(__A    )
			print("\n Cluster \n"    )
			for key, value in sorted(cluster.items()   ,							reverse=__A    ):
						print(__A   ,							__A    )
			print("\n Graph\n"    )
			for key, value in graph.items():
						print(__A   ,							__A    )
			print("\n Edge List of Frequent subgraphs \n"    )
			for edge_list in freq_subgraph_edge_list:
						print(__A    )






def        lowerCamelCase__    (    __lowerCAmelCase  :  int   ,							__lowerCAmelCase  :  int   ,							__lowerCAmelCase  :  Optional[Any]   ,							__lowerCAmelCase  :  List[str]    ):




			"""simple docstring"""


			for i in cluster[ca]:
						lowerCAmelCase_      =     0
						lowerCAmelCase_      =     ca + 1
						while ca < max(cluster.keys()    ):
									for j in cluster[ca]:
												if int(__A   ,							2    ) & int(__A   ,							2    ) == int(__A   ,							2    ):
															if tuple(nodes[i]    ) in graph:
																		graph[tuple(nodes[i]    )].append(nodes[j]    )
															else:
																		lowerCAmelCase_      =     [nodes[j]]
															count += 1
									if count == 0:
												lowerCAmelCase_      =     ca + 1
									else:
												break






def        lowerCamelCase__    (    __lowerCAmelCase  :  List[str]   ,							__lowerCAmelCase  :  int    ):




			"""simple docstring"""


			lowerCAmelCase_      =     cluster[max(cluster.keys()    )]
			lowerCAmelCase_      =     "Header"
			lowerCAmelCase_      =     {}
			for i in x:
						if (["Header"],) in graph:
									graph[(["Header"],)].append(x[i]    )
						else:
									lowerCAmelCase_      =     [x[i]]
			for i in x:
						lowerCAmelCase_      =     [["Header"]]
			lowerCAmelCase_      =     1
			while i < max(__A    ) - 1:
						create_edge(__A   ,							__A   ,							__A   ,							__A    )
						lowerCAmelCase_      =     i + 1
			return graph






def        lowerCamelCase__    (    __lowerCAmelCase  :  List[str]   ,							__lowerCAmelCase  :  Optional[Any]   ,							__lowerCAmelCase  :  Dict   ,							__lowerCAmelCase  :  Any=None    ):




			"""simple docstring"""


			lowerCAmelCase_      =     (path or []) + [start]
			if start == end:
						paths.append(__A    )
			for node in graph[start]:
						if tuple(__A    ) not in path:
									my_dfs(__A   ,							tuple(__A    )   ,							__A   ,							__A    )






def        lowerCamelCase__    (    __lowerCAmelCase  :  Dict   ,							__lowerCAmelCase  :  int   ,							__lowerCAmelCase  :  int    ):




			"""simple docstring"""


			lowerCAmelCase_      =     int(s / 100 * (len(__A    ) - 1)    )
			for i in cluster[k]:
						my_dfs(__A   ,							tuple(cluster[k][i]    )   ,							(["Header"],)    )






def        lowerCamelCase__    (    __lowerCAmelCase  :  List[str]    ):




			"""simple docstring"""


			lowerCAmelCase_      =     []
			for edges in paths:
						lowerCAmelCase_      =     []
						for j in range(len(__A    ) - 1    ):
									lowerCAmelCase_      =     list(edges[j]    )
									for e in temp:
												lowerCAmelCase_      =     (e[0], e[1])
												el.append(__A    )
						freq_sub_el.append(__A    )
			return freq_sub_el






def        lowerCamelCase__    (    __lowerCAmelCase  :  str    ):




			"""simple docstring"""


			for i in range(len(__A    )    ):
						for j in range(len(edge_array[i]    )    ):
									lowerCAmelCase_      =     edge_array[i][j].split("-"    )
									lowerCAmelCase_      =     t


if __name__ == "__main__":
			preprocess(edge_array)
			_A       =					get_frequency_table(edge_array)
			_A       =					get_nodes(frequency_table)
			_A       =					get_cluster(nodes)
			_A       =					get_support(cluster)
			_A       =					construct_graph(cluster, nodes)
			find_freq_subgraph_given_support(60, cluster, graph)
			_A       =					[]
			_A       =					freq_subgraphs_edge_list(paths)
			print_all()





import math





class      _lowerCAmelCase :




				def __init__( self    ,    _UpperCamelCase					)    ->				Dict:
							lowerCAmelCase_      =     len(_UpperCamelCase					)
							lowerCAmelCase_      =     [0] * (
							    4 * self.N
							)  # approximate the overall size of segment tree with array N
							self.build(1    ,    0    ,    self.N - 1					)




				def 					__a						( self    ,    _UpperCamelCase					)    ->				List[str]:
							return idx * 2




				def 					__a						( self    ,    _UpperCamelCase					)    ->				Tuple:
							return idx * 2 + 1




				def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				int:  # noqa: E741
							if l == r:
										lowerCAmelCase_      =     A[l]
							else:
										lowerCAmelCase_      =     (l + r) // 2
										self.build(self.left(_UpperCamelCase					)    ,    _UpperCamelCase    ,    _UpperCamelCase					)
										self.build(self.right(_UpperCamelCase					)    ,    mid + 1    ,    _UpperCamelCase					)
										lowerCAmelCase_      =     max(self.st[self.left(_UpperCamelCase					)]    ,    self.st[self.right(_UpperCamelCase					)]					)




				def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				int:
							return self.update_recursive(1    ,    0    ,    self.N - 1    ,    a - 1    ,    b - 1    ,    _UpperCamelCase					)




				def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				str:  # noqa: E741
							if r < a or l > b:
										return True
							if l == r:
										lowerCAmelCase_      =     val
										return True
							lowerCAmelCase_      =     (l + r) // 2
							self.update_recursive(self.left(_UpperCamelCase					)    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)
							self.update_recursive(self.right(_UpperCamelCase					)    ,    mid + 1    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)
							lowerCAmelCase_      =     max(self.st[self.left(_UpperCamelCase					)]    ,    self.st[self.right(_UpperCamelCase					)]					)
							return True




				def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				Optional[Any]:
							return self.query_recursive(1    ,    0    ,    self.N - 1    ,    a - 1    ,    b - 1					)




				def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				Any:  # noqa: E741
							if r < a or l > b:
										return -math.inf
							if l >= a and r <= b:
										return self.st[idx]
							lowerCAmelCase_      =     (l + r) // 2
							lowerCAmelCase_      =     self.query_recursive(self.left(_UpperCamelCase					)    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)
							lowerCAmelCase_      =     self.query_recursive(self.right(_UpperCamelCase					)    ,    mid + 1    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)
							return max(_UpperCamelCase    ,    _UpperCamelCase					)




				def 					__a						( self					)    ->				int:
							lowerCAmelCase_      =     []
							for i in range(1    ,    N + 1					):
										show_list += [self.query(_UpperCamelCase    ,    _UpperCamelCase					)]
							print(_UpperCamelCase					)


if __name__ == "__main__":
			_A       =					[1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
			_A       =					15
			_A       =					SegmentTree(A)
			print(segt.query(4, 6))
			print(segt.query(7, 11))
			print(segt.query(7, 12))
			segt.update(1, 3, 1_11)
			print(segt.query(1, 15))
			segt.update(7, 8, 2_35)
			segt.show_data()



