


from __future__ import annotations

import random
from collections.abc import Iterable



class    __lowercase  :

							"""simple docstring"""


							def __init__(    self				, A_	)->	None:
											_SCREAMING_SNAKE_CASE      = {literal: None for literal in literals}





							def __str__(    self	)->	str:
											return "{" + " , ".join(self.literals	) + "}"





							def __len__(    self	)->	int:
											return len(self.literals	)





							def 		__magic_name__			(    self				, A_	)->	None:
											for literal in self.literals:
															_SCREAMING_SNAKE_CASE      = literal[:2]
															if symbol in model:
																			_SCREAMING_SNAKE_CASE      = model[symbol]
															else:
																			continue
															if value is not None:
																			# Complement assignment if literal is in complemented form
																			if literal.endswith('\''	):
																							_SCREAMING_SNAKE_CASE      = not value
															_SCREAMING_SNAKE_CASE      = value





							def 		__magic_name__			(    self				, A_	)->	bool | None:
											for literal in self.literals:
															_SCREAMING_SNAKE_CASE      = literal.rstrip('\''	) if literal.endswith('\''	) else literal + '\''
															if symbol in self.literals:
																			return True

											self.assign(A_	)
											for value in self.literals.values():
															if value in (True, None):
																			return value
											return any(self.literals.values()	)







class    __lowercase  :

							"""simple docstring"""


							def __init__(    self				, A_	)->	None:
											_SCREAMING_SNAKE_CASE      = list(A_	)





							def __str__(    self	)->	str:
											return "{" + " , ".join(str(A_	) for clause in self.clauses	) + "}"







def 				SCREAMING_SNAKE_CASE (     ):

				"""simple docstring"""






				_SCREAMING_SNAKE_CASE      = []
				_SCREAMING_SNAKE_CASE      = random.randint(1   ,5							)
				_SCREAMING_SNAKE_CASE      = 'A'
				_SCREAMING_SNAKE_CASE      = 0
				while i < no_of_literals:
								_SCREAMING_SNAKE_CASE      = random.randint(1   ,5							)
								_SCREAMING_SNAKE_CASE      = base_var + str(UpperCAmelCase__							)
								_SCREAMING_SNAKE_CASE      = random.randint(0   ,1							)
								if var_complement == 1:
												var_name += "'"
								if var_name in literals:
												i -= 1
								else:
												literals.append(UpperCAmelCase__							)
								i += 1
				return Clause(UpperCAmelCase__							)


def 				SCREAMING_SNAKE_CASE (     ):

				"""simple docstring"""






				_SCREAMING_SNAKE_CASE      = set()
				_SCREAMING_SNAKE_CASE      = random.randint(1   ,10							)
				while len(UpperCAmelCase__							) < no_of_clauses:
								clauses.add(generate_clause()							)
				return Formula(UpperCAmelCase__							)


def 				SCREAMING_SNAKE_CASE (     UpperCAmelCase__							):

				"""simple docstring"""






				_SCREAMING_SNAKE_CASE      = formula.clauses
				_SCREAMING_SNAKE_CASE      = []
				for clause in formula.clauses:
								for literal in clause.literals:
												_SCREAMING_SNAKE_CASE      = literal[:2]
												if symbol not in symbols_set:
																symbols_set.append(UpperCAmelCase__							)
				return clauses, symbols_set


def 				SCREAMING_SNAKE_CASE (     UpperCAmelCase__   ,UpperCAmelCase__   ,UpperCAmelCase__							):

				"""simple docstring"""






				_SCREAMING_SNAKE_CASE      = []
				_SCREAMING_SNAKE_CASE      = {}
				_SCREAMING_SNAKE_CASE      = []

				for clause in clauses:
								if clause.evaluate(UpperCAmelCase__							):
												continue
								for literal in clause.literals:
												literals.append(UpperCAmelCase__							)

				for s in symbols:
								_SCREAMING_SNAKE_CASE      = s + '\''
								if (s in literals and sym not in literals) or (
								    s not in literals and sym in literals
								):
												pure_symbols.append(UpperCAmelCase__							)
				for p in pure_symbols:
								_SCREAMING_SNAKE_CASE      = None
				for s in pure_symbols:
								_SCREAMING_SNAKE_CASE      = s + '\''
								if s in literals:
												_SCREAMING_SNAKE_CASE      = True
								elif sym in literals:
												_SCREAMING_SNAKE_CASE      = False
				return pure_symbols, assignment


def 				SCREAMING_SNAKE_CASE (     UpperCAmelCase__   ,UpperCAmelCase__							):

				"""simple docstring"""






				_SCREAMING_SNAKE_CASE      = []
				for clause in clauses:
								if len(UpperCAmelCase__							) == 1:
												unit_symbols.append(list(clause.literals.keys()							)[0]							)
								else:
												_SCREAMING_SNAKE_CASE      ,      _SCREAMING_SNAKE_CASE      = 0, 0
												for literal, value in clause.literals.items():
																if value is False:
																				f_count += 1
																elif value is None:
																				_SCREAMING_SNAKE_CASE      = literal
																				n_count += 1
												if f_count == len(UpperCAmelCase__							) - 1 and n_count == 1:
																unit_symbols.append(UpperCAmelCase__							)
				_SCREAMING_SNAKE_CASE      = {}
				for i in unit_symbols:
								_SCREAMING_SNAKE_CASE      = i[:2]
								_SCREAMING_SNAKE_CASE      = len(UpperCAmelCase__							) == 2
				_SCREAMING_SNAKE_CASE      = [i[:2] for i in unit_symbols]

				return unit_symbols, assignment


def 				SCREAMING_SNAKE_CASE (     UpperCAmelCase__   ,UpperCAmelCase__   ,UpperCAmelCase__							):

				"""simple docstring"""






				_SCREAMING_SNAKE_CASE      = True
				for clause in clauses:
								_SCREAMING_SNAKE_CASE      = clause.evaluate(UpperCAmelCase__							)
								if clause_check is False:
												return False, None
								elif clause_check is None:
												_SCREAMING_SNAKE_CASE      = False
												continue

				if check_clause_all_true:
								return True, model

				try:
								_SCREAMING_SNAKE_CASE      ,      _SCREAMING_SNAKE_CASE      = find_pure_symbols(UpperCAmelCase__   ,UpperCAmelCase__   ,UpperCAmelCase__							)
				except RecursionError:
								print('raises a RecursionError and is'							)
								return None, {}
				_SCREAMING_SNAKE_CASE      = None
				if len(UpperCAmelCase__							) > 0:
								_SCREAMING_SNAKE_CASE      ,      _SCREAMING_SNAKE_CASE      = pure_symbols[0], assignment[pure_symbols[0]]

				if p:
								_SCREAMING_SNAKE_CASE      = model
								_SCREAMING_SNAKE_CASE      = value
								_SCREAMING_SNAKE_CASE      = list(UpperCAmelCase__							)
								if p in tmp_symbols:
												tmp_symbols.remove(UpperCAmelCase__							)
								return dpll_algorithm(UpperCAmelCase__   ,UpperCAmelCase__   ,UpperCAmelCase__							)

				_SCREAMING_SNAKE_CASE      ,      _SCREAMING_SNAKE_CASE      = find_unit_clauses(UpperCAmelCase__   ,UpperCAmelCase__							)
				_SCREAMING_SNAKE_CASE      = None
				if len(UpperCAmelCase__							) > 0:
								_SCREAMING_SNAKE_CASE      ,      _SCREAMING_SNAKE_CASE      = unit_symbols[0], assignment[unit_symbols[0]]
				if p:
								_SCREAMING_SNAKE_CASE      = model
								_SCREAMING_SNAKE_CASE      = value
								_SCREAMING_SNAKE_CASE      = list(UpperCAmelCase__							)
								if p in tmp_symbols:
												tmp_symbols.remove(UpperCAmelCase__							)
								return dpll_algorithm(UpperCAmelCase__   ,UpperCAmelCase__   ,UpperCAmelCase__							)
				_SCREAMING_SNAKE_CASE      = symbols[0]
				_SCREAMING_SNAKE_CASE      = symbols[1:]
				_SCREAMING_SNAKE_CASE      ,      _SCREAMING_SNAKE_CASE      = model, model
				_SCREAMING_SNAKE_CASE      ,      _SCREAMING_SNAKE_CASE      = True, False

				return dpll_algorithm(UpperCAmelCase__   ,UpperCAmelCase__   ,UpperCAmelCase__							) or dpll_algorithm(UpperCAmelCase__   ,UpperCAmelCase__   ,UpperCAmelCase__							)


if __name__ == "__main__":
							import doctest

							doctest.testmod()

							snake_case			:      List[Any] 							=   generate_formula()
							print(f"""The formula {formula} is""", end=' ')

							snake_case							,		snake_case			:      Optional[Any] 							=   generate_parameters(formula)
							snake_case							,		snake_case			:      Dict 							=   dpll_algorithm(clauses, symbols, {})

							if solution:
														print(f"""satisfiable with the assignment {model}.""")
							else:
														print('not satisfiable.')




from __future__ import annotations

from collections import Counter


def 				SCREAMING_SNAKE_CASE (     UpperCAmelCase__							):

				"""simple docstring"""






				_SCREAMING_SNAKE_CASE      = [True] * n
				_SCREAMING_SNAKE_CASE      = False
				_SCREAMING_SNAKE_CASE      = False
				_SCREAMING_SNAKE_CASE      = True

				for i in range(3   ,int(n**0.5 + 1							)   ,2							):
								_SCREAMING_SNAKE_CASE      = i * 2
								while index < n:
												_SCREAMING_SNAKE_CASE      = False
												_SCREAMING_SNAKE_CASE      = index + i

				_SCREAMING_SNAKE_CASE      = [2]

				for i in range(3   ,UpperCAmelCase__   ,2							):
								if is_prime[i]:
												primes.append(UpperCAmelCase__							)

				return primes


def 				SCREAMING_SNAKE_CASE (     UpperCAmelCase__							):

				"""simple docstring"""






				_SCREAMING_SNAKE_CASE      = str(UpperCAmelCase__							)
				_SCREAMING_SNAKE_CASE      = []
				_SCREAMING_SNAKE_CASE      = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

				for duplicate in Counter(UpperCAmelCase__							) - Counter(set(UpperCAmelCase__							)							):
								_SCREAMING_SNAKE_CASE      = [int(number_str.replace(UpperCAmelCase__   ,UpperCAmelCase__							)							) for digit in digits]
								replacements.append(UpperCAmelCase__							)

				return replacements


def 				SCREAMING_SNAKE_CASE (     UpperCAmelCase__ = 8							):

				"""simple docstring"""






				_SCREAMING_SNAKE_CASE      = set()

				# Filter primes with less than 3 replaceable digits
				_SCREAMING_SNAKE_CASE      = {
				    x for x in set(prime_sieve(100_0000							)							) if len(str(UpperCAmelCase__							)							) - len(set(str(UpperCAmelCase__							)							)							) >= 3
				}

				for prime in primes:
								if prime in numbers_checked:
												continue

								_SCREAMING_SNAKE_CASE      = digit_replacements(UpperCAmelCase__							)

								for family in replacements:
												numbers_checked.update(UpperCAmelCase__							)
												_SCREAMING_SNAKE_CASE      = primes.intersection(UpperCAmelCase__							)

												if len(UpperCAmelCase__							) != family_length:
																continue

												return min(UpperCAmelCase__							)

				return -1


if __name__ == "__main__":
							print(solution())
