from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

_lowerCamelCase   :				int     			=						TypeVar('''T''')





def 		__lowerCamelCase							(UpperCAmelCase__       :							int					):
					return (position - 1) // 2





def 		__lowerCamelCase							(UpperCAmelCase__       :							int					):
					return (2 * position) + 1





def 		__lowerCamelCase							(UpperCAmelCase__       :							int					):
					return (2 * position) + 2


class   lowercase      (       Generic[T]       ):




							def __init__(  self				:   List[Any] )   ->			None:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    []
												SCREAMING_SNAKE_CASE           =    {}
												SCREAMING_SNAKE_CASE           =    0




							def __len__(  self				:   List[Any] )   ->			int:



												'''simple docstring'''

												return self.elements




							def __repr__(  self				:   Dict )   ->			str:



												'''simple docstring'''

												return str(self.heap )




							def 		__snake_case(  self				:   int )   ->			bool:



												'''simple docstring'''

												return self.elements == 0




							def 		__snake_case(  self				:   Tuple		,							_UpperCamelCase				:   T		,							_UpperCamelCase				:   int )   ->			None:



												'''simple docstring'''

												self.heap.append((elem, weight) )
												SCREAMING_SNAKE_CASE           =    self.elements
												self.elements += 1
												self._bubble_up(_UpperCamelCase )




							def 		__snake_case(  self				:   str )   ->			T:



												'''simple docstring'''

												if self.elements > 1:
																	self._swap_nodes(0		,							self.elements - 1 )
												SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    self.heap.pop()
												del self.position_map[elem]
												self.elements -= 1
												if self.elements > 0:
																	SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    self.heap[0]
																	self._bubble_down(_UpperCamelCase )
												return elem




							def 		__snake_case(  self				:   str		,							_UpperCamelCase				:   T		,							_UpperCamelCase				:   int )   ->			None:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    self.position_map[elem]
												SCREAMING_SNAKE_CASE           =    (elem, weight)
												if position > 0:
																	SCREAMING_SNAKE_CASE           =    get_parent_position(_UpperCamelCase )
																	SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    self.heap[parent_position]
																	if parent_weight > weight:
																						self._bubble_up(_UpperCamelCase )
																	else:
																						self._bubble_down(_UpperCamelCase )
												else:
																	self._bubble_down(_UpperCamelCase )




							def 		__snake_case(  self				:   Optional[int]		,							_UpperCamelCase				:   T )   ->			None:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    self.position_map[elem]
												if curr_pos == 0:
																	return None
												SCREAMING_SNAKE_CASE           =    get_parent_position(_UpperCamelCase )
												SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    self.heap[curr_pos]
												SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    self.heap[parent_position]
												if parent_weight > weight:
																	self._swap_nodes(_UpperCamelCase		,							_UpperCamelCase )
																	return self._bubble_up(_UpperCamelCase )
												return None




							def 		__snake_case(  self				:   Tuple		,							_UpperCamelCase				:   T )   ->			None:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    self.position_map[elem]
												SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    self.heap[curr_pos]
												SCREAMING_SNAKE_CASE           =    get_child_left_position(_UpperCamelCase )
												SCREAMING_SNAKE_CASE           =    get_child_right_position(_UpperCamelCase )
												if child_left_position < self.elements and child_right_position < self.elements:
																	SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    self.heap[child_left_position]
																	SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    self.heap[child_right_position]
																	if child_right_weight < child_left_weight and child_right_weight < weight:
																						self._swap_nodes(_UpperCamelCase		,							_UpperCamelCase )
																						return self._bubble_down(_UpperCamelCase )
												if child_left_position < self.elements:
																	SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    self.heap[child_left_position]
																	if child_left_weight < weight:
																						self._swap_nodes(_UpperCamelCase		,							_UpperCamelCase )
																						return self._bubble_down(_UpperCamelCase )
												else:
																	return None
												if child_right_position < self.elements:
																	SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    self.heap[child_right_position]
																	if child_right_weight < weight:
																						self._swap_nodes(_UpperCamelCase		,							_UpperCamelCase )
																						return self._bubble_down(_UpperCamelCase )
												return None





							def 		__snake_case(  self				:   Any		,							_UpperCamelCase				:   int		,							_UpperCamelCase				:   int )   ->			None:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    self.heap[nodea_pos][0]
												SCREAMING_SNAKE_CASE           =    self.heap[nodea_pos][0]
												SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    (
												    self.heap[nodea_pos],
												    self.heap[nodea_pos],
												)
												SCREAMING_SNAKE_CASE           =    nodea_pos
												SCREAMING_SNAKE_CASE           =    nodea_pos



class   lowercase      (       Generic[T]       ):




							def __init__(  self				:   Tuple )   ->			None:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    {}
												SCREAMING_SNAKE_CASE           =    0




							def __repr__(  self				:   Dict )   ->			str:



												'''simple docstring'''

												return str(self.connections )




							def __len__(  self				:   Union[str, Any] )   ->			int:



												'''simple docstring'''

												return self.nodes




							def 		__snake_case(  self				:   Tuple		,							_UpperCamelCase				:   T )   ->			None:



												'''simple docstring'''

												if node not in self.connections:
																	SCREAMING_SNAKE_CASE           =    {}
																	self.nodes += 1





							def 		__snake_case(  self				:   str		,							_UpperCamelCase				:   T		,							_UpperCamelCase				:   T		,							_UpperCamelCase				:   int )   ->			None:



												'''simple docstring'''

												self.add_node(_UpperCamelCase )
												self.add_node(_UpperCamelCase )
												SCREAMING_SNAKE_CASE           =    weight
												SCREAMING_SNAKE_CASE           =    weight





def 		__lowerCamelCase							(UpperCAmelCase__       :							GraphUndirectedWeighted[T] ,	):
					SCREAMING_SNAKE_CASE           =    {node: maxsize for node in graph.connections}
					SCREAMING_SNAKE_CASE           =    {node: None for node in graph.connections}

					SCREAMING_SNAKE_CASE           =    MinPriorityQueue()
					for node, weight in dist.items():
										priority_queue.push(UpperCAmelCase__ ,	UpperCAmelCase__					)

					if priority_queue.is_empty():
										return dist, parent

					# initialization
					SCREAMING_SNAKE_CASE           =    priority_queue.extract_min()
					SCREAMING_SNAKE_CASE           =    0
					for neighbour in graph.connections[node]:
										if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
															SCREAMING_SNAKE_CASE           =    dist[node] + graph.connections[node][neighbour]
															priority_queue.update_key(UpperCAmelCase__ ,	dist[neighbour]					)
															SCREAMING_SNAKE_CASE           =    node

    # running prim's algorithm
					while not priority_queue.is_empty():
										SCREAMING_SNAKE_CASE           =    priority_queue.extract_min()
										for neighbour in graph.connections[node]:
															if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
																				SCREAMING_SNAKE_CASE           =    dist[node] + graph.connections[node][neighbour]
																				priority_queue.update_key(UpperCAmelCase__ ,	dist[neighbour]					)
																				SCREAMING_SNAKE_CASE           =    node
					return dist, parent





from random import randint, random





def 		__lowerCamelCase							(UpperCAmelCase__       :							int ,	UpperCAmelCase__       :							int ,	UpperCAmelCase__       :							int ,	UpperCAmelCase__       :							bool = False ,	UpperCAmelCase__       :							bool = False ,	UpperCAmelCase__       :							int = 5 ,	):
					SCREAMING_SNAKE_CASE           =    [[-1] * number_of_cells]  # Create a highway without any car
					SCREAMING_SNAKE_CASE           =    0
					SCREAMING_SNAKE_CASE           =    max(UpperCAmelCase__ ,	0					)
					while i < number_of_cells:
										SCREAMING_SNAKE_CASE           =    (
										    randint(0 ,	UpperCAmelCase__					) if random_speed else initial_speed
										)  # Place the cars
										i += (
										    randint(1 ,	max_speed * 2					) if random_frequency else frequency
										)  # Arbitrary number, may need tuning
					return highway





def 		__lowerCamelCase							(UpperCAmelCase__       :							list ,	UpperCAmelCase__       :							int					):
					SCREAMING_SNAKE_CASE           =    0
					SCREAMING_SNAKE_CASE           =    highway_now[car_index + 1 :]
					for cell in range(len(UpperCAmelCase__					)					):  # May need a better name for this
										if cells[cell] != -1:  # If the cell is not empty then
															return distance  # we have the distance we wanted
										distance += 1
					# Here if the car is near the end of the highway
					return distance + get_distance(UpperCAmelCase__ ,	-1					)





def 		__lowerCamelCase							(UpperCAmelCase__       :							list ,	UpperCAmelCase__       :							float ,	UpperCAmelCase__       :							int					):
					SCREAMING_SNAKE_CASE           =    len(UpperCAmelCase__					)
					# Beforce calculations, the highway is empty
					SCREAMING_SNAKE_CASE           =    [-1] * number_of_cells

					for car_index in range(UpperCAmelCase__					):
										if highway_now[car_index] != -1:
															# Add 1 to the current speed of the car and cap the speed
															SCREAMING_SNAKE_CASE           =    min(highway_now[car_index] + 1 ,	UpperCAmelCase__					)
															# Number of empty cell before the next car
															SCREAMING_SNAKE_CASE           =    get_distance(UpperCAmelCase__ ,	UpperCAmelCase__					) - 1
															# We can't have the car causing an accident
															SCREAMING_SNAKE_CASE           =    min(next_highway[car_index] ,	UpperCAmelCase__					)
															if random() < probability:
																				# Randomly, a driver will slow down
																				SCREAMING_SNAKE_CASE           =    max(next_highway[car_index] - 1 ,	0					)
					return next_highway





def 		__lowerCamelCase							(UpperCAmelCase__       :							list ,	UpperCAmelCase__       :							int ,	UpperCAmelCase__       :							float ,	UpperCAmelCase__       :							int					):
					SCREAMING_SNAKE_CASE           =    len(highway[0]					)

					for i in range(UpperCAmelCase__					):
										SCREAMING_SNAKE_CASE           =    update(highway[i] ,	UpperCAmelCase__ ,	UpperCAmelCase__					)
										SCREAMING_SNAKE_CASE           =    [-1] * number_of_cells

										for car_index in range(UpperCAmelCase__					):
															SCREAMING_SNAKE_CASE           =    next_speeds_calculated[car_index]
															if speed != -1:
																				# Change the position based on the speed (with % to create the loop)
																				SCREAMING_SNAKE_CASE           =    (car_index + speed) % number_of_cells
																				# Commit the change of position
																				SCREAMING_SNAKE_CASE           =    speed
										highway.append(UpperCAmelCase__					)

					return highway


if __name__ == "__main__":
							import doctest

							doctest.testmod()




