"""simple docstring"""



import contextlib
import faulthandler
import io
import multiprocessing
import os
import platform
import signal
import tempfile





def    SCREAMING_SNAKE_CASE       (     snake_case,      snake_case,      snake_case,      snake_case):
     __snake_case				=							multiprocessing.Manager()
     __snake_case				=							manager.list()

     __snake_case				=							multiprocessing.Process(target=snake_case,      args=(check_program, result, timeout))
     p.start()
     p.join(timeout=timeout + 1)
     if p.is_alive():
          p.kill()

     if not result:
          result.append('''timed out''')

     return {
         "task_id": task_id,
         "passed": result[0] == "passed",
         "result": result[0],
         "completion_id": completion_id,
     }





def    SCREAMING_SNAKE_CASE       (     snake_case,      snake_case,      snake_case):
     with create_tempdir():
          # These system calls are needed when cleaning up tempdir.
          import os
          import shutil

          __snake_case				=							shutil.rmtree
          __snake_case				=							os.rmdir
          __snake_case				=							os.chdir

          # Disable functionalities that can make destructive changes to the test.
          reliability_guard()

          # Run program.
          try:
               __snake_case				=							{}
               with swallow_io():
                    with time_limit(snake_case):
                         exec(snake_case,      snake_case)
               result.append('''passed''')
          except TimeoutException:
               result.append('''timed out''')
          except BaseException as e:
               result.append(f"failed: {e}")

          # Needed for cleaning up.
          __snake_case				=							rmtree
          __snake_case				=							rmdir
          __snake_case				=							chdir





@contextlib.contextmanager
def    SCREAMING_SNAKE_CASE       (     snake_case):
     def signal_handler(snake_case,      snake_case):
          raise TimeoutException('''Timed out!''')

     signal.setitimer(signal.ITIMER_REAL,      snake_case)
     signal.signal(signal.SIGALRM,      snake_case)
     try:
          yield
     finally:
          signal.setitimer(signal.ITIMER_REAL,      0)





@contextlib.contextmanager
def    SCREAMING_SNAKE_CASE       (     ):
     __snake_case				=							WriteOnlyStringIO()
     with contextlib.redirect_stdout(snake_case):
          with contextlib.redirect_stderr(snake_case):
               with redirect_stdin(snake_case):
                    yield





@contextlib.contextmanager
def    SCREAMING_SNAKE_CASE       (     ):
     with tempfile.TemporaryDirectory() as dirname:
          with chdir(snake_case):
               yield dirname





class      _A	(						_UpperCAmelCase					):




    """simple docstring"""




    pass






class      _A	(						io.StringIO					):




    """simple docstring"""




    def  lowercase					(		self							:     int	,      *A_							:     List[Any]	,      **A_							:     Tuple    )    ->       str:
         raise OSError
    def  lowercase					(		self							:     Dict	,      *A_							:     Dict	,      **A_							:     Optional[Any]    )    ->       int:
         raise OSError
    def  lowercase					(		self							:     List[str]	,      *A_							:     str	,      **A_							:     Any    )    ->       List[Any]:
         raise OSError







    def  lowercase					(		self							:     Optional[Any]	,      *A_							:     List[str]	,      **A_							:     Optional[int]    )    ->       Tuple:
         return False






class      _A	(						contextlib._RedirectStream					):  # type: ignore




    """simple docstring"""




    UpperCamelCase_	:					Union[str, Any]							=					'''stdin'''






@contextlib.contextmanager
def    SCREAMING_SNAKE_CASE       (     snake_case):
     if root == ".":
          yield
          return
     __snake_case				=							os.getcwd()
     os.chdir(snake_case)
     try:
          yield
     except BaseException as exc:
          raise exc
     finally:
          os.chdir(snake_case)





def    SCREAMING_SNAKE_CASE       (     snake_case=None):

     if maximum_memory_bytes is not None:
          import resource

          resource.setrlimit(resource.RLIMIT_AS,      (maximum_memory_bytes, maximum_memory_bytes))
          resource.setrlimit(resource.RLIMIT_DATA,      (maximum_memory_bytes, maximum_memory_bytes))
          if not platform.uname().system == "Darwin":
               resource.setrlimit(resource.RLIMIT_STACK,      (maximum_memory_bytes, maximum_memory_bytes))

     faulthandler.disable()

     import builtins

     __snake_case				=							None
     __snake_case				=							None

     import os

     __snake_case				=							'''1'''

     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None

     import shutil

     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None

     import subprocess

     __snake_case				=							None  # type: ignore

     __snake_case				=							None

     import sys

     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
     __snake_case				=							None
"""simple docstring"""



from __future__ import annotations

from collections.abc import Iterator
from typing import Any



class      _A	:




    """simple docstring"""




    def __init__(		self							:     Tuple	,      A_							:     Any    )    ->       Union[str, Any]:
         __snake_case				=							data
         __snake_case				=							None






class      _A	:




    """simple docstring"""




    def __init__(		self							:     Union[str, Any]    )    ->       List[Any]:
         __snake_case				=							None
         __snake_case				=							None
    def __iter__(		self							:     Optional[Any]    )    ->       Iterator[Any]:
         __snake_case				=							self.head
         while self.head:
              yield node.data
              __snake_case				=							node.next
              if node == self.head:
                   break
    def __len__(		self							:     List[Any]    )    ->       int:
         return sum(1 for _ in self    )
    def __repr__(		self							:     Optional[int]    )    ->       Union[str, Any]:
         return "->".join(str(A_    ) for item in iter(self    )    )
    def  lowercase					(		self							:     int	,      A_							:     Any    )    ->       None:
         self.insert_nth(len(self    )	,      A_    )
    def  lowercase					(		self							:     List[str]	,      A_							:     Any    )    ->       None:
         self.insert_nth(0	,      A_    )
    def  lowercase					(		self							:     List[Any]	,      A_							:     int	,      A_							:     Any    )    ->       None:
         if index < 0 or index > len(self    ):
              raise IndexError('''list index out of range.'''    )
         __snake_case				=							Node(A_    )
         if self.head is None:
              __snake_case				=							new_node  # first node points itself
              __snake_case				=							__snake_case				=							new_node
         elif index == 0:  # insert at head
              __snake_case				=							self.head
              __snake_case				=							__snake_case				=							new_node
         else:
              __snake_case				=							self.head
              for _ in range(index - 1    ):
                   __snake_case				=							temp.next
              __snake_case				=							temp.next
              __snake_case				=							new_node
              if index == len(self    ) - 1:  # insert at tail
                   __snake_case				=							new_node
    def  lowercase					(		self							:     int    )    ->       str:
         return self.delete_nth(0    )
    def  lowercase					(		self							:     List[Any]    )    ->       Any:
         return self.delete_nth(len(self    ) - 1    )
    def  lowercase					(		self							:     List[str]	,      A_							:     int = 0    )    ->       Any:
         if not 0 <= index < len(self    ):
              raise IndexError('''list index out of range.'''    )
         __snake_case				=							self.head
         if self.head == self.tail:  # just one node
              __snake_case				=							__snake_case				=							None
         elif index == 0:  # delete head node
              __snake_case				=							self.tail.next.next
              __snake_case				=							self.head.next
         else:
              __snake_case				=							self.head
              for _ in range(index - 1    ):
                   __snake_case				=							temp.next
              __snake_case				=							temp.next
              __snake_case				=							temp.next.next
              if index == len(self    ) - 1:  # delete at tail
                   __snake_case				=							temp
         return delete_node.data







    def  lowercase					(		self							:     Dict    )    ->       bool:
         return len(self    ) == 0






def    SCREAMING_SNAKE_CASE       (     ):
     __snake_case				=							CircularLinkedList()
     assert len(snake_case) == 0
     assert circular_linked_list.is_empty() is True
     assert str(snake_case) == ""

     try:
          circular_linked_list.delete_front()
          raise AssertionError  # This should not happen
     except IndexError:
          assert True  # This should happen

     try:
          circular_linked_list.delete_tail()
          raise AssertionError  # This should not happen
     except IndexError:
          assert True  # This should happen

     try:
          circular_linked_list.delete_nth(-1)
          raise AssertionError
     except IndexError:
          assert True

     try:
          circular_linked_list.delete_nth(0)
          raise AssertionError
     except IndexError:
          assert True

     assert circular_linked_list.is_empty() is True
     for i in range(5):
          assert len(snake_case) == i
          circular_linked_list.insert_nth(snake_case,      i + 1)
     assert str(snake_case) == "->".join(str(snake_case) for i in range(1,      6))

     circular_linked_list.insert_tail(6)
     assert str(snake_case) == "->".join(str(snake_case) for i in range(1,      7))
     circular_linked_list.insert_head(0)
     assert str(snake_case) == "->".join(str(snake_case) for i in range(0,      7))

     assert circular_linked_list.delete_front() == 0
     assert circular_linked_list.delete_tail() == 6
     assert str(snake_case) == "->".join(str(snake_case) for i in range(1,      6))
     assert circular_linked_list.delete_nth(2) == 3

     circular_linked_list.insert_nth(2,      3)
     assert str(snake_case) == "->".join(str(snake_case) for i in range(1,      6))

     assert circular_linked_list.is_empty() is False


if __name__ == "__main__":
       import doctest

       doctest.testmod()