



def        lowerCamelCase__    (    __lowerCAmelCase  :  str   ,							__lowerCAmelCase  :  int = 13    ):




			"""simple docstring"""


			lowerCAmelCase_      =     ""
			for c in s:
						if "A" <= c <= "Z":
									out += chr(ord("A"    ) + (ord(__lowerCAmelCase    ) - ord("A"    ) + n) % 26    )
						elif "a" <= c <= "z":
									out += chr(ord("a"    ) + (ord(__lowerCAmelCase    ) - ord("a"    ) + n) % 26    )
						else:
									out += c
			return out






def        lowerCamelCase__    (    ):




			"""simple docstring"""


			lowerCAmelCase_      =     input("Enter message: "    )

			lowerCAmelCase_      =     dencrypt(__lowerCAmelCase   ,							13    )
			print("Encryption:"   ,							__lowerCAmelCase    )

			lowerCAmelCase_      =     dencrypt(__lowerCAmelCase   ,							13    )
			print("Decryption: "   ,							__lowerCAmelCase    )


if __name__ == "__main__":
			import doctest

			doctest.testmod()
			main()





import math





class      _lowerCAmelCase :




				def __init__( self    ,    _UpperCamelCase					)    ->				Dict:
							lowerCAmelCase_      =     len(_UpperCamelCase					)
							lowerCAmelCase_      =     [0] * (
							    4 * self.N
							)  # approximate the overall size of segment tree with array N
							self.build(1    ,    0    ,    self.N - 1					)




				def 					__a						( self    ,    _UpperCamelCase					)    ->				List[str]:
							return idx * 2




				def 					__a						( self    ,    _UpperCamelCase					)    ->				Tuple:
							return idx * 2 + 1




				def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				int:  # noqa: E741
							if l == r:
										lowerCAmelCase_      =     A[l]
							else:
										lowerCAmelCase_      =     (l + r) // 2
										self.build(self.left(_UpperCamelCase					)    ,    _UpperCamelCase    ,    _UpperCamelCase					)
										self.build(self.right(_UpperCamelCase					)    ,    mid + 1    ,    _UpperCamelCase					)
										lowerCAmelCase_      =     max(self.st[self.left(_UpperCamelCase					)]    ,    self.st[self.right(_UpperCamelCase					)]					)




				def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				int:
							return self.update_recursive(1    ,    0    ,    self.N - 1    ,    a - 1    ,    b - 1    ,    _UpperCamelCase					)




				def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				str:  # noqa: E741
							if r < a or l > b:
										return True
							if l == r:
										lowerCAmelCase_      =     val
										return True
							lowerCAmelCase_      =     (l + r) // 2
							self.update_recursive(self.left(_UpperCamelCase					)    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)
							self.update_recursive(self.right(_UpperCamelCase					)    ,    mid + 1    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)
							lowerCAmelCase_      =     max(self.st[self.left(_UpperCamelCase					)]    ,    self.st[self.right(_UpperCamelCase					)]					)
							return True




				def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				Optional[Any]:
							return self.query_recursive(1    ,    0    ,    self.N - 1    ,    a - 1    ,    b - 1					)




				def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				Any:  # noqa: E741
							if r < a or l > b:
										return -math.inf
							if l >= a and r <= b:
										return self.st[idx]
							lowerCAmelCase_      =     (l + r) // 2
							lowerCAmelCase_      =     self.query_recursive(self.left(_UpperCamelCase					)    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)
							lowerCAmelCase_      =     self.query_recursive(self.right(_UpperCamelCase					)    ,    mid + 1    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)
							return max(_UpperCamelCase    ,    _UpperCamelCase					)




				def 					__a						( self					)    ->				int:
							lowerCAmelCase_      =     []
							for i in range(1    ,    N + 1					):
										show_list += [self.query(_UpperCamelCase    ,    _UpperCamelCase					)]
							print(_UpperCamelCase					)


if __name__ == "__main__":
			_A       =					[1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
			_A       =					15
			_A       =					SegmentTree(A)
			print(segt.query(4, 6))
			print(segt.query(7, 11))
			print(segt.query(7, 12))
			segt.update(1, 3, 1_11)
			print(segt.query(1, 15))
			segt.update(7, 8, 2_35)
			segt.show_data()



