






from __future__ import annotations







def 	_UpperCamelCase   (    UpperCamelCase_       :					str    ,       UpperCamelCase_       :					list[str] | None = None    ,       UpperCamelCase_       :					dict[str, float] | None = None    ,       UpperCamelCase_       :					bool = False    ,       )  ->   tuple[int, float, str]:

						"""simple docstring"""



						lowerCAmelCase__    						=						cipher_alphabet or [chr(UpperCamelCase_		) for i in range(97    ,       123		)]

						# If the argument is None or the user provided an empty dictionary
						if not frequencies_dict:
												# Frequencies of letters in the english language (how much they show up)
												lowerCAmelCase__    						=						{
												    'a': 0.0_8497,
												    'b': 0.0_1492,
												    'c': 0.0_2202,
												    'd': 0.0_4253,
												    'e': 0.1_1162,
												    'f': 0.0_2228,
												    'g': 0.0_2015,
												    'h': 0.0_6094,
												    'i': 0.0_7546,
												    'j': 0.0_0153,
												    'k': 0.0_1292,
												    'l': 0.0_4025,
												    'm': 0.0_2406,
												    'n': 0.0_6749,
												    'o': 0.0_7507,
												    'p': 0.0_1929,
												    'q': 0.0_0095,
												    'r': 0.0_7587,
												    's': 0.0_6327,
												    't': 0.0_9356,
												    'u': 0.0_2758,
												    'v': 0.0_0978,
												    'w': 0.0_2560,
												    'x': 0.0_0150,
												    'y': 0.0_1994,
												    'z': 0.0_0077,
												}
						else:
												# Custom frequencies dictionary
												lowerCAmelCase__    						=						frequencies_dict

						if not case_sensitive:
												lowerCAmelCase__    						=						ciphertext.lower()

						# Chi squared statistic values
						lowerCAmelCase__    						=						{}

						# cycle through all of the shifts
						for shift in range(len(UpperCamelCase_		)		):
												lowerCAmelCase__    						=						''

												# decrypt the message with the shift
												for letter in ciphertext:
																		try:
																								# Try to index the letter in the alphabet
																								lowerCAmelCase__    						=						(alphabet_letters.index(letter.lower()		) - shift) % len(
																								    UpperCamelCase_		)
																								decrypted_with_shift += (
																								    alphabet_letters[new_key].upper()
																								    if case_sensitive and letter.isupper()
																								    else alphabet_letters[new_key]
																								)
																		except ValueError:
																								# Append the character if it isn't in the alphabet
																								decrypted_with_shift += letter

												lowerCAmelCase__    						=						0.0

												# Loop through each letter in the decoded message with the shift
												for letter in decrypted_with_shift:
																		if case_sensitive:
																								lowerCAmelCase__    						=						letter.lower()
																								if letter in frequencies:
																														# Get the amount of times the letter occurs in the message
																														lowerCAmelCase__    						=						decrypted_with_shift.lower().count(UpperCamelCase_		)

																														# Get the excepcted amount of times the letter should appear based
																														# on letter frequencies
																														lowerCAmelCase__    						=						frequencies[letter] * occurrences

																														# Complete the chi squared statistic formula
																														lowerCAmelCase__    						=						((occurrences - expected) ** 2) / expected

																														# Add the margin of error to the total chi squared statistic
																														chi_squared_statistic += chi_letter_value
																		else:
																								if letter.lower() in frequencies:
																														# Get the amount of times the letter occurs in the message
																														lowerCAmelCase__    						=						decrypted_with_shift.count(UpperCamelCase_		)

																														# Get the excepcted amount of times the letter should appear based
																														# on letter frequencies
																														lowerCAmelCase__    						=						frequencies[letter] * occurrences

																														# Complete the chi squared statistic formula
																														lowerCAmelCase__    						=						((occurrences - expected) ** 2) / expected

																														# Add the margin of error to the total chi squared statistic
																														chi_squared_statistic += chi_letter_value

        # Add the data to the chi_squared_statistic_values dictionary
												lowerCAmelCase__    						=						(
												    chi_squared_statistic,
												    decrypted_with_shift,
												)

						# Get the most likely cipher by finding the cipher with the smallest chi squared
						# statistic
						def chi_squared_statistic_values_sorting_key(UpperCamelCase_       :					int		) -> tuple[float, str]:
												return chi_squared_statistic_values[key]

						lowerCAmelCase__    						=						min(
						    UpperCamelCase_    ,       key=UpperCamelCase_    ,       )

						# Get all the data from the most likely cipher (key, decoded message)
						(
						    (
						    lowerCAmelCase__
						)						,       (
						    lowerCAmelCase__
						)						,       
						)    						=						chi_squared_statistic_values[most_likely_cipher]

						# Return the data on the most likely shift
						return (
						    most_likely_cipher,
						    most_likely_cipher_chi_squared_value,
						    decoded_most_likely_cipher,
						)













__snake_case    :    Tuple         =     range(2, 20 + 1)
__snake_case    :    str         =     [10**k for k in range(ks[-1] + 1)]
__snake_case    :    dict[int, dict[int, list[list[int]]]]         =     {}







def 	_UpperCamelCase   (    UpperCamelCase_       :					Optional[int]    ,       UpperCamelCase_       :					List[Any]    ,       UpperCamelCase_       :					List[Any]    ,       UpperCamelCase_       :					Tuple		)  ->   List[Any]:

						"""simple docstring"""



						lowerCAmelCase__    						=						sum(a_i[j] for j in range(UpperCamelCase_    ,       len(UpperCamelCase_		)		)		)
						lowerCAmelCase__    						=						sum(a_i[j] * base[j] for j in range(min(len(UpperCamelCase_		)    ,       UpperCamelCase_		)		)		)

						lowerCAmelCase__						,       lowerCAmelCase__    						=						0, 0
						lowerCAmelCase__    						=						n - i

						lowerCAmelCase__    						=						memo.get(UpperCamelCase_		)

						if sub_memo is not None:
												lowerCAmelCase__    						=						sub_memo.get(UpperCamelCase_		)

												if jumps is not None and len(UpperCamelCase_		) > 0:
																		# find and make the largest jump without going over
																		lowerCAmelCase__    						=						-1
																		for _k in range(len(UpperCamelCase_		) - 1    ,       -1    ,       -1		):
																								if jumps[_k][2] <= k and jumps[_k][1] <= max_dn:
																														lowerCAmelCase__    						=						_k
																														break

																		if max_jump >= 0:
																								lowerCAmelCase__						,       lowerCAmelCase__						,       lowerCAmelCase__    						=						jumps[max_jump]
																								# since the difference between jumps is cached, add c
																								lowerCAmelCase__    						=						diff + c
																								for j in range(min(UpperCamelCase_    ,       len(UpperCamelCase_		)		)		):
																														lowerCAmelCase__						,       lowerCAmelCase__    						=						divmod(UpperCamelCase_    ,       10		)
																								if new_c > 0:
																														add(UpperCamelCase_    ,       UpperCamelCase_    ,       UpperCamelCase_		)

												else:
																		lowerCAmelCase__    						=						[]
						else:
												lowerCAmelCase__    						=						{c: []}
												lowerCAmelCase__    						=						sub_memo

						if dn >= max_dn or c + diff >= base[k]:
												return diff, dn

						if k > ks[0]:
												while True:
																		# keep doing smaller jumps
																		lowerCAmelCase__						,       lowerCAmelCase__    						=						next_term(UpperCamelCase_    ,       k - 1    ,       i + dn    ,       UpperCamelCase_		)
																		diff += _diff
																		dn += terms_jumped

																		if dn >= max_dn or c + diff >= base[k]:
																								break
						else:
												# would be too small a jump, just compute sequential terms instead
												lowerCAmelCase__						,       lowerCAmelCase__    						=						compute(UpperCamelCase_    ,       UpperCamelCase_    ,       i + dn    ,       UpperCamelCase_		)
												diff += _diff
												dn += terms_jumped

						lowerCAmelCase__    						=						sub_memo[c]

						# keep jumps sorted by # of terms skipped
						lowerCAmelCase__    						=						0
						while j < len(UpperCamelCase_		):
												if jumps[j][1] > dn:
																		break
												j += 1

						# cache the jump for this value digitsum(b) and c
						sub_memo[c].insert(UpperCamelCase_    ,       (diff, dn, k)		)
						return (diff, dn)







def 	_UpperCamelCase   (    UpperCamelCase_       :					Tuple    ,       UpperCamelCase_       :					List[str]    ,       UpperCamelCase_       :					int    ,       UpperCamelCase_       :					Tuple		)  ->   List[str]:

						"""simple docstring"""



						if i >= n:
												return 0, i
						if k > len(UpperCamelCase_		):
												a_i.extend([0 for _ in range(k - len(UpperCamelCase_		)		)]		)

						# note: a_i -> b * 10^k + c
						# ds_b -> digitsum(b)
						# ds_c -> digitsum(c)
						lowerCAmelCase__    						=						i
						lowerCAmelCase__						,       lowerCAmelCase__						,       lowerCAmelCase__    						=						0, 0, 0
						for j in range(len(UpperCamelCase_		)		):
												if j >= k:
																		ds_b += a_i[j]
												else:
																		ds_c += a_i[j]

						while i < n:
												i += 1
												lowerCAmelCase__    						=						ds_c + ds_b
												diff += addend
												lowerCAmelCase__    						=						0
												for j in range(UpperCamelCase_		):
																		lowerCAmelCase__    						=						a_i[j] + addend
																		lowerCAmelCase__						,       lowerCAmelCase__    						=						divmod(UpperCamelCase_    ,       10		)

																		ds_c += a_i[j]

												if addend > 0:
																		break

						if addend > 0:
												add(UpperCamelCase_    ,       UpperCamelCase_    ,       UpperCamelCase_		)
						return diff, i - start_i







def 	_UpperCamelCase   (    UpperCamelCase_       :					Tuple    ,       UpperCamelCase_       :					Optional[int]    ,       UpperCamelCase_       :					List[str]		)  ->   List[str]:

						"""simple docstring"""



						for j in range(UpperCamelCase_    ,       len(UpperCamelCase_		)		):
												lowerCAmelCase__    						=						digits[j] + addend
												if s >= 10:
																		lowerCAmelCase__						,       lowerCAmelCase__    						=						divmod(UpperCamelCase_    ,       10		)
																		lowerCAmelCase__    						=						addend // 10 + quotient
												else:
																		lowerCAmelCase__    						=						s
																		lowerCAmelCase__    						=						addend // 10

												if addend == 0:
																		break

						while addend > 0:
												lowerCAmelCase__						,       lowerCAmelCase__    						=						divmod(UpperCamelCase_    ,       10		)
												digits.append(UpperCamelCase_		)







def 	_UpperCamelCase   (    UpperCamelCase_       :					int = 10**15		)  ->   int:

						"""simple docstring"""



						lowerCAmelCase__    						=						[1]
						lowerCAmelCase__    						=						1
						lowerCAmelCase__    						=						0
						while True:
												lowerCAmelCase__						,       lowerCAmelCase__    						=						next_term(UpperCamelCase_    ,       20    ,       i + dn    ,       UpperCamelCase_		)
												dn += terms_jumped
												if dn == n - i:
																		break

						lowerCAmelCase__    						=						0
						for j in range(len(UpperCamelCase_		)		):
												a_n += digits[j] * 10**j
						return a_n


if __name__ == "__main__":
					print(f'{solution() = }')





