






def 	SCREAMING_SNAKE_CASE							(      __lowerCAmelCase      ,					__lowerCAmelCase      ,					__lowerCAmelCase      ,					__lowerCAmelCase    )				->			int:
     return len_board * len_board_column * row + column







def 	SCREAMING_SNAKE_CASE							(      __lowerCAmelCase      ,					__lowerCAmelCase      ,					__lowerCAmelCase      ,					__lowerCAmelCase      ,					__lowerCAmelCase      ,					__lowerCAmelCase      ,					)				->			bool:

     if board[row][column] != word[word_index]:
          return False

     if word_index == len(__lowerCAmelCase    ) - 1:
          return True

     UpperCamelCase__    :     Any        =						[(0, 1), (0, -1), (-1, 0), (1, 0)]
     UpperCamelCase__    :     int        =						len(__lowerCAmelCase    )
     UpperCamelCase__    :     Any        =						len(board[0]    )
     for direction in traverts_directions:
          UpperCamelCase__    :     List[Any]        =						row + direction[0]
          UpperCamelCase__    :     Tuple        =						column + direction[1]
          if not (0 <= next_i < len_board and 0 <= next_j < len_board_column):
               continue

          UpperCamelCase__    :     Dict        =						get_point_key(__lowerCAmelCase      ,					__lowerCAmelCase      ,					__lowerCAmelCase      ,					__lowerCAmelCase    )
          if key in visited_points_set:
               continue

          visited_points_set.add(__lowerCAmelCase    )
          if exits_word(__lowerCAmelCase      ,					__lowerCAmelCase      ,					__lowerCAmelCase      ,					__lowerCAmelCase      ,					word_index + 1      ,					__lowerCAmelCase    ):
               return True

          visited_points_set.remove(__lowerCAmelCase    )

     return False







def 	SCREAMING_SNAKE_CASE							(      __lowerCAmelCase      ,					__lowerCAmelCase    )				->			bool:
     UpperCamelCase__    :     str        =						(
         "The board should be a non empty matrix of single chars strings."
     )

     UpperCamelCase__    :     List[Any]        =						len(__lowerCAmelCase    )
     if not isinstance(__lowerCAmelCase      ,					__lowerCAmelCase    ) or len(__lowerCAmelCase    ) == 0:
          raise ValueError(__lowerCAmelCase    )

     for row in board:
          if not isinstance(__lowerCAmelCase      ,					__lowerCAmelCase    ) or len(__lowerCAmelCase    ) == 0:
               raise ValueError(__lowerCAmelCase    )

          for item in row:
               if not isinstance(__lowerCAmelCase      ,					__lowerCAmelCase    ) or len(__lowerCAmelCase    ) != 1:
                    raise ValueError(__lowerCAmelCase    )

    # Validate word
     if not isinstance(__lowerCAmelCase      ,					__lowerCAmelCase    ) or len(__lowerCAmelCase    ) == 0:
          raise ValueError(
              "The word parameter should be a string of length greater than 0."    )

     UpperCamelCase__    :     List[str]        =						len(board[0]    )
     for i in range(__lowerCAmelCase    ):
          for j in range(__lowerCAmelCase    ):
               if exits_word(
                   __lowerCAmelCase      ,					__lowerCAmelCase      ,					__lowerCAmelCase      ,					__lowerCAmelCase      ,					0      ,					{get_point_key(__lowerCAmelCase      ,					__lowerCAmelCase      ,					__lowerCAmelCase      ,					__lowerCAmelCase    )}    ):
                    return True

     return False


if __name__ == "__main__":
 import doctest

 doctest.testmod()







from __future__ import annotations

from collections.abc import Iterator
from typing import Any





class     __a						:







 def __init__(	self      :     str							,     SCREAMING_SNAKE_CASE      :     Any		):


      '''simple docstring'''






      UpperCamelCase__    :     Any        =						data
      UpperCamelCase__    :     Node | None        =						None







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


      '''simple docstring'''






      return F'{self.data}'







class     __a						:







 def __init__(	self      :     Optional[int]		):


      '''simple docstring'''






      UpperCamelCase__    :     Node | None        =						None
      UpperCamelCase__    :     Node | None        =						None







 def __iter__(	self      :     str		):


      '''simple docstring'''






      UpperCamelCase__    :     int        =						self.front
      while node:
           yield node.data
           UpperCamelCase__    :     Any        =						node.next







 def __len__(	self      :     Tuple		):


      '''simple docstring'''






      return len(tuple(iter(self		)		)		)







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


      '''simple docstring'''






      return " <- ".join(str(SCREAMING_SNAKE_CASE		) for item in self		)







 def       __lowercase      (	self      :     List[str]		):


      '''simple docstring'''






      return len(self		) == 0







 def       __lowercase      (	self      :     Union[str, Any]							,     SCREAMING_SNAKE_CASE      :     Any		):


      '''simple docstring'''






      UpperCamelCase__    :     int        =						Node(SCREAMING_SNAKE_CASE		)
      if self.is_empty():
           UpperCamelCase__    :     int        =						node
      else:
           assert isinstance(self.rear							,     SCREAMING_SNAKE_CASE		)
           UpperCamelCase__    :     Dict        =						node
           UpperCamelCase__    :     str        =						node







 def       __lowercase      (	self      :     Dict		):


      '''simple docstring'''






      if self.is_empty():
           raise IndexError("dequeue from empty queue"		)
      assert isinstance(self.front							,     SCREAMING_SNAKE_CASE		)
      UpperCamelCase__    :     Optional[int]        =						self.front
      UpperCamelCase__    :     List[str]        =						self.front.next
      if self.front is None:
           UpperCamelCase__    :     List[Any]        =						None
      return node.data







 def       __lowercase      (	self      :     str		):


      '''simple docstring'''






      UpperCamelCase__    :     Optional[int]        =						None


if __name__ == "__main__":
 from doctest import testmod

 testmod()