






from __future__ import annotations

from random import random
from typing import Generic, TypeVar

__A					=	TypeVar("KT")
__A					=	TypeVar("VT")



class 				_A			(     Generic[KT, VT]				):
    """simple docstring"""

    def __init__(				self      :     int ,     __SCREAMING_SNAKE_CASE      :     KT | str = "root" ,     __SCREAMING_SNAKE_CASE      :     VT | None = None      )      ->							List[Any]:
           __UpperCAmelCase     				=key
           __UpperCAmelCase     				=value
           __UpperCAmelCase     				=[]



    def __repr__(				self      :     str      )      ->							str:
           return f'''Node({self.key}: {self.value})'''



    @property
    def _a							(				self      :     str      )      ->							int:
           return len(self.forward      )




class 				_A			(     Generic[KT, VT]				):
    """simple docstring"""

    def __init__(				self      :     Optional[int] ,     __SCREAMING_SNAKE_CASE      :     float = 0.5 ,     __SCREAMING_SNAKE_CASE      :     int = 16      )      ->							Optional[int]:
           __UpperCAmelCase     				=Node[KT, VT]()
           __UpperCAmelCase     				=0
           __UpperCAmelCase     				=p
           __UpperCAmelCase     				=max_level



    def __str__(				self      :     Optional[int]      )      ->							str:
           __UpperCAmelCase     				=list(self      )

           if len(__SCREAMING_SNAKE_CASE      ) == 0:
                  return f'''SkipList(level={self.level})'''

           __UpperCAmelCase     				=max((len(str(__SCREAMING_SNAKE_CASE      )      ) for item in items) ,     default=4      )
           __UpperCAmelCase     				=max(__SCREAMING_SNAKE_CASE ,     4      ) + 4

           __UpperCAmelCase     				=self.head
           __UpperCAmelCase     				=[]

           __UpperCAmelCase     				=node.forward.copy()
           lines.append(f'''[{node.key}]'''.ljust(__SCREAMING_SNAKE_CASE ,     """-"""      ) + """* """ * len(__SCREAMING_SNAKE_CASE      )      )
           lines.append(""" """ * label_size + """| """ * len(__SCREAMING_SNAKE_CASE      )      )

           while len(node.forward      ) != 0:
                  __UpperCAmelCase     				=node.forward[0]

                  lines.append(
                      f'''[{node.key}]'''.ljust(__SCREAMING_SNAKE_CASE ,     """-"""      )
                      + """ """.join(str(n.key      ) if n.key == node.key else """|""" for n in forwards      )      )
                  lines.append(""" """ * label_size + """| """ * len(__SCREAMING_SNAKE_CASE      )      )
                  __UpperCAmelCase     				=node.forward

           lines.append("""None""".ljust(__SCREAMING_SNAKE_CASE      ) + """* """ * len(__SCREAMING_SNAKE_CASE      )      )
           return f'''SkipList(level={self.level})\n''' + "\n".join(__SCREAMING_SNAKE_CASE      )



    def __iter__(				self      :     Tuple      )      ->							Optional[int]:
           __UpperCAmelCase     				=self.head

           while len(node.forward      ) != 0:
                  yield node.forward[0].key
                  __UpperCAmelCase     				=node.forward[0]



    def _a							(				self      :     Dict      )      ->							int:
           __UpperCAmelCase     				=1
           while random() < self.p and level < self.max_level:
                  level += 1

           return level



    def _a							(				self      :     int ,     __SCREAMING_SNAKE_CASE      :     List[str]      )      ->							tuple[Node[KT, VT] | None, list[Node[KT, VT]]]:
           __UpperCAmelCase     				=[]

           __UpperCAmelCase     				=self.head

           for i in reversed(range(self.level      )      ):
                  # i < node.level - When node level is lesser than `i` decrement `i`.
                  # node.forward[i].key < key - Jumping to node with key value higher
                  #                             or equal to searched key would result
                  #                             in skipping searched key.
                  while i < node.level and node.forward[i].key < key:
                         __UpperCAmelCase     				=node.forward[i]
                  # Each leftmost node (relative to searched node) will potentially have to
                  # be updated.
                  update_vector.append(__SCREAMING_SNAKE_CASE      )

           update_vector.reverse()  # Note that we were inserting values in reverse order.

           # len(node.forward) != 0 - If current node doesn't contain any further
           #                          references then searched key is not present.
           # node.forward[0].key == key - Next node key should be equal to search key
           #                              if key is present.
           if len(node.forward      ) != 0 and node.forward[0].key == key:
                  return node.forward[0], update_vector
           else:
                  return None, update_vector



    def _a							(				self      :     Any ,     __SCREAMING_SNAKE_CASE      :     KT      )      ->							Any:
           __UpperCAmelCase				, __UpperCAmelCase     				=self._locate_node(__SCREAMING_SNAKE_CASE      )

           if node is not None:
                  for i, update_node in enumerate(__SCREAMING_SNAKE_CASE      ):
                         # Remove or replace all references to removed node.
                         if update_node.level > i and update_node.forward[i].key == key:
                                if node.level > i:
                                       __UpperCAmelCase     				=node.forward[i]
                                else:
                                       __UpperCAmelCase     				=update_node.forward[:i]



    def _a							(				self      :     Dict ,     __SCREAMING_SNAKE_CASE      :     KT ,     __SCREAMING_SNAKE_CASE      :     VT      )      ->							Any:
           __UpperCAmelCase				, __UpperCAmelCase     				=self._locate_node(__SCREAMING_SNAKE_CASE      )
           if node is not None:
                  __UpperCAmelCase     				=value
           else:
                  __UpperCAmelCase     				=self.random_level()

                  if level > self.level:
                         # After level increase we have to add additional nodes to head.
                         for _ in range(self.level - 1 ,     __SCREAMING_SNAKE_CASE      ):
                                update_vector.append(self.head      )
                         __UpperCAmelCase     				=level

                  __UpperCAmelCase     				=Node(__SCREAMING_SNAKE_CASE ,     __SCREAMING_SNAKE_CASE      )

                  for i, update_node in enumerate(update_vector[:level]      ):
                         # Change references to pass through new node.
                         if update_node.level > i:
                                new_node.forward.append(update_node.forward[i]      )

                         if update_node.level < i + 1:
                                update_node.forward.append(__SCREAMING_SNAKE_CASE      )
                         else:
                                __UpperCAmelCase     				=new_node



    def _a							(				self      :     Optional[Any] ,     __SCREAMING_SNAKE_CASE      :     VT      )      ->							VT | None:
           __UpperCAmelCase				, __UpperCAmelCase     				=self._locate_node(__SCREAMING_SNAKE_CASE      )

           if node is not None:
                  return node.value

           return None







def       lowercase__	(					)	->				Any:







       """simple docstring"""






       __UpperCAmelCase     				=SkipList()
       skip_list.insert("""Key1"""  ,      3		)
       skip_list.insert("""Key2"""  ,      12		)
       skip_list.insert("""Key3"""  ,      41		)
       skip_list.insert("""Key4"""  ,      -19		)

       __UpperCAmelCase     				=skip_list.head
       __UpperCAmelCase     				={}
       while node.level != 0:
              __UpperCAmelCase     				=node.forward[0]
              __UpperCAmelCase     				=node.value

       assert len(A_		) == 4
       assert all_values["Key1"] == 3
       assert all_values["Key2"] == 12
       assert all_values["Key3"] == 41
       assert all_values["Key4"] == -19







def       lowercase__	(					)	->				Optional[Any]:







       """simple docstring"""






       __UpperCAmelCase     				=SkipList()
       skip_list.insert("""Key1"""  ,      10		)
       skip_list.insert("""Key1"""  ,      12		)

       skip_list.insert("""Key5"""  ,      7		)
       skip_list.insert("""Key7"""  ,      10		)
       skip_list.insert("""Key10"""  ,      5		)

       skip_list.insert("""Key7"""  ,      7		)
       skip_list.insert("""Key5"""  ,      5		)
       skip_list.insert("""Key10"""  ,      10		)

       __UpperCAmelCase     				=skip_list.head
       __UpperCAmelCase     				={}
       while node.level != 0:
              __UpperCAmelCase     				=node.forward[0]
              __UpperCAmelCase     				=node.value

       if len(A_		) != 4:
              print()
       assert len(A_		) == 4
       assert all_values["Key1"] == 12
       assert all_values["Key7"] == 7
       assert all_values["Key5"] == 5
       assert all_values["Key10"] == 10







def       lowercase__	(					)	->				Union[str, Any]:







       """simple docstring"""






       __UpperCAmelCase     				=SkipList()
       assert skip_list.find("""Some key"""		) is None







def       lowercase__	(					)	->				int:







       """simple docstring"""






       __UpperCAmelCase     				=SkipList()

       skip_list.insert("""Key2"""  ,      20		)
       assert skip_list.find("""Key2"""		) == 20

       skip_list.insert("""Some Key"""  ,      10		)
       skip_list.insert("""Key2"""  ,      8		)
       skip_list.insert("""V"""  ,      13		)

       assert skip_list.find("""Y"""		) is None
       assert skip_list.find("""Key2"""		) == 8
       assert skip_list.find("""Some Key"""		) == 10
       assert skip_list.find("""V"""		) == 13







def       lowercase__	(					)	->				Tuple:







       """simple docstring"""






       __UpperCAmelCase     				=SkipList()
       skip_list.delete("""Some key"""		)

       assert len(skip_list.head.forward		) == 0







def       lowercase__	(					)	->				Dict:







       """simple docstring"""






       __UpperCAmelCase     				=SkipList()

       skip_list.insert("""Key1"""  ,      12		)
       skip_list.insert("""V"""  ,      13		)
       skip_list.insert("""X"""  ,      14		)
       skip_list.insert("""Key2"""  ,      15		)

       skip_list.delete("""V"""		)
       skip_list.delete("""Key2"""		)

       assert skip_list.find("""V"""		) is None
       assert skip_list.find("""Key2"""		) is None







def       lowercase__	(					)	->				Any:







       """simple docstring"""






       __UpperCAmelCase     				=SkipList()

       skip_list.insert("""Key1"""  ,      12		)
       skip_list.insert("""V"""  ,      13		)
       skip_list.insert("""X"""  ,      14		)
       skip_list.insert("""Key2"""  ,      15		)

       skip_list.delete("""V"""		)
       assert skip_list.find("""V"""		) is None
       assert skip_list.find("""X"""		) == 14
       assert skip_list.find("""Key1"""		) == 12
       assert skip_list.find("""Key2"""		) == 15

       skip_list.delete("""X"""		)
       assert skip_list.find("""V"""		) is None
       assert skip_list.find("""X"""		) is None
       assert skip_list.find("""Key1"""		) == 12
       assert skip_list.find("""Key2"""		) == 15

       skip_list.delete("""Key1"""		)
       assert skip_list.find("""V"""		) is None
       assert skip_list.find("""X"""		) is None
       assert skip_list.find("""Key1"""		) is None
       assert skip_list.find("""Key2"""		) == 15

       skip_list.delete("""Key2"""		)
       assert skip_list.find("""V"""		) is None
       assert skip_list.find("""X"""		) is None
       assert skip_list.find("""Key1"""		) is None
       assert skip_list.find("""Key2"""		) is None







def       lowercase__	(					)	->				Dict:







       """simple docstring"""






       __UpperCAmelCase     				=SkipList()

       skip_list.insert("""Key1"""  ,      12		)
       skip_list.insert("""V"""  ,      13		)
       skip_list.insert("""X"""  ,      142		)
       skip_list.insert("""Key2"""  ,      15		)

       skip_list.delete("""X"""		)

       def traverse_keys(A_:						Dict		):
              yield node.key
              for forward_node in node.forward:
                     yield from traverse_keys(A_		)

       assert len(set(traverse_keys(skip_list.head		)		)		) == 4







def       lowercase__	(					)	->				Optional[Any]:







       """simple docstring"""






       def is_sorted(A_:						Any		):
              return all(next_item >= item for item, next_item in zip(A_  ,      lst[1:]		)		)

       __UpperCAmelCase     				=SkipList()
       for i in range(10		):
              skip_list.insert(A_  ,      A_		)
       assert is_sorted(list(A_		)		)
       skip_list.delete(5		)
       skip_list.delete(8		)
       skip_list.delete(2		)
       assert is_sorted(list(A_		)		)
       skip_list.insert(-12  ,      -12		)
       skip_list.insert(77  ,      77		)
       assert is_sorted(list(A_		)		)







def       lowercase__	(					)	->				Dict:







       """simple docstring"""






       for _ in range(100		):
              # Repeat test 100 times due to the probabilistic nature of skip list
              # random values == random bugs
              test_insert()
              test_insert_overrides_existing_value()

              test_searching_empty_list_returns_none()
              test_search()

              test_deleting_item_from_empty_list_do_nothing()
              test_deleted_items_are_not_founded_by_find_method()
              test_delete_removes_only_given_key()
              test_delete_doesnt_leave_dead_nodes()

              test_iter_always_yields_sorted_values()







def       lowercase__	(					)	->				Optional[int]:







       """simple docstring"""






       __UpperCAmelCase     				=SkipList()
       skip_list.insert(2  ,      """2"""		)
       skip_list.insert(4  ,      """4"""		)
       skip_list.insert(6  ,      """4"""		)
       skip_list.insert(4  ,      """5"""		)
       skip_list.insert(8  ,      """4"""		)
       skip_list.insert(9  ,      """4"""		)

       skip_list.delete(4		)

       print(A_		)


if __name__ == "__main__":
   import doctest

   doctest.testmod()
   main()







"""simple docstring"""

from __future__ import annotations

_UpperCamelCase		     =    []



def       SCREAMING_SNAKE_CASE							( lowercase__					,					lowercase__					,					lowercase__   )			->						bool:
 for i in range(len(lowercase__   )   ):
  if board[row][i] == 1:
   return False
 for i in range(len(lowercase__   )   ):
  if board[i][column] == 1:
   return False
 for i, j in zip(range(lowercase__					,					-1					,					-1   )					,					range(lowercase__					,					-1					,					-1   )   ):
  if board[i][j] == 1:
   return False
 for i, j in zip(range(lowercase__					,					-1					,					-1   )					,					range(lowercase__					,					len(lowercase__   )   )   ):
  if board[i][j] == 1:
   return False
 return True



def       SCREAMING_SNAKE_CASE							( lowercase__					,					lowercase__   )			->						bool:
 if row >= len(lowercase__   ):
  solution.append(lowercase__   )
  printboard(lowercase__   )
  print()
  return True
 for i in range(len(lowercase__   )   ):
  if is_safe(lowercase__					,					lowercase__					,					lowercase__   ):
   lowerCAmelCase__   :				List[Any] 			=				1
   solve(lowercase__					,					row + 1   )
   lowerCAmelCase__   :				Dict 			=				0
 return False



def       SCREAMING_SNAKE_CASE							( lowercase__   )			->						None:
 for i in range(len(lowercase__   )   ):
  for j in range(len(lowercase__   )   ):
   if board[i][j] == 1:
    print("Q"					,					end=" "   )
   else:
    print("."					,					end=" "   )
  print()


# n=int(input("The no. of queens"))
_UpperCamelCase		     =    8
_UpperCamelCase		     =    [[0 for i in range(n)] for j in range(n)]
solve(board, 0)






print("""The total no. of solutions are :""", len(solution))






