


def 							lowerCAmelCase_	(   __lowerCamelCase				,      __lowerCamelCase      ):
							print("\nThe shortest path matrix using Floyd Warshall algorithm\n"      )
							for i in range(__lowerCamelCase      ):
														for j in range(__lowerCamelCase      ):
																					if dist[i][j] != float("inf"      ):
																												print(int(dist[i][j]      )				,      end="\t"      )
																					else:
																												print("INF"				,      end="\t"      )
														print()







def 							lowerCAmelCase_	(   __lowerCamelCase				,      __lowerCamelCase      ):
							__snake_case						:     int									=  [[float("inf"      ) for _ in range(__lowerCamelCase      )] for _ in range(__lowerCamelCase      )]

							for i in range(__lowerCamelCase      ):
														for j in range(__lowerCamelCase      ):
																					__snake_case						:     Optional[Any]									=  graph[i][j]

																					# check vertex k against all other vertices (i, j)
							for k in range(__lowerCamelCase      ):
														# looping through rows of graph array
														for i in range(__lowerCamelCase      ):
																					# looping through columns of graph array
																					for j in range(__lowerCamelCase      ):
																												if (
																												    dist[i][k] != float("inf"      )
																												    and dist[k][j] != float("inf"      )
																												    and dist[i][k] + dist[k][j] < dist[i][j]
																												):
																																			__snake_case						:     List[Any]									=  dist[i][k] + dist[k][j]

							_print_dist(__lowerCamelCase				,      __lowerCamelCase      )
							return dist, v


if __name__ == "__main__":
			_snake_case	:						int         =							int(input("Enter number of vertices: "))
			_snake_case	:						List[str]         =							int(input("Enter number of edges: "))

			_snake_case	:						str         =							[[float("inf") for i in range(v)] for j in range(v)]

			for i in range(v):
						_snake_case	:						Dict         =							0.0

						# src and dst are indices that must be within the array size graph[e][v]
						# failure to follow this will result in an error
			for i in range(e):
						print("\nEdge ", i + 1)
						_snake_case	:						str         =							int(input("Enter source:"))
						_snake_case	:						Any         =							int(input("Enter destination:"))
						_snake_case	:						Tuple         =							float(input("Enter weight:"))
						_snake_case	:						Union[str, Any]         =							weight

			floyd_warshall(graph, v)

			# Example Input
			# Enter number of vertices: 3
			# Enter number of edges: 2

			# # generated graph from vertex and edge inputs
			# [[inf, inf, inf], [inf, inf, inf], [inf, inf, inf]]
			# [[0.0, inf, inf], [inf, 0.0, inf], [inf, inf, 0.0]]

			# specify source, destination and weight for edge #1
			# Edge  1
			# Enter source:1
			# Enter destination:2
			# Enter weight:2

			# specify source, destination and weight for edge #2
			# Edge  2
			# Enter source:2
			# Enter destination:1
			# Enter weight:1

			# # Expected Output from the vertice, edge and src, dst, weight inputs!!
			# 0		INF	INF
			# INF	0	2
			# INF	1	0






from collections.abc import Sequence
from queue import Queue






class     __a			:



	def __init__(    self				:     str					,						snake_case_				:     List[str]					,						snake_case_				:     Tuple					,						snake_case_				:     Tuple					,						snake_case_				:     Optional[Any]=None					,						snake_case_				:     Dict=None)->				Optional[int]:
						__lowerCAmelCase						 =start
						__lowerCAmelCase						 =end
						__lowerCAmelCase						 =val
						__lowerCAmelCase						 =(start + end) // 2
						__lowerCAmelCase						 =left
						__lowerCAmelCase						 =right



	def __repr__(    self				:     List[Any])->				Dict:
						return F"""SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})"""






class     __a			:



	def __init__(    self				:     List[str]					,						snake_case_				:     Sequence					,						snake_case_				:     int)->				str:
						__lowerCAmelCase						 =collection
						__lowerCAmelCase						 =function
						if self.collection:
											__lowerCAmelCase						 =self._build_tree(0					,						len(snake_case_) - 1)



	def 		UpperCamelCase				(    self				:     Dict					,						snake_case_				:     Tuple					,						snake_case_				:     Optional[int])->				Optional[int]:
						self._update_tree(self.root					,						snake_case_					,						snake_case_)



	def 		UpperCamelCase				(    self				:     Optional[Any]					,						snake_case_				:     Any					,						snake_case_				:     Union[str, Any])->				Union[str, Any]:
						return self._query_range(self.root					,						snake_case_					,						snake_case_)



	def 		UpperCamelCase				(    self				:     List[str]					,						snake_case_				:     List[str]					,						snake_case_				:     List[str])->				List[Any]:
						if start == end:
											return SegmentTreeNode(snake_case_					,						snake_case_					,						self.collection[start])
						__lowerCAmelCase						 =(start + end) // 2
						__lowerCAmelCase						 =self._build_tree(snake_case_					,						snake_case_)
						__lowerCAmelCase						 =self._build_tree(mid + 1					,						snake_case_)
						return SegmentTreeNode(snake_case_					,						snake_case_					,						self.fn(left.val					,						right.val)					,						snake_case_					,						snake_case_)



	def 		UpperCamelCase				(    self				:     Dict					,						snake_case_				:     Tuple					,						snake_case_				:     int					,						snake_case_				:     int)->				List[Any]:
						if node.start == i and node.end == i:
											__lowerCAmelCase						 =val
											return
						if i <= node.mid:
											self._update_tree(node.left					,						snake_case_					,						snake_case_)
						else:
											self._update_tree(node.right					,						snake_case_					,						snake_case_)
						__lowerCAmelCase						 =self.fn(node.left.val					,						node.right.val)



	def 		UpperCamelCase				(    self				:     Tuple					,						snake_case_				:     str					,						snake_case_				:     str					,						snake_case_				:     List[Any])->				Optional[int]:
						if node.start == i and node.end == j:
											return node.val

						if i <= node.mid:
											if j <= node.mid:
																# range in left child tree
																return self._query_range(node.left					,						snake_case_					,						snake_case_)
											else:
																# range in left child tree and right child tree
																return self.fn(
																    self._query_range(node.left					,						snake_case_					,						node.mid)					,						self._query_range(node.right					,						node.mid + 1					,						snake_case_)					,						)
						else:
											# range in right child tree
											return self._query_range(node.right					,						snake_case_					,						snake_case_)



	def 		UpperCamelCase				(    self				:     List[str])->				Tuple:
						if self.root is not None:
											__lowerCAmelCase						 =Queue()
											queue.put(self.root)
											while not queue.empty():
																__lowerCAmelCase						 =queue.get()
																yield node

																if node.left is not None:
																					queue.put(node.left)

																if node.right is not None:
																					queue.put(node.right)


if __name__ == "__main__":
				import operator

				for fn in [operator.add, max, min]:
								print('''*''' * 50)
								lowercase_													=      SegmentTree([2, 1, 5, 3, 4], fn)
								for node in arr.traverse():
												print(node)
								print()

								arr.update(1, 5)
								for node in arr.traverse():
												print(node)
								print()

								print(arr.query_range(3, 4))  # 7
								print(arr.query_range(2, 2))  # 5
								print(arr.query_range(1, 3))  # 13
								print()




