





import numpy as np


def 					__SCREAMING_SNAKE_CASE  (							__lowercase:		Union[str, Any]     ,							__lowercase:		List[str]="utf-8"     ,							__lowercase:		Tuple="surrogatepass"):



  '''simple docstring'''






  __lowerCAmelCase			=				bin(int.from_bytes(text.encode(__lowercase     ,							__lowercase)     ,							'''big'''))[2:]
  return bits.zfill(8 * ((len(__lowercase) + 7) // 8))


def 					__SCREAMING_SNAKE_CASE  (							__lowercase:		Tuple     ,							__lowercase:		List[Any]="utf-8"     ,							__lowercase:		int="surrogatepass"):



  '''simple docstring'''






  __lowerCAmelCase			=				int(__lowercase     ,							2)
  return n.to_bytes((n.bit_length() + 7) // 8     ,							'''big''').decode(__lowercase     ,							__lowercase) or "\0"


def 					__SCREAMING_SNAKE_CASE  (							__lowercase:		List[Any]     ,							__lowercase:		List[str]):



  '''simple docstring'''






  if size_par + len(__lowercase) <= 2**size_par - (len(__lowercase) - 1):
    raise ValueError('''size of parity don\'t match with size of data''')

  __lowerCAmelCase			=				[]
  __lowerCAmelCase			=				[]
  __lowerCAmelCase			=				[bin(__lowercase)[2:] for x in range(1     ,							size_par + len(__lowercase) + 1)]

  # sorted information data for the size of the output data
  __lowerCAmelCase			=				[]
  # data position template + parity
  __lowerCAmelCase			=				[]
  # parity bit counter
  __lowerCAmelCase			=				0
  # counter position of data bits
  __lowerCAmelCase			=				0

  for x in range(1     ,							size_par + len(__lowercase) + 1):
    # Performs a template of bit positions - who should be given,
    # and who should be parity
    if qtd_bp < size_par:
      if (np.log(__lowercase) / np.log(2)).is_integer():
        data_out_gab.append('''P''')
        __lowerCAmelCase			=				qtd_bp + 1
      else:
        data_out_gab.append('''D''')
    else:
      data_out_gab.append('''D''')

    # Sorts the data to the new output size
    if data_out_gab[-1] == "D":
      data_ord.append(data[cont_data])
      cont_data += 1
    else:
      data_ord.append(__lowercase)

    # Calculates parity
  __lowerCAmelCase			=				0  # parity bit counter
  for bp in range(1     ,							size_par + 1):
    # Bit counter one for a given parity
    __lowerCAmelCase			=				0
    # counter to control the loop reading
    __lowerCAmelCase			=				0
    for x in data_ord:
      if x is not None:
        try:
          __lowerCAmelCase			=				(bin_pos[cont_loop])[-1 * (bp)]
        except IndexError:
          __lowerCAmelCase			=				'''0'''
        if aux == "1" and x == "1":
          cont_bo += 1
      cont_loop += 1
    parity.append(cont_bo % 2)

    qtd_bp += 1

  # Mount the message
  __lowerCAmelCase			=				0  # parity bit counter
  for x in range(0     ,							size_par + len(__lowercase)):
    if data_ord[x] is None:
      data_out.append(str(parity[cont_bp]))
      cont_bp += 1
    else:
      data_out.append(data_ord[x])

  return data_out


def 					__SCREAMING_SNAKE_CASE  (							__lowercase:		Union[str, Any]     ,							__lowercase:		List[Any]):



  '''simple docstring'''






  __lowerCAmelCase			=				[]
  # Parity bit counter
  __lowerCAmelCase			=				0
  # Counter p data bit reading
  __lowerCAmelCase			=				0
  # list of parity received
  __lowerCAmelCase			=				[]
  __lowerCAmelCase			=				[]

  for x in range(1     ,							len(__lowercase) + 1):
    # Performs a template of bit positions - who should be given,
    #  and who should be parity
    if qtd_bp < size_par and (np.log(__lowercase) / np.log(2)).is_integer():
      data_out_gab.append('''P''')
      __lowerCAmelCase			=				qtd_bp + 1
    else:
      data_out_gab.append('''D''')

    # Sorts the data to the new output size
    if data_out_gab[-1] == "D":
      data_output.append(data[cont_data])
    else:
      parity_received.append(data[cont_data])
    cont_data += 1

  # -----------calculates the parity with the data
  __lowerCAmelCase			=				[]
  __lowerCAmelCase			=				[]
  __lowerCAmelCase			=				[bin(__lowercase)[2:] for x in range(1     ,							size_par + len(__lowercase) + 1)]

  #  sorted information data for the size of the output data
  __lowerCAmelCase			=				[]
  # Data position feedback + parity
  __lowerCAmelCase			=				[]
  # Parity bit counter
  __lowerCAmelCase			=				0
  # Counter p data bit reading
  __lowerCAmelCase			=				0

  for x in range(1     ,							size_par + len(__lowercase) + 1):
    # Performs a template position of bits - who should be given,
    # and who should be parity
    if qtd_bp < size_par and (np.log(__lowercase) / np.log(2)).is_integer():
      data_out_gab.append('''P''')
      __lowerCAmelCase			=				qtd_bp + 1
    else:
      data_out_gab.append('''D''')

    # Sorts the data to the new output size
    if data_out_gab[-1] == "D":
      data_ord.append(data_output[cont_data])
      cont_data += 1
    else:
      data_ord.append(__lowercase)

    # Calculates parity
  __lowerCAmelCase			=				0  # parity bit counter
  for bp in range(1     ,							size_par + 1):
    # Bit counter one for a certain parity
    __lowerCAmelCase			=				0
    # Counter to control loop reading
    __lowerCAmelCase			=				0
    for x in data_ord:
      if x is not None:
        try:
          __lowerCAmelCase			=				(bin_pos[cont_loop])[-1 * (bp)]
        except IndexError:
          __lowerCAmelCase			=				'''0'''
        if aux == "1" and x == "1":
          cont_bo += 1
      cont_loop += 1
    parity.append(str(cont_bo % 2))

    qtd_bp += 1

  # Mount the message
  __lowerCAmelCase			=				0  # Parity bit counter
  for x in range(0     ,							size_par + len(__lowercase)):
    if data_ord[x] is None:
      data_out.append(str(parity[cont_bp]))
      cont_bp += 1
    else:
      data_out.append(data_ord[x])

  __lowerCAmelCase			=				parity_received == parity
  return data_output, ack







class   __snake_case				:






    '''simple docstring'''





    def __init__(   self						:		Any							):

      """simple docstring"""





      __lowerCAmelCase			=				{}
      # indexmap keys are an index and it's values are the number at that index
      __lowerCAmelCase			=				{}





    def 	A		(   self						:		List[Any]			,						snake_case						:		list | str | range			,						snake_case						:		int							):

      """simple docstring"""





      if isinstance(snake_case			,						(range, str)							):
        __lowerCAmelCase			=				list(snake_case							)
      elif not isinstance(snake_case			,						snake_case							):
        raise TypeError(
            '''binary_search_delete() only accepts either a list, range or str'''							)

      __lowerCAmelCase			=				0
      __lowerCAmelCase			=				len(snake_case							) - 1

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





    def 	A		(   self						:		Tuple			,						snake_case						:		list | str | range			,						snake_case						:		int							):

      """simple docstring"""





      if isinstance(snake_case			,						(range, str)							):
        __lowerCAmelCase			=				list(snake_case							)
      elif not isinstance(snake_case			,						snake_case							):
        raise TypeError(
            '''binary_search_insert() only accepts either a list, range or str'''							)

      __lowerCAmelCase			=				0
      __lowerCAmelCase			=				len(snake_case							) - 1

      while low <= high:
        __lowerCAmelCase			=				(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			,						snake_case							)
          return array
        elif array[mid] < index:
          __lowerCAmelCase			=				mid + 1
        else:
          __lowerCAmelCase			=				mid - 1

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





    def 	A		(   self						:		Tuple			,						snake_case						:		int			,						snake_case						:		int							):

      """simple docstring"""





      if index in self.indexmap:
        __lowerCAmelCase			=				self.indexmap[index]
        if len(self.numbermap[n]							) == 1:
          del self.numbermap[n]
        else:
          __lowerCAmelCase			=				self.binary_search_delete(self.numbermap[n]			,						snake_case							)

        # Set new index
      __lowerCAmelCase			=				number

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

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





    def 	A		(   self						:		List[str]			,						snake_case						:		int							):

      """simple docstring"""





      return self.numbermap.get(snake_case			,						[-1]							)[0]


if __name__ == "__main__":
      import doctest

      doctest.testmod()
