"""simple docstring"""







class      _lowercase						:

				def __init__(       self    :      str       ):


										'''simple docstring'''
										# numbermap keys are the number and its values are lists of indexes sorted
										# in ascending order
										UpperCAmelCase__   		=						{}
										# indexmap keys are an index and it's values are the number at that index
										UpperCAmelCase__   		=						{}

				def     A	(       self    :      List[str]    ,      _lowercase    :      Optional[Any]    ,      _lowercase    :      Union[str, Any]       ):


										'''simple docstring'''
										if isinstance(_A    ,      (range, str)       ):
																UpperCAmelCase__   		=						list(_A       )
										elif not isinstance(_A    ,      _A       ):
																raise TypeError(
																    """binary_search_delete() only accepts either a list, range or str"""       )

										UpperCAmelCase__   		=						0
										UpperCAmelCase__   		=						len(_A       ) - 1

										while low <= high:
																UpperCAmelCase__   		=						(low + high) // 2
																if array[mid] == item:
																						array.pop(_A       )
																						return array
																elif array[mid] < item:
																						UpperCAmelCase__   		=						mid + 1
																else:
																						UpperCAmelCase__   		=						mid - 1
										raise ValueError(
										    """Either the item is not in the array or the array was unsorted"""       )

				def     A	(       self    :      Optional[int]    ,      _lowercase    :      Any    ,      _lowercase    :      Tuple       ):


										'''simple docstring'''
										if isinstance(_A    ,      (range, str)       ):
																UpperCAmelCase__   		=						list(_A       )
										elif not isinstance(_A    ,      _A       ):
																raise TypeError(
																    """binary_search_insert() only accepts either a list, range or str"""       )

										UpperCAmelCase__   		=						0
										UpperCAmelCase__   		=						len(_A       ) - 1

										while low <= high:
																UpperCAmelCase__   		=						(low + high) // 2
																if array[mid] == index:
																						# If the item already exists in the array,
																						# insert it after the existing item
																						array.insert(mid + 1    ,      _A       )
																						return array
																elif array[mid] < index:
																						UpperCAmelCase__   		=						mid + 1
																else:
																						UpperCAmelCase__   		=						mid - 1

        # If the item doesn't exist in the array, insert it at the appropriate position
										array.insert(_A    ,      _A       )
										return array

				def     A	(       self    :      str    ,      _lowercase    :      Dict    ,      _lowercase    :      Tuple       ):


										'''simple docstring'''
										# Remove previous index
										if index in self.indexmap:
																UpperCAmelCase__   		=						self.indexmap[index]
																if len(self.numbermap[n]       ) == 1:
																						del self.numbermap[n]
																else:
																						UpperCAmelCase__   		=						self.binary_search_delete(self.numbermap[n]    ,      _A       )

        # Set new index
										UpperCAmelCase__   		=						number

										# Number not seen before or empty so insert number value
										if number not in self.numbermap:
																UpperCAmelCase__   		=						[index]

										# Here we need to perform a binary search insertion in order to insert
										# The item in the correct place
										else:
																UpperCAmelCase__   		=						self.binary_search_insert(
																    self.numbermap[number]    ,      _A       )

				def     A	(       self    :      List[str]    ,      _lowercase    :      List[Any]       ):


										'''simple docstring'''
										return self.numbermap.get(_A    ,      [-1]       )[0]


if __name__ == "__main__":
						import doctest

						doctest.testmod()


"""simple docstring"""







from __future__ import annotations


def 					a__ (						UpperCAmelCase__    :     int     )->		list[int]:
						assert (
						    isinstance(UpperCAmelCase__						,     UpperCAmelCase__     ) and mask > 0
						), f'mask needs to be positive integer, your input {mask}'
						UpperCAmelCase__   		=						[]
						UpperCAmelCase__   		=						mask

						while submask:
												all_submasks.append(UpperCAmelCase__     )
												UpperCAmelCase__   		=						(submask - 1) & mask

						return all_submasks


if __name__ == "__main__":
						import doctest

						doctest.testmod()

