



from __future__ import annotations

from random import random
from typing import Generic, TypeVar

__snake_case		:Any   	=  TypeVar('''KT''')
__snake_case		:List[str]   	=  TypeVar('''VT''')

class 					_A (			Generic[KT, VT]					):



       def __init__(	self							:  Dict  ,	__SCREAMING_SNAKE_CASE							:  KT | str = "root"  ,	__SCREAMING_SNAKE_CASE							:  VT | None = None):


           '''simple docstring'''

           __a		 =       key
           __a		 =       value
           __a		 =       []



       def __repr__(	self							:  Dict):


           '''simple docstring'''

           return F'Node({self.key}: {self.value})'





       @property
       def 	_lowerCamelCase    (	self							:  Tuple):


           '''simple docstring'''

           return len(self.forward)


class 					_A (			Generic[KT, VT]					):



       def __init__(	self							:  Union[str, Any]  ,	__SCREAMING_SNAKE_CASE							:  float = 0.5  ,	__SCREAMING_SNAKE_CASE							:  int = 16):


           '''simple docstring'''

           __a		 =       Node[KT, VT]()
           __a		 =       0
           __a		 =       p
           __a		 =       max_level



       def __str__(	self							:  Union[str, Any]):


           '''simple docstring'''

           __a		 =       list(self)

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

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

           __a		 =       self.head
           __a		 =       []

           __a		 =       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:
               __a		 =       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))
               __a		 =       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							:  int):


           '''simple docstring'''

           __a		 =       self.head

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



       def 	_lowerCamelCase    (	self							:  List[Any]):


           '''simple docstring'''

           __a		 =       1
           while random() < self.p and level < self.max_level:
               level += 1

           return level



       def 	_lowerCamelCase    (	self							:  Tuple  ,	__SCREAMING_SNAKE_CASE							:  Union[str, Any]):


           '''simple docstring'''

           __a		 =       []

           __a		 =       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:
                   __a		 =       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 	_lowerCamelCase    (	self							:  Dict  ,	__SCREAMING_SNAKE_CASE							:  KT):


           '''simple docstring'''

           __a ,     __a		 =       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:
                           __a		 =       node.forward[i]
                       else:
                           __a		 =       update_node.forward[:i]



       def 	_lowerCamelCase    (	self							:  List[str]  ,	__SCREAMING_SNAKE_CASE							:  KT  ,	__SCREAMING_SNAKE_CASE							:  VT):


           '''simple docstring'''

           __a ,     __a		 =       self._locate_node(__SCREAMING_SNAKE_CASE)
           if node is not None:
               __a		 =       value
           else:
               __a		 =       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)
                   __a		 =       level

               __a		 =       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:
                       __a		 =       new_node





       def 	_lowerCamelCase    (	self							:  Union[str, Any]  ,	__SCREAMING_SNAKE_CASE							:  VT):


           '''simple docstring'''

           __a ,     __a		 =       self._locate_node(__SCREAMING_SNAKE_CASE)

           if node is not None:
               return node.value

           return None







def   __snake_case			(    ):
    __a		 =       SkipList()
    skip_list.insert('''Key1'''     ,				3       )
    skip_list.insert('''Key2'''     ,				12       )
    skip_list.insert('''Key3'''     ,				41       )
    skip_list.insert('''Key4'''     ,				-19       )

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

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







def   __snake_case			(    ):
    __a		 =       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       )

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

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







def   __snake_case			(    ):
    __a		 =       SkipList()
    assert skip_list.find('''Some key'''       ) is None







def   __snake_case			(    ):
    __a		 =       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   __snake_case			(    ):
    __a		 =       SkipList()
    skip_list.delete('''Some key'''       )

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







def   __snake_case			(    ):
    __a		 =       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   __snake_case			(    ):
    __a		 =       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   __snake_case			(    ):
    __a		 =       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(_UpperCAmelCase       ):
        yield node.key
        for forward_node in node.forward:
            yield from traverse_keys(_UpperCAmelCase       )

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







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

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







def   __snake_case			(    ):
    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   __snake_case			(    ):
    __a		 =       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(_UpperCAmelCase       )


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 main()










from __future__ import annotations

__snake_case		:Optional[Any]   	=  []





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





def   __snake_case			(    _UpperCAmelCase     ,				_UpperCAmelCase       ):
    if row >= len(_UpperCAmelCase       ):
        solution.append(_UpperCAmelCase       )
        printboard(_UpperCAmelCase       )
        print()
        return True
    for i in range(len(_UpperCAmelCase       )       ):
        if is_safe(_UpperCAmelCase     ,				_UpperCAmelCase     ,				_UpperCAmelCase       ):
            __a		 =       1
            solve(_UpperCAmelCase     ,				row + 1       )
            __a		 =       0
    return False





def   __snake_case			(    _UpperCAmelCase       ):
    for i in range(len(_UpperCAmelCase       )       ):
        for j in range(len(_UpperCAmelCase       )       ):
            if board[i][j] == 1:
                print('''Q'''     ,				end=''' '''       )
            else:
                print('''.'''     ,				end=''' '''       )
        print()


# n=int(input("The no. of queens"))
__snake_case		:Optional[Any]   	=  8
__snake_case		:Tuple   	=  [[0 for i in range(n)] for j in range(n)]
solve(board, 0)
print('''The total no. of solutions are :''', len(solution))





