




from __future__ import annotations







def 		_A(       UpperCamelCase__							:			list				,       UpperCamelCase__							:			int | None = None				,       UpperCamelCase__							:			int | None = None				)    -> None:
							'''simple docstring'''


							if start is None:
														__lowercase      =    0

							if end is None:
														__lowercase      =    len(UpperCamelCase__				) - 1

							if start >= end:
														return

							__lowercase      =    (start + end) // 2

							slowsort(UpperCamelCase__				,       UpperCamelCase__				,       UpperCamelCase__				)
							slowsort(UpperCamelCase__				,       mid + 1				,       UpperCamelCase__				)

							if sequence[end] < sequence[mid]:
														__lowercase     ,     __lowercase      =    sequence[mid], sequence[end]

							slowsort(UpperCamelCase__				,       UpperCamelCase__				,       end - 1				)


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

			testmod()












import itertools
import string
from collections.abc import Generator, Iterable







def 		_A(       UpperCamelCase__							:			Iterable[str]				,       UpperCamelCase__							:			int				)    -> Generator[tuple[str, ...], None, None]:
							'''simple docstring'''


							__lowercase      =    iter(UpperCamelCase__				)
							while True:
														__lowercase      =    tuple(itertools.islice(UpperCamelCase__				,       UpperCamelCase__				)				)
														if not chunk:
																					return
														yield chunk







def 		_A(       UpperCamelCase__							:			str				)    -> str:
							'''simple docstring'''


							__lowercase      =    ''''''.join([c.upper() for c in dirty if c in string.ascii_letters]				)
							__lowercase      =    ''''''

							if len(UpperCamelCase__				) < 2:
														return dirty

							for i in range(len(UpperCamelCase__				) - 1				):
														clean += dirty[i]

														if dirty[i] == dirty[i + 1]:
																					clean += "X"

							clean += dirty[-1]

							if len(UpperCamelCase__				) & 1:
														clean += "X"

							return clean







def 		_A(       UpperCamelCase__							:			str				)    -> list[str]:
							'''simple docstring'''


							__lowercase      =    '''ABCDEFGHIKLMNOPQRSTUVWXYZ'''
							# we're using a list instead of a '2d' array because it makes the math
							# for setting up the table and doing the actual encoding/decoding simpler
							__lowercase      =    []

							# copy key chars into the table if they are in `alphabet` ignoring duplicates
							for char in key.upper():
														if char not in table and char in alphabet:
																					table.append(UpperCamelCase__				)

    # fill the rest of the table in with the remaining alphabet chars
							for char in alphabet:
														if char not in table:
																					table.append(UpperCamelCase__				)

							return table







def 		_A(       UpperCamelCase__							:			str				,       UpperCamelCase__							:			str				)    -> str:
							'''simple docstring'''


							__lowercase      =    generate_table(UpperCamelCase__				)
							__lowercase      =    prepare_input(UpperCamelCase__				)
							__lowercase      =    ''''''

							# https://en.wikipedia.org/wiki/Playfair_cipher#Description
							for chara, chara in chunker(UpperCamelCase__				,       2				):
														__lowercase     ,     __lowercase      =    divmod(table.index(UpperCamelCase__				)				,       5				)
														__lowercase     ,     __lowercase      =    divmod(table.index(UpperCamelCase__				)				,       5				)

														if rowa == rowa:
																					ciphertext += table[rowa * 5 + (cola + 1) % 5]
																					ciphertext += table[rowa * 5 + (cola + 1) % 5]
														elif cola == cola:
																					ciphertext += table[((rowa + 1) % 5) * 5 + cola]
																					ciphertext += table[((rowa + 1) % 5) * 5 + cola]
														else:  # rectangle
																					ciphertext += table[rowa * 5 + cola]
																					ciphertext += table[rowa * 5 + cola]

							return ciphertext







def 		_A(       UpperCamelCase__							:			str				,       UpperCamelCase__							:			str				)    -> str:
							'''simple docstring'''


							__lowercase      =    generate_table(UpperCamelCase__				)
							__lowercase      =    ''''''

							# https://en.wikipedia.org/wiki/Playfair_cipher#Description
							for chara, chara in chunker(UpperCamelCase__				,       2				):
														__lowercase     ,     __lowercase      =    divmod(table.index(UpperCamelCase__				)				,       5				)
														__lowercase     ,     __lowercase      =    divmod(table.index(UpperCamelCase__				)				,       5				)

														if rowa == rowa:
																					plaintext += table[rowa * 5 + (cola - 1) % 5]
																					plaintext += table[rowa * 5 + (cola - 1) % 5]
														elif cola == cola:
																					plaintext += table[((rowa - 1) % 5) * 5 + cola]
																					plaintext += table[((rowa - 1) % 5) * 5 + cola]
														else:  # rectangle
																					plaintext += table[rowa * 5 + cola]
																					plaintext += table[rowa * 5 + cola]

							return plaintext






