






import os
import re
import unicodedata
from shutil import copyfile
from typing import Any, Dict, List, Optional, Tuple

import sentencepiece as spm

from ...tokenization_utils import AddedToken, PreTrainedTokenizer
from ...utils import logging


__UpperCAmelCase										=		logging.get_logger(__name__)
__UpperCAmelCase										=		{'vocab_file': 'spiece.model'}

__UpperCAmelCase										=		{
    'vocab_file': {
        'google/fnet-base': 'https://huggingface.co/google/fnet-base/resolve/main/spiece.model',
        'google/fnet-large': 'https://huggingface.co/google/fnet-large/resolve/main/spiece.model',
    },
}

__UpperCAmelCase										=		{
    'google/fnet-base': 512,
    'google/fnet-large': 512,
}

__UpperCAmelCase										=		'▁'



class 						lowerCamelCase   (_snake_case    ):







		'''simple docstring'''



		_snake_case					:					List[Any] 		=						VOCAB_FILES_NAMES
		_snake_case					:					Optional[Any] 		=						PRETRAINED_VOCAB_FILES_MAP
		_snake_case					:					Any 		=						PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
		_snake_case					:					List[str] 		=						['''input_ids''', '''token_type_ids''']



		def __init__(							self       ,	_UpperCamelCase       ,	_UpperCamelCase=False       ,	_UpperCamelCase=True       ,	_UpperCamelCase=True       ,	_UpperCamelCase="<unk>"       ,	_UpperCamelCase="[SEP]"       ,	_UpperCamelCase="<pad>"       ,	_UpperCamelCase="[CLS]"       ,	_UpperCamelCase="[MASK]"       ,	_UpperCamelCase = None       ,	**_UpperCamelCase       ,	)			->							None:
							# Mask token behave like a normal word, i.e. include the space before it and
							# is included in the raw text, there should be a match in a non-normalized sentence.
							UpperCAmelCase_					:   Any   =		(
							    AddedToken(_UpperCamelCase       ,	lstrip=_UpperCamelCase       ,	rstrip=_UpperCamelCase       ,	normalized=_UpperCamelCase     )
							    if isinstance(_UpperCamelCase       ,	_UpperCamelCase     )
							    else mask_token
							)

							UpperCAmelCase_					:   Optional[Any]   =		{} if sp_model_kwargs is None else sp_model_kwargs

							super().__init__(
							    do_lower_case=_UpperCamelCase       ,	remove_space=_UpperCamelCase       ,	keep_accents=_UpperCamelCase       ,	unk_token=_UpperCamelCase       ,	sep_token=_UpperCamelCase       ,	pad_token=_UpperCamelCase       ,	cls_token=_UpperCamelCase       ,	mask_token=_UpperCamelCase       ,	sp_model_kwargs=self.sp_model_kwargs       ,	**_UpperCamelCase       ,	)

							UpperCAmelCase_					:   Dict   =		do_lower_case
							UpperCAmelCase_					:   str   =		remove_space
							UpperCAmelCase_					:   Tuple   =		keep_accents
							UpperCAmelCase_					:   Optional[Any]   =		vocab_file

							UpperCAmelCase_					:   List[str]   =		spm.SentencePieceProcessor(**self.sp_model_kwargs     )
							self.sp_model.Load(_UpperCamelCase     )



		@property
		def       __UpperCAmelCase    (							self     )			->							Dict:
							return len(self.sp_model     )



		def       __UpperCAmelCase    (							self     )			->							Optional[int]:
							UpperCAmelCase_					:   int   =		{self.convert_ids_to_tokens(_UpperCamelCase     ): i for i in range(self.vocab_size     )}
							vocab.update(self.added_tokens_encoder     )
							return vocab



		def __getstate__(							self     )			->							List[Any]:
							UpperCAmelCase_					:   Optional[int]   =		self.__dict__.copy()
							UpperCAmelCase_					:   Optional[Any]   =		None
							return state



		def __setstate__(							self       ,	_UpperCamelCase     )			->							Union[str, Any]:
							UpperCAmelCase_					:   int   =		d

							# for backward compatibility
							if not hasattr(self       ,	'sp_model_kwargs'     ):
												UpperCAmelCase_					:   Optional[Any]   =		{}

							UpperCAmelCase_					:   List[Any]   =		spm.SentencePieceProcessor(**self.sp_model_kwargs     )
							self.sp_model.Load(self.vocab_file     )



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase     )			->							Optional[Any]:
							if self.remove_space:
												UpperCAmelCase_					:   Optional[int]   =		' '.join(inputs.strip().split()     )
							else:
												UpperCAmelCase_					:   str   =		inputs
							UpperCAmelCase_					:   List[Any]   =		outputs.replace('``'       ,	'"'     ).replace('\'\''       ,	'"'     )

							if not self.keep_accents:
												UpperCAmelCase_					:   Union[str, Any]   =		unicodedata.normalize('NFKD'       ,	_UpperCamelCase     )
												UpperCAmelCase_					:   str   =		''.join([c for c in outputs if not unicodedata.combining(_UpperCamelCase     )]     )
							if self.do_lower_case:
												UpperCAmelCase_					:   Union[str, Any]   =		outputs.lower()

							return outputs



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase     )			->							List[str]:
							UpperCAmelCase_					:   Union[str, Any]   =		self.preprocess_text(_UpperCamelCase     )
							UpperCAmelCase_					:   Tuple   =		self.sp_model.encode(_UpperCamelCase       ,	out_type=_UpperCamelCase     )
							UpperCAmelCase_					:   Tuple   =		[]
							for piece in pieces:
												if len(_UpperCamelCase     ) > 1 and piece[-1] == str(','     ) and piece[-2].isdigit():
																	UpperCAmelCase_					:   str   =		self.sp_model.EncodeAsPieces(piece[:-1].replace(_UpperCamelCase       ,	''     )     )
																	if piece[0] != SPIECE_UNDERLINE and cur_pieces[0][0] == SPIECE_UNDERLINE:
																						if len(cur_pieces[0]     ) == 1:
																											UpperCAmelCase_					:   Any   =		cur_pieces[1:]
																						else:
																											UpperCAmelCase_					:   Tuple   =		cur_pieces[0][1:]
																	cur_pieces.append(piece[-1]     )
																	new_pieces.extend(_UpperCamelCase     )
												else:
																	new_pieces.append(_UpperCamelCase     )

							return new_pieces



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase     )			->							Any:
							return self.sp_model.PieceToId(_UpperCamelCase     )



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase     )			->							Union[str, Any]:
							return self.sp_model.IdToPiece(_UpperCamelCase     )



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase     )			->							List[Any]:
							UpperCAmelCase_					:   Any   =		[]
							UpperCAmelCase_					:   List[str]   =		''
							UpperCAmelCase_					:   str   =		False
							for token in tokens:
												# make sure that special tokens are not decoded using sentencepiece model
												if token in self.all_special_tokens:
																	if not prev_is_special:
																						out_string += " "
																	out_string += self.sp_model.decode(_UpperCamelCase     ) + token
																	UpperCAmelCase_					:   Optional[Any]   =		True
																	UpperCAmelCase_					:   str   =		[]
												else:
																	current_sub_tokens.append(_UpperCamelCase     )
																	UpperCAmelCase_					:   str   =		False
							out_string += self.sp_model.decode(_UpperCamelCase     )
							return out_string.strip()



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase       ,	_UpperCamelCase = False       ,	_UpperCamelCase = None       ,	_UpperCamelCase = True       ,	**_UpperCamelCase       ,	)			->							str:
							UpperCAmelCase_					:   Tuple   =		kwargs.pop('use_source_tokenizer'       ,	_UpperCamelCase     )

							UpperCAmelCase_					:   Union[str, Any]   =		self.convert_ids_to_tokens(_UpperCamelCase       ,	skip_special_tokens=_UpperCamelCase     )

							# To avoid mixing byte-level and unicode for byte-level BPT
							# we need to build string separately for added tokens and byte-level tokens
							# cf. https://github.com/huggingface/transformers/issues/1133
							UpperCAmelCase_					:   List[Any]   =		[]
							UpperCAmelCase_					:   Dict   =		[]
							for token in filtered_tokens:
												if skip_special_tokens and token in self.all_special_ids:
																	continue
												if token in self.added_tokens_encoder:
																	if current_sub_text:
																						sub_texts.append(self.convert_tokens_to_string(_UpperCamelCase     )     )
																						UpperCAmelCase_					:   Union[str, Any]   =		[]
																	sub_texts.append(_UpperCamelCase     )
												else:
																	current_sub_text.append(_UpperCamelCase     )
							if current_sub_text:
												sub_texts.append(self.convert_tokens_to_string(_UpperCamelCase     )     )

							# Mimic the behavior of the Rust tokenizer:
							# No space after <unk>
							if spaces_between_special_tokens:
												UpperCAmelCase_					:   str   =		re.sub(r'(<unk>) '       ,	r'\1'       ,	' '.join(_UpperCamelCase     )     )
							else:
												UpperCAmelCase_					:   int   =		''.join(_UpperCamelCase     )

							UpperCAmelCase_					:   int   =		(
							    clean_up_tokenization_spaces
							    if clean_up_tokenization_spaces is not None
							    else self.clean_up_tokenization_spaces
							)
							if clean_up_tokenization_spaces:
												UpperCAmelCase_					:   Dict   =		self.clean_up_tokenization(_UpperCamelCase     )
												return clean_text
							else:
												return text



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase       ,	_UpperCamelCase = None     )			->							List[int]:
							UpperCAmelCase_					:   str   =		[self.sep_token_id]
							UpperCAmelCase_					:   Dict   =		[self.cls_token_id]
							if token_ids_a is None:
												return cls + token_ids_a + sep
							return cls + token_ids_a + sep + token_ids_a + sep



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase       ,	_UpperCamelCase = None       ,	_UpperCamelCase = False     )			->							List[int]:

							if already_has_special_tokens:
												return super().get_special_tokens_mask(
												    token_ids_a=_UpperCamelCase       ,	token_ids_a=_UpperCamelCase       ,	already_has_special_tokens=_UpperCamelCase     )

							if token_ids_a is not None:
												return [1] + ([0] * len(_UpperCamelCase     )) + [1] + ([0] * len(_UpperCamelCase     )) + [1]
							return [1] + ([0] * len(_UpperCamelCase     )) + [1]



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase       ,	_UpperCamelCase = None     )			->							List[int]:
							UpperCAmelCase_					:   Tuple   =		[self.sep_token_id]
							UpperCAmelCase_					:   Union[str, Any]   =		[self.cls_token_id]

							if token_ids_a is None:
												return len(cls + token_ids_a + sep     ) * [0]
							return len(cls + token_ids_a + sep     ) * [0] + len(token_ids_a + sep     ) * [1]



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase       ,	_UpperCamelCase = None     )			->							Tuple[str]:
							if not os.path.isdir(_UpperCamelCase     ):
												logger.error(f"Vocabulary path ({save_directory}) should be a directory"     )
												return
							UpperCAmelCase_					:   Optional[Any]   =		os.path.join(
							    _UpperCamelCase       ,	(filename_prefix + '-' if filename_prefix else '') + VOCAB_FILES_NAMES['vocab_file']     )

							if os.path.abspath(self.vocab_file     ) != os.path.abspath(_UpperCamelCase     ) and os.path.isfile(self.vocab_file     ):
												copyfile(self.vocab_file       ,	_UpperCamelCase     )
							elif not os.path.isfile(self.vocab_file     ):
												with open(_UpperCamelCase       ,	'wb'     ) as fi:
																	UpperCAmelCase_					:   Optional[Any]   =		self.sp_model.serialized_model_proto()
																	fi.write(_UpperCamelCase     )

							return (out_vocab_file,)














from __future__ import annotations




def   lowercase__   (  __snake_case					:							Any  , __snake_case					:							int						):


					'''simple docstring'''


					UpperCAmelCase_					:   Optional[int]   =		0
					UpperCAmelCase_					:   Optional[int]   =		len(__snake_case						) - 1
					while left <= right:
										UpperCAmelCase_					:   Optional[Any]   =		(left + right) // 2
										if left == right:
															if sorted_list[middle] < item:
																				UpperCAmelCase_					:   List[Any]   =		middle + 1
															break
										elif sorted_list[middle] < item:
															UpperCAmelCase_					:   Union[str, Any]   =		middle + 1
										else:
															UpperCAmelCase_					:   Tuple   =		middle - 1
					sorted_list.insert(__snake_case  , __snake_case						)
					return sorted_list




def   lowercase__   (  __snake_case					:							Union[str, Any]  , __snake_case					:							int						):


					'''simple docstring'''


					UpperCAmelCase_					:   str   =		[]
					while left and right:
										if left[0][0] < right[0][0]:
															result.append(left.pop(0						)						)
										else:
															result.append(right.pop(0						)						)
					return result + left + right




def   lowercase__   (  __snake_case					:							Dict						):


					'''simple docstring'''


					UpperCAmelCase_					:   str   =		len(__snake_case						)
					if length <= 1:
										return list_ad
					UpperCAmelCase_					:   List[Any]   =		length // 2
					return merge(sortlist_ad(list_ad[:middle]						)  , sortlist_ad(list_ad[middle:]						)						)




def   lowercase__   (  __snake_case					:							list[int]						):


					'''simple docstring'''


					if len(__snake_case						) <= 1:
										return collection
					UpperCAmelCase_					:   Any   =		[]
					UpperCAmelCase_					:   Union[str, Any]   =		False
					for i in range(0  , len(__snake_case						)  , 2						):
										if i == len(__snake_case						) - 1:
															UpperCAmelCase_					:   Tuple   =		True
										else:
															if collection[i] < collection[i + 1]:
																				two_paired_list.append([collection[i], collection[i + 1]]						)
															else:
																				two_paired_list.append([collection[i + 1], collection[i]]						)
					UpperCAmelCase_					:   Union[str, Any]   =		sortlist_ad(__snake_case						)
					UpperCAmelCase_					:   Any   =		[i[0] for i in sorted_list_ad]
					result.append(sorted_list_ad[-1][1]						)
					if has_last_odd_item:
										UpperCAmelCase_					:   Union[str, Any]   =		collection[-1]
										UpperCAmelCase_					:   List[Any]   =		binary_search_insertion(__snake_case  , __snake_case						)
					UpperCAmelCase_					:   Tuple   =		False
					for i in range(len(__snake_case						) - 1						):
										if result[i] == collection[-1] and has_last_odd_item:
															UpperCAmelCase_					:   List[Any]   =		True
										UpperCAmelCase_					:   Optional[int]   =		sorted_list_ad[i][1]
										# If last_odd_item is inserted before the item's index,
										# you should forward index one more.
										if is_last_odd_item_inserted_before_this_index:
															UpperCAmelCase_					:   List[str]   =		result[: i + 2] + binary_search_insertion(result[i + 2 :]  , __snake_case						)
										else:
															UpperCAmelCase_					:   List[Any]   =		result[: i + 1] + binary_search_insertion(result[i + 1 :]  , __snake_case						)

					return result


if __name__ == "__main__":
		__UpperCAmelCase										=		input('Enter numbers separated by a comma:\n').strip()
		__UpperCAmelCase										=		[int(item) for item in user_input.split(',')]
		print(merge_insertion_sort(unsorted))






