"""simple docstring"""







from __future__ import annotations

from queue import Queue


def 	a__   (		UpperCAmelCase__							:      int		,      UpperCAmelCase__							:      int      )->						tuple[int, int]:
						a ^= b
						b ^= a
						a ^= b
						return a, b


def 	a__   (		UpperCAmelCase__							:      int		,      UpperCAmelCase__							:      list[list[int]]      )->						list[list[int]]:
						UpperCAmelCase__       						=		1
						while (1 << j) < max_node:
												for i in range(1		,      max_node + 1      ):
																		UpperCAmelCase__       						=		parent[j - 1][parent[j - 1][i]]
												j += 1
						return parent


def 	a__   (		UpperCAmelCase__							:      int		,      UpperCAmelCase__							:      int		,      UpperCAmelCase__							:      list[int]		,      UpperCAmelCase__							:      list[list[int]]      )->						int:
						# u must be deeper in the tree than v
						if level[u] < level[v]:
												UpperCAmelCase__						,   UpperCAmelCase__       						=		swap(UpperCAmelCase__		,      UpperCAmelCase__      )
						# making depth of u same as depth of v
						for i in range(1_8		,      -1		,      -1      ):
												if level[u] - (1 << i) >= level[v]:
																		UpperCAmelCase__       						=		parent[i][u]
    # at the same depth if u==v that mean lca is found
						if u == v:
												return u
						# moving both nodes upwards till lca in found
						for i in range(1_8		,      -1		,      -1      ):
												if parent[i][u] not in [0, parent[i][v]]:
																		UpperCAmelCase__						,   UpperCAmelCase__       						=		parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
						return parent[0][u]


def 	a__   (		UpperCAmelCase__							:      list[int]		,      UpperCAmelCase__							:      list[list[int]]		,      UpperCAmelCase__							:      int		,      UpperCAmelCase__							:      dict[int, list[int]]		,      UpperCAmelCase__							:      int = 1		,      )->						tuple[list[int], list[list[int]]]:
						UpperCAmelCase__       						=		0
						UpperCAmelCase__       						=		Queue(maxsize=UpperCAmelCase__      )
						q.put(UpperCAmelCase__      )
						while q.qsize() != 0:
												UpperCAmelCase__       						=		q.get()
												for v in graph[u]:
																		if level[v] == -1:
																								UpperCAmelCase__       						=		level[u] + 1
																								q.put(UpperCAmelCase__      )
																								UpperCAmelCase__       						=		u
						return level, parent


def 	a__   (		)->						None:
						UpperCAmelCase__       						=		1_3
						# initializing with 0
						UpperCAmelCase__       						=		[[0 for _ in range(max_node + 1_0      )] for _ in range(2_0      )]
						# initializing with -1 which means every node is unvisited
						UpperCAmelCase__       						=		[-1 for _ in range(max_node + 1_0      )]
						UpperCAmelCase__       						=		{
						    1: [2, 3, 4],
						    2: [5],
						    3: [6, 7],
						    4: [8],
						    5: [9, 1_0],
						    6: [1_1],
						    7: [],
						    8: [1_2, 1_3],
						    9: [],
						    1_0: [],
						    1_1: [],
						    1_2: [],
						    1_3: [],
						}
						UpperCAmelCase__						,   UpperCAmelCase__       						=		breadth_first_search(UpperCAmelCase__		,      UpperCAmelCase__		,      UpperCAmelCase__		,      UpperCAmelCase__		,      1      )
						UpperCAmelCase__       						=		create_sparse(UpperCAmelCase__		,      UpperCAmelCase__      )
						print("""LCA of node 1 and 3 is: """		,      lowest_common_ancestor(1		,      3		,      UpperCAmelCase__		,      UpperCAmelCase__      )      )
						print("""LCA of node 5 and 6 is: """		,      lowest_common_ancestor(5		,      6		,      UpperCAmelCase__		,      UpperCAmelCase__      )      )
						print("""LCA of node 7 and 11 is: """		,      lowest_common_ancestor(7		,      1_1		,      UpperCAmelCase__		,      UpperCAmelCase__      )      )
						print("""LCA of node 6 and 7 is: """		,      lowest_common_ancestor(6		,      7		,      UpperCAmelCase__		,      UpperCAmelCase__      )      )
						print("""LCA of node 4 and 12 is: """		,      lowest_common_ancestor(4		,      1_2		,      UpperCAmelCase__		,      UpperCAmelCase__      )      )
						print("""LCA of node 8 and 8 is: """		,      lowest_common_ancestor(8		,      8		,      UpperCAmelCase__		,      UpperCAmelCase__      )      )


if __name__ == "__main__":
						main()


"""simple docstring"""







def 	a__   (		UpperCAmelCase__							:      list[int]      )->						int:
						UpperCAmelCase__       						=		len(UpperCAmelCase__      )
						if n in (0, 1):
												return 0
						return sum(query * (n - i - 1) for i, query in enumerate(sorted(UpperCAmelCase__      )      )      )


if __name__ == "__main__":
						import doctest

						doctest.testmod()

