





import os
import string
import sys


UpperCamelCase__     =	1 << 8

UpperCamelCase__     =	{
    "tab": ord("\t"),
    "newline": ord("\r"),
    "esc": 27,
    "up": 65 + ARROW_KEY_FLAG,
    "down": 66 + ARROW_KEY_FLAG,
    "right": 67 + ARROW_KEY_FLAG,
    "left": 68 + ARROW_KEY_FLAG,
    "mod_int": 91,
    "undefined": sys.maxsize,
    "interrupt": 3,
    "insert": 50,
    "delete": 51,
    "pg_up": 53,
    "pg_down": 54,
}

UpperCamelCase__     =	KEYMAP["up"]
UpperCamelCase__     =	KEYMAP["left"]

if sys.platform == "win32":
					UpperCamelCase__     =	[]
					UpperCamelCase__     =	{
					    B"\xe0H": KEYMAP["up"] - ARROW_KEY_FLAG,
					    B"\x00H": KEYMAP["up"] - ARROW_KEY_FLAG,
					    B"\xe0P": KEYMAP["down"] - ARROW_KEY_FLAG,
					    B"\x00P": KEYMAP["down"] - ARROW_KEY_FLAG,
					    B"\xe0M": KEYMAP["right"] - ARROW_KEY_FLAG,
					    B"\x00M": KEYMAP["right"] - ARROW_KEY_FLAG,
					    B"\xe0K": KEYMAP["left"] - ARROW_KEY_FLAG,
					    B"\x00K": KEYMAP["left"] - ARROW_KEY_FLAG,
					}

for i in range(10):
					UpperCamelCase__     =	ord(str(i))





def       _UpperCamelCase       ():






							"""simple docstring"""





							if os.name == "nt":
														import msvcrt

														UpperCamelCase__			       =     """mbcs"""
														# Flush the keyboard buffer
														while msvcrt.kbhit():
																					msvcrt.getch()
														if len(SCREAMING_SNAKE_CASE__    ) == 0:
																					# Read the keystroke
																					UpperCamelCase__			       =     msvcrt.getch()

																					# If it is a prefix char, get second part
																					if ch in (b"\x00", b"\xe0"):
																												UpperCamelCase__			       =     ch + msvcrt.getch()
																												# Translate actual Win chars to bullet char types
																												try:
																																			UpperCamelCase__			       =     chr(WIN_KEYMAP[cha]    )
																																			WIN_CH_BUFFER.append(chr(KEYMAP["""mod_int"""]    )    )
																																			WIN_CH_BUFFER.append(SCREAMING_SNAKE_CASE__    )
																																			if ord(SCREAMING_SNAKE_CASE__    ) in (
																																			    KEYMAP["insert"] - 1 << 9,
																																			    KEYMAP["delete"] - 1 << 9,
																																			    KEYMAP["pg_up"] - 1 << 9,
																																			    KEYMAP["pg_down"] - 1 << 9,
																																			):
																																										WIN_CH_BUFFER.append(chr(126    )    )
																																			UpperCamelCase__			       =     chr(KEYMAP["""esc"""]    )
																												except KeyError:
																																			UpperCamelCase__			       =     cha[1]
																					else:
																												UpperCamelCase__			       =     ch.decode(SCREAMING_SNAKE_CASE__    )
														else:
																					UpperCamelCase__			       =     WIN_CH_BUFFER.pop(0    )
							elif os.name == "posix":
														import termios
														import tty

														UpperCamelCase__			       =     sys.stdin.fileno()
														UpperCamelCase__			       =     termios.tcgetattr(SCREAMING_SNAKE_CASE__    )
														try:
																					tty.setraw(SCREAMING_SNAKE_CASE__    )
																					UpperCamelCase__			       =     sys.stdin.read(1    )
														finally:
																					termios.tcsetattr(SCREAMING_SNAKE_CASE__				,     termios.TCSADRAIN				,     SCREAMING_SNAKE_CASE__    )
							return ch





def       _UpperCamelCase       ():






							"""simple docstring"""





							UpperCamelCase__			       =     get_raw_chars()
							if ord(SCREAMING_SNAKE_CASE__    ) in [KEYMAP["interrupt"], KEYMAP["newline"]]:
														return char

							elif ord(SCREAMING_SNAKE_CASE__    ) == KEYMAP["esc"]:
														UpperCamelCase__			       =     get_raw_chars()
														if ord(SCREAMING_SNAKE_CASE__    ) == KEYMAP["mod_int"]:
																					UpperCamelCase__			       =     get_raw_chars()
																					if ord(SCREAMING_SNAKE_CASE__    ) >= KEYMAP["arrow_begin"] - ARROW_KEY_FLAG and ord(SCREAMING_SNAKE_CASE__    ) <= KEYMAP["arrow_end"] - ARROW_KEY_FLAG:
																												return chr(ord(SCREAMING_SNAKE_CASE__    ) + ARROW_KEY_FLAG    )
																					else:
																												return KEYMAP["undefined"]
														else:
																					return get_raw_chars()

							else:
														if char in string.printable:
																					return char
														else:
																					return KEYMAP["undefined"]









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()




