
'''simple docstring'''





from __future__ import annotations

import math


class        UpperCamelCase__     :






 def __init__(	self     :Union[str, Any]		, _A     :int	) ->	List[Any]:







       '''simple docstring'''



       __A						=	size
       # approximate the overall size of segment tree with given value
       __A						=	[0 for i in range(0		, 4 * size	)]
       # create array to store lazy update
       __A						=	[0 for i in range(0		, 4 * size	)]
       __A						=	[0 for i in range(0		, 4 * size	)]  # flag for lazy update






 def 		lowercase_  (	self     :Optional[Any]		, _A     :int	) ->	str:







       '''simple docstring'''



       return idx * 2






 def 		lowercase_  (	self     :Any		, _A     :int	) ->	int:







       '''simple docstring'''



       return idx * 2 + 1






 def 		lowercase_  (	self     :Tuple		, _A     :int		, _A     :int		, _A     :int		, _A     :list[int]	) ->	Dict:







       '''simple docstring'''



       if left_element == right_element:
             __A						=	a[left_element - 1]
       else:
             __A						=	(left_element + right_element) // 2
             self.build(self.left(UpperCamelCase__	)		, UpperCamelCase__		, UpperCamelCase__		, UpperCamelCase__	)
             self.build(self.right(UpperCamelCase__	)		, mid + 1		, UpperCamelCase__		, UpperCamelCase__	)
             __A						=	max(
                 self.segment_tree[self.left(UpperCamelCase__	)]		, self.segment_tree[self.right(UpperCamelCase__	)]	)






 def 		lowercase_  (	self     :List[Any]		, _A     :int		, _A     :int		, _A     :int		, _A     :int		, _A     :int		, _A     :int	) ->	int:







       '''simple docstring'''



       if self.flag[idx] is True:
             __A						=	self.lazy[idx]
             __A						=	False
             if left_element != right_element:
                   __A						=	self.lazy[idx]
                   __A						=	self.lazy[idx]
                   __A						=	True
                   __A						=	True

       if right_element < a or left_element > b:
             return True
       if left_element >= a and right_element <= b:
             __A						=	val
             if left_element != right_element:
                   __A						=	val
                   __A						=	val
                   __A						=	True
                   __A						=	True
             return True
       __A						=	(left_element + right_element) // 2
       self.update(self.left(UpperCamelCase__	)		, UpperCamelCase__		, UpperCamelCase__		, UpperCamelCase__		, UpperCamelCase__		, UpperCamelCase__	)
       self.update(self.right(UpperCamelCase__	)		, mid + 1		, UpperCamelCase__		, UpperCamelCase__		, UpperCamelCase__		, UpperCamelCase__	)
       __A						=	max(
           self.segment_tree[self.left(UpperCamelCase__	)]		, self.segment_tree[self.right(UpperCamelCase__	)]	)
       return True






 def 		lowercase_  (	self     :int		, _A     :int		, _A     :int		, _A     :int		, _A     :int		, _A     :int	) ->	List[str]:







       '''simple docstring'''



       if self.flag[idx] is True:
             __A						=	self.lazy[idx]
             __A						=	False
             if left_element != right_element:
                   __A						=	self.lazy[idx]
                   __A						=	self.lazy[idx]
                   __A						=	True
                   __A						=	True
       if right_element < a or left_element > b:
             return -math.inf
       if left_element >= a and right_element <= b:
             return self.segment_tree[idx]
       __A						=	(left_element + right_element) // 2
       __A						=	self.query(self.left(UpperCamelCase__	)		, UpperCamelCase__		, UpperCamelCase__		, UpperCamelCase__		, UpperCamelCase__	)
       __A						=	self.query(self.right(UpperCamelCase__	)		, mid + 1		, UpperCamelCase__		, UpperCamelCase__		, UpperCamelCase__	)
       return max(UpperCamelCase__		, UpperCamelCase__	)






 def __str__(	self     :List[Any]	) ->	Optional[Any]:







       '''simple docstring'''



       return str([self.query(1		, 1		, self.size		, UpperCamelCase__		, UpperCamelCase__	) for i in range(1		, self.size + 1	)]	)


if __name__ == "__main__":
 a__						:      int   				=				[1, 2, -4, 7, 3, -5, 6, 1_1, -2_0, 9, 1_4, 1_5, 5, 2, -8]
 a__						:      str   				=				1_5
 a__						:      List[str]   				=				SegmentTree(size)
 segt.build(1, 1, size, A)
 print(segt.query(1, 1, size, 4, 6))
 print(segt.query(1, 1, size, 7, 1_1))
 print(segt.query(1, 1, size, 7, 1_2))
 segt.update(1, 1, size, 1, 3, 1_1_1)
 print(segt.query(1, 1, size, 1, 1_5))
 segt.update(1, 1, size, 7, 8, 2_3_5)
 print(segt)







import itertools
import string
from collections.abc import Generator, Iterable
def       A	(    _lowercase		,  _lowercase						):
						SCREAMING_SNAKE_CASE							:    Union[str, Any]							=							iter(_lowercase						)
						while True:
												SCREAMING_SNAKE_CASE							:    Optional[Any]							=							tuple(itertools.islice(_lowercase		,  _lowercase						)						)
												if not chunk:
																		return
												yield chunk
def       A	(    _lowercase						):
						SCREAMING_SNAKE_CASE							:    int							=							''''''.join([c.upper() for c in dirty if c in string.ascii_letters]						)
						SCREAMING_SNAKE_CASE							:    List[str]							=							''''''

						if len(_lowercase						) < 2:
												return dirty

						for i in range(len(_lowercase						) - 1						):
												clean += dirty[i]

												if dirty[i] == dirty[i + 1]:
																		clean += "X"

						clean += dirty[-1]

						if len(_lowercase						) & 1:
												clean += "X"

						return clean
def       A	(    _lowercase						):
						# I and J are used interchangeably to allow
						# us to use a 5x5 table (25 letters)
						SCREAMING_SNAKE_CASE							:    Optional[Any]							=							'''ABCDEFGHIKLMNOPQRSTUVWXYZ'''
						# we're using a list instead of a '2d' array because it makes the math
						# for setting up the table and doing the actual encoding/decoding simpler
						SCREAMING_SNAKE_CASE							:    List[Any]							=							[]

						# copy key chars into the table if they are in `alphabet` ignoring duplicates
						for char in key.upper():
												if char not in table and char in alphabet:
																		table.append(_lowercase						)

    # fill the rest of the table in with the remaining alphabet chars
						for char in alphabet:
												if char not in table:
																		table.append(_lowercase						)

						return table
def       A	(    _lowercase		,  _lowercase						):
						SCREAMING_SNAKE_CASE							:    Any							=							generate_table(_lowercase						)
						SCREAMING_SNAKE_CASE							:    Any							=							prepare_input(_lowercase						)
						SCREAMING_SNAKE_CASE							:    Union[str, Any]							=							''''''

						# https://en.wikipedia.org/wiki/Playfair_cipher#Description
						for chara, chara in chunker(_lowercase		,  2						):
												SCREAMING_SNAKE_CASE				,  SCREAMING_SNAKE_CASE							:    int							=							divmod(table.index(_lowercase						)		,  5						)
												SCREAMING_SNAKE_CASE				,  SCREAMING_SNAKE_CASE							:    Union[str, Any]							=							divmod(table.index(_lowercase						)		,  5						)

												if rowa == rowa:
																		ciphertext += table[rowa * 5 + (cola + 1) % 5]
																		ciphertext += table[rowa * 5 + (cola + 1) % 5]
												elif cola == cola:
																		ciphertext += table[((rowa + 1) % 5) * 5 + cola]
																		ciphertext += table[((rowa + 1) % 5) * 5 + cola]
												else:  # rectangle
																		ciphertext += table[rowa * 5 + cola]
																		ciphertext += table[rowa * 5 + cola]

						return ciphertext



def       A	(    _lowercase		,  _lowercase						):
						SCREAMING_SNAKE_CASE							:    Any							=							generate_table(_lowercase						)
						SCREAMING_SNAKE_CASE							:    List[Any]							=							''''''

						# https://en.wikipedia.org/wiki/Playfair_cipher#Description
						for chara, chara in chunker(_lowercase		,  2						):
												SCREAMING_SNAKE_CASE				,  SCREAMING_SNAKE_CASE							:    List[str]							=							divmod(table.index(_lowercase						)		,  5						)
												SCREAMING_SNAKE_CASE				,  SCREAMING_SNAKE_CASE							:    Optional[Any]							=							divmod(table.index(_lowercase						)		,  5						)

												if rowa == rowa:
																		plaintext += table[rowa * 5 + (cola - 1) % 5]
																		plaintext += table[rowa * 5 + (cola - 1) % 5]
												elif cola == cola:
																		plaintext += table[((rowa - 1) % 5) * 5 + cola]
																		plaintext += table[((rowa - 1) % 5) * 5 + cola]
												else:  # rectangle
																		plaintext += table[rowa * 5 + cola]
																		plaintext += table[rowa * 5 + cola]

						return plaintext





