





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





def       _UpperCamelCase       (a__				:Union[str, Any]				,     a__				:Optional[int]				,     a__				:Tuple				,     a__				:str    ):






							"""simple docstring"""





							UpperCamelCase__			       =     multiprocessing.Manager()
							UpperCamelCase__			       =     manager.list()

							UpperCamelCase__			       =     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       _UpperCamelCase       (a__				:int				,     a__				:Optional[Any]				,     a__				:int    ):






							"""simple docstring"""





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

														UpperCamelCase__			       =     shutil.rmtree
														UpperCamelCase__			       =     os.rmdir
														UpperCamelCase__			       =     os.chdir

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

														# Run program.
														try:
																					UpperCamelCase__			       =     {}
																					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.
														UpperCamelCase__			       =     rmtree
														UpperCamelCase__			       =     rmdir
														UpperCamelCase__			       =     chdir





@contextlib.contextmanager
def       _UpperCamelCase       (a__				:Dict    ):






							"""simple docstring"""





							def signal_handler(a__				:Optional[Any]				,     a__				:int    ):
														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       _UpperCamelCase       ():






							"""simple docstring"""





							UpperCamelCase__			       =     WriteOnlyStringIO()
							with contextlib.redirect_stdout(snake_case_    ):
														with contextlib.redirect_stderr(snake_case_    ):
																					with redirect_stdin(snake_case_    ):
																												yield





@contextlib.contextmanager
def       _UpperCamelCase       ():






							"""simple docstring"""





							with tempfile.TemporaryDirectory() as dirname:
														with chdir(snake_case_    ):
																					yield dirname

class     __SCREAMING_SNAKE_CASE   (       UpperCamelCase__    ):
							pass






class     __SCREAMING_SNAKE_CASE   (       io.StringIO    ):






							def 			_lowerCamelCase						(  self					,	*__lowerCAmelCase					,	**__lowerCAmelCase					):
														raise OSError






							def 			_lowerCamelCase						(  self					,	*__lowerCAmelCase					,	**__lowerCAmelCase					):
														raise OSError






							def 			_lowerCamelCase						(  self					,	*__lowerCAmelCase					,	**__lowerCAmelCase					):
														raise OSError







							def 			_lowerCamelCase						(  self					,	*__lowerCAmelCase					,	**__lowerCAmelCase					):
														return False






class     __SCREAMING_SNAKE_CASE   (       contextlib._RedirectStream    ):  # type: ignore
							snake_case       : Union[str, Any]         =    """stdin"""






@contextlib.contextmanager
def       _UpperCamelCase       (a__				:str    ):






							"""simple docstring"""





							if root == ".":
														yield
														return
							UpperCamelCase__			       =     os.getcwd()
							os.chdir(snake_case_    )
							try:
														yield
							except BaseException as exc:
														raise exc
							finally:
														os.chdir(snake_case_    )





def       _UpperCamelCase       (a__				:Any=None    ):






							"""simple docstring"""





							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

							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None

							import os

							UpperCamelCase__			       =     """1"""

							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None

							import shutil

							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None

							import subprocess

							UpperCamelCase__			       =     None  # type: ignore

							UpperCamelCase__			       =     None

							import sys

							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None
							UpperCamelCase__			       =     None









def       _UpperCamelCase       (a__				:str    ):






							"""simple docstring"""





							UpperCamelCase__			       =     0

							# if input_string is "aba" than new_input_string become "a|b|a"
							UpperCamelCase__			       =     """"""
							UpperCamelCase__			       =     """"""

							# append each character + "|" in new_string for range(0, length-1)
							for i in input_string[: len(a__    ) - 1]:
														new_input_string += i + "|"
							# append last character
							new_input_string += input_string[-1]

							# we will store the starting and ending of previous furthest ending palindromic
							# substring
							UpperCamelCase__       ,       UpperCamelCase__			       =     0, 0

							# length[i] shows the length of palindromic substring with center i
							UpperCamelCase__			       =     [1 for i in range(len(a__    )    )]

							# for each character in new_string find corresponding palindromic string
							UpperCamelCase__			       =     0
							for j in range(len(a__    )    ):
														UpperCamelCase__			       =     1 if j > r else min(length[l + r - j] // 2				,     r - j + 1    )
														while (
														    j - k >= 0
														    and j + k < len(a__    )
														    and new_input_string[k + j] == new_input_string[j - k]
														):
																					k += 1

														UpperCamelCase__			       =     2 * k - 1

														# does this string is ending after the previously explored end (that is r) ?
														# if yes the update the new r to the last index of this
														if j + k - 1 > r:
																					UpperCamelCase__			       =     j - k + 1  # noqa: E741
																					UpperCamelCase__			       =     j + k - 1

														# update max_length and start position
														if max_length < length[j]:
																					UpperCamelCase__			       =     length[j]
																					UpperCamelCase__			       =     j

    # create that string
							UpperCamelCase__			       =     new_input_string[start - max_length // 2 : start + max_length // 2 + 1]
							for i in s:
														if i != "|":
																					output_string += i

							return output_string


if __name__ == "__main__":
					import doctest

					doctest.testmod()




