
"""simple docstring"""







import os
import random
import sys

from . import cryptomath_module as cryptomath
from . import rabin_miller

lowerCamelCase__           =	3
def 					__lowerCAmelCase       (_UpperCamelCase	):
	print('Generating primitive root of p'	)
	while True:
		__lowerCAmelCase    :		Any		    =   random.randrange(3 ,						_UpperCamelCase	)
		if pow(_UpperCamelCase ,						2 ,						_UpperCamelCase	) == 1:
			continue
		if pow(_UpperCamelCase ,						_UpperCamelCase ,						_UpperCamelCase	) == 1:
			continue
		return g
def 					__lowerCAmelCase       (_UpperCamelCase	):
	print('Generating prime p...'	)
	__lowerCAmelCase    :		List[str]		    =   rabin_miller.generate_large_prime(_UpperCamelCase	)  # select large prime number.
	__lowerCAmelCase    :		Optional[int]		    =   primitive_root(_UpperCamelCase	)  # one primitive root on modulo p.
	__lowerCAmelCase    :		Union[str, Any]		    =   random.randrange(3 ,						_UpperCamelCase	)  # private_key -> have to be greater than 2 for safety.
	__lowerCAmelCase    :		Dict		    =   cryptomath.find_mod_inverse(pow(_UpperCamelCase ,						_UpperCamelCase ,						_UpperCamelCase	) ,						_UpperCamelCase	)

	__lowerCAmelCase    :		Tuple		    =   (key_size, e_a, e_a, p)
	__lowerCAmelCase    :		str		    =   (key_size, d)

	return public_key, private_key
def 					__lowerCAmelCase       (_UpperCamelCase ,						_UpperCamelCase	):
	if os.path.exists(F"{name}_pubkey.txt"	) or os.path.exists(F"{name}_privkey.txt"	):
		print('\nWARNING:'	)
		print(
		    F"\"{name}_pubkey.txt\" or \"{name}_privkey.txt\" already exists. \n"
		    'Use a different name or delete these files and re-run this program.'	)
		sys.exit()

	__lowerCAmelCase    ,     __lowerCAmelCase    :		str		    =   generate_key(_UpperCamelCase	)
	print(F"\nWriting public key to file {name}_pubkey.txt..."	)
	with open(F"{name}_pubkey.txt" ,						'w'	) as fo:
		fo.write(F"{public_key[0]},{public_key[1]},{public_key[2]},{public_key[3]}"	)

	print(F"Writing private key to file {name}_privkey.txt..."	)
	with open(F"{name}_privkey.txt" ,						'w'	) as fo:
		fo.write(F"{private_key[0]},{private_key[1]}"	)
def 					__lowerCAmelCase       ():
	print('Making key files...'	)
	make_key_files('elgamal' ,						2048	)
	print('Key files generation successful'	)


if __name__ == "__main__":
							main()

"""simple docstring"""







from collections.abc import Sequence
from queue import Queue




class 				A__ :

		def __init__(   self ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE=None ,	_SCREAMING_SNAKE_CASE=None				):
			__lowerCAmelCase    :		List[str]		    =   start
			__lowerCAmelCase    :		Union[str, Any]		    =   end
			__lowerCAmelCase    :		Union[str, Any]		    =   val
			__lowerCAmelCase    :		Dict		    =   (start + end) // 2
			__lowerCAmelCase    :		Dict		    =   left
			__lowerCAmelCase    :		List[Any]		    =   right







		def __repr__(   self				):
			return f"SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})"




class 				A__ :

		def __init__(   self ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE				):
			__lowerCAmelCase    :		Optional[Any]		    =   collection
			__lowerCAmelCase    :		Optional[int]		    =   function
			if self.collection:
				__lowerCAmelCase    :		str		    =   self._build_tree(0 ,	len(_SCREAMING_SNAKE_CASE				) - 1				)

		def 							__lowerCamelCase							(   self ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE				):
			self._update_tree(self.root ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE				)

		def 							__lowerCamelCase							(   self ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE				):
			return self._query_range(self.root ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE				)

		def 							__lowerCamelCase							(   self ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE				):
			if start == end:
				return SegmentTreeNode(_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE ,	self.collection[start]				)
			__lowerCAmelCase    :		Tuple		    =   (start + end) // 2
			__lowerCAmelCase    :		List[str]		    =   self._build_tree(_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE				)
			__lowerCAmelCase    :		Dict		    =   self._build_tree(mid + 1 ,	_SCREAMING_SNAKE_CASE				)
			return SegmentTreeNode(_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE ,	self.fn(left.val ,	right.val				) ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE				)

		def 							__lowerCamelCase							(   self ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE				):
			if node.start == i and node.end == i:
				__lowerCAmelCase    :		int		    =   val
				return
			if i <= node.mid:
				self._update_tree(node.left ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE				)
			else:
				self._update_tree(node.right ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE				)
			__lowerCAmelCase    :		Optional[Any]		    =   self.fn(node.left.val ,	node.right.val				)

		def 							__lowerCamelCase							(   self ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE				):
			if node.start == i and node.end == j:
				return node.val

			if i <= node.mid:
				if j <= node.mid:
					# range in left child tree
					return self._query_range(node.left ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE				)
				else:
					# range in left child tree and right child tree
					return self.fn(
					    self._query_range(node.left ,	_SCREAMING_SNAKE_CASE ,	node.mid				) ,	self._query_range(node.right ,	node.mid + 1 ,	_SCREAMING_SNAKE_CASE				) ,	)
			else:
				# range in right child tree
				return self._query_range(node.right ,	_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE				)







		def 							__lowerCamelCase							(   self				):
			if self.root is not None:
				__lowerCAmelCase    :		Optional[Any]		    =   Queue()
				queue.put(self.root				)
				while not queue.empty():
					__lowerCAmelCase    :		str		    =   queue.get()
					yield node

					if node.left is not None:
						queue.put(node.left				)

					if node.right is not None:
						queue.put(node.right				)


if __name__ == "__main__":
							import operator

							for fn in [operator.add, max, min]:
														print("""*""" * 50)
														lowerCamelCase__           =	SegmentTree([2, 1, 5, 3, 4], fn)
														for node in arr.traverse():
																					print(node)
														print()

														arr.update(1, 5)
														for node in arr.traverse():
																					print(node)
														print()

														print(arr.query_range(3, 4))  # 7
														print(arr.query_range(2, 2))  # 5
														print(arr.query_range(1, 3))  # 13
														print()