



"""simple docstring"""




def 						__snake_case						(				SCREAMING_SNAKE_CASE__     :						list[int]    )  ->       list[list[int]]:





     '''simple docstring'''

     _UpperCAmelCase      :     str        =   []
     if len(SCREAMING_SNAKE_CASE__    ) == 1:
          return [nums.copy()]
     for _ in range(len(SCREAMING_SNAKE_CASE__    )    ):
          _UpperCAmelCase      :     int        =   nums.pop(0    )
          _UpperCAmelCase      :     List[Any]        =   permute(SCREAMING_SNAKE_CASE__    )
          for perm in permutations:
               perm.append(SCREAMING_SNAKE_CASE__    )
          result.extend(SCREAMING_SNAKE_CASE__    )
          nums.append(SCREAMING_SNAKE_CASE__    )
     return result

def 						__snake_case						(				SCREAMING_SNAKE_CASE__     :						Optional[int]    )  ->       Dict:





     '''simple docstring'''

     def backtrack(SCREAMING_SNAKE_CASE__     :						List[Any]    ):
          if start == len(SCREAMING_SNAKE_CASE__    ) - 1:
               output.append(nums[:]    )
          else:
               for i in range(SCREAMING_SNAKE_CASE__						,  len(SCREAMING_SNAKE_CASE__    )    ):
                    _UpperCAmelCase    ,	_UpperCAmelCase      :     Optional[int]        =   nums[i], nums[start]
                    backtrack(start + 1    )
                    _UpperCAmelCase    ,	_UpperCAmelCase      :     int        =   nums[i], nums[start]  # backtrack

     _UpperCAmelCase      :     Tuple        =   []
     backtrack(0    )
     return output


if __name__ == "__main__":
 import doctest

 # use res to print the data in permute2 function
 _lowerCAmelCase    : int							=							permutea([1, 2, 3])
 print(res)
 doctest.testmod()





"""simple docstring"""




from collections.abc import Callable






class      UpperCAmelCase_  :



      def __init__(					self					:     Dict					,     A					:     Callable | None = None						):
           # Stores actual heap items.
           _UpperCAmelCase      :     list        =   []
           # Stores indexes of each item for supporting updates and deletion.
           _UpperCAmelCase      :     dict        =   {}
           # Stores current size of heap.
           _UpperCAmelCase      :     Tuple        =   0
           # Stores function used to evaluate the score of an item on which basis ordering
           # will be done.
           _UpperCAmelCase      :     Any        =   key or (lambda A						: x)



      def 						snake_case_ (					self					:     List[Any]					,     A					:     int						):
           return int((i - 1) / 2						) if i > 0 else None



      def 						snake_case_ (					self					:     List[Any]					,     A					:     int						):
           _UpperCAmelCase      :     Tuple        =   int(2 * i + 1						)
           return left if 0 < left < self.size else None



      def 						snake_case_ (					self					:     List[Any]					,     A					:     int						):
           _UpperCAmelCase      :     Tuple        =   int(2 * i + 2						)
           return right if 0 < right < self.size else None



      def 						snake_case_ (					self					:     Optional[int]					,     A					:     int					,     A					:     int						):
           _UpperCAmelCase    ,	_UpperCAmelCase      :     int        =   (
               self.pos_map[self.arr[j][0]],
               self.pos_map[self.arr[i][0]],
           )
           # Then swap the items in the list.
           _UpperCAmelCase    ,	_UpperCAmelCase      :     Any        =   self.arr[j], self.arr[i]



      def 						snake_case_ (					self					:     List[str]					,     A					:     int					,     A					:     int						):
           return self.arr[i][1] < self.arr[j][1]



      def 						snake_case_ (					self					:     Dict					,     A					:     int						):
           _UpperCAmelCase      :     str        =   self._left(A						)
           _UpperCAmelCase      :     str        =   self._right(A						)
           _UpperCAmelCase      :     List[Any]        =   i

           if left is not None and not self._cmp(A					,     A						):
                _UpperCAmelCase      :     Optional[int]        =   left
           if right is not None and not self._cmp(A					,     A						):
                _UpperCAmelCase      :     Any        =   right

           return valid_parent



      def 						snake_case_ (					self					:     Tuple					,     A					:     int						):
           _UpperCAmelCase      :     Tuple        =   self._parent(A						)
           while parent is not None and not self._cmp(A					,     A						):
                self._swap(A					,     A						)
                _UpperCAmelCase    ,	_UpperCAmelCase      :     Dict        =   parent, self._parent(A						)



      def 						snake_case_ (					self					:     Optional[int]					,     A					:     int						):
           _UpperCAmelCase      :     Tuple        =   self._get_valid_parent(A						)
           while valid_parent != index:
                self._swap(A					,     A						)
                _UpperCAmelCase    ,	_UpperCAmelCase      :     Optional[Any]        =   valid_parent, self._get_valid_parent(A						)



      def 						snake_case_ (					self					:     Dict					,     A					:     int					,     A					:     int						):
           if item not in self.pos_map:
                return
           _UpperCAmelCase      :     Any        =   self.pos_map[item]
           _UpperCAmelCase      :     Optional[int]        =   [item, self.key(A						)]
           # Make sure heap is right in both up and down direction.
           # Ideally only one of them will make any change.
           self._heapify_up(A						)
           self._heapify_down(A						)



      def 						snake_case_ (					self					:     List[str]					,     A					:     int						):
           if item not in self.pos_map:
                return
           _UpperCAmelCase      :     str        =   self.pos_map[item]
           del self.pos_map[item]
           _UpperCAmelCase      :     Tuple        =   self.arr[self.size - 1]
           _UpperCAmelCase      :     List[Any]        =   index
           self.size -= 1
           # Make sure heap is right in both up and down direction. Ideally only one
           # of them will make any change- so no performance loss in calling both.
           if self.size > index:
                self._heapify_up(A						)
                self._heapify_down(A						)



      def 						snake_case_ (					self					:     Any					,     A					:     int					,     A					:     int						):
           _UpperCAmelCase      :     Any        =   len(self.arr						)
           if arr_len == self.size:
                self.arr.append([item, self.key(A						)]						)
           else:
                _UpperCAmelCase      :     Any        =   [item, self.key(A						)]
           _UpperCAmelCase      :     List[Any]        =   self.size
           self.size += 1
           self._heapify_up(self.size - 1						)



      def 						snake_case_ (					self					:     Tuple						):
           return self.arr[0] if self.size else None



      def 						snake_case_ (					self					:     Any						):
           _UpperCAmelCase      :     Dict        =   self.get_top()
           if top_item_tuple:
                self.delete_item(top_item_tuple[0]						)
           return top_item_tuple







def 						__snake_case						(				)  ->       None:





     '''simple docstring'''



if __name__ == "__main__":
 import doctest

 doctest.testmod()
