

from __future__ import annotations

from collections.abc import Callable
from typing import Any, Generic, TypeVar

lowerCAmelCase__								=		TypeVar("""T""")







class 	lowercase    (				Generic[T]							):


		"""simple docstring"""




		def __init__(				self	,       __snake_case	,       __snake_case):
			_UpperCamelCase   :		Any | T			=						None

			_UpperCamelCase   :		int			=						len(__snake_case)
			_UpperCamelCase   :		list[T]			=						[any_type for _ in range(self.N)] + arr
			_UpperCamelCase   :		List[Any]			=						fnc
			self.build()


		def 		A__					(				self):
			for p in range(self.N - 1	,       0	,       -1):
				_UpperCamelCase   :		List[Any]			=						self.fn(self.st[p * 2]	,       self.st[p * 2 + 1])


		def 		A__					(				self	,       __snake_case	,       __snake_case):
			p += self.N
			_UpperCamelCase   :		Optional[int]			=						v
			while p > 1:
				_UpperCamelCase   :		List[Any]			=						p // 2
				_UpperCamelCase   :		Optional[Any]			=						self.fn(self.st[p * 2]	,       self.st[p * 2 + 1])






		def 		A__					(				self	,       __snake_case	,       __snake_case):  # noqa: E741
			_UpperCamelCase   :		Optional[int]			=						l + self.N, r + self.N

			_UpperCamelCase   :		T | None			=						None
			while l <= r:
				if l % 2 == 1:
					_UpperCamelCase   :		List[Any]			=						self.st[l] if res is None else self.fn(__snake_case	,       self.st[l])
				if r % 2 == 0:
					_UpperCamelCase   :		Any			=						self.st[r] if res is None else self.fn(__snake_case	,       self.st[r])
				_UpperCamelCase   :		Dict			=						(l + 1) // 2, (r - 1) // 2
			return res


if __name__ == "__main__":
							from functools import reduce

							lowerCAmelCase__								=		[1, 1_0, -2, 9, -3, 8, 4, -7, 5, 6, 1_1, -1_2]

							lowerCAmelCase__								=		{
							    0: 7,
							    1: 2,
							    2: 6,
							    3: -1_4,
							    4: 5,
							    5: 4,
							    6: 7,
							    7: -1_0,
							    8: 9,
							    9: 1_0,
							    1_0: 1_2,
							    1_1: 1,
							}

							lowerCAmelCase__								=		SegmentTree(test_array, min)
							lowerCAmelCase__								=		SegmentTree(test_array, max)
							lowerCAmelCase__								=		SegmentTree(test_array, lambda a, b: a + b)






							def 					lowerCamelCase_     (							)						->				None:




								'''simple docstring'''




								for i in range(len(UpperCAmelCase_	)	):
									for j in range(UpperCAmelCase_							,       len(UpperCAmelCase_	)	):
										_UpperCamelCase   :		int			=						reduce(UpperCAmelCase_							,       test_array[i : j + 1]	)
										_UpperCamelCase   :		List[str]			=						reduce(UpperCAmelCase_							,       test_array[i : j + 1]	)
										_UpperCamelCase   :		Optional[int]			=						reduce(lambda UpperCAmelCase_							,       UpperCAmelCase_	: a + b							,       test_array[i : j + 1]	)
										assert min_range == min_segment_tree.query(UpperCAmelCase_							,       UpperCAmelCase_	)
										assert max_range == max_segment_tree.query(UpperCAmelCase_							,       UpperCAmelCase_	)
										assert sum_range == sum_segment_tree.query(UpperCAmelCase_							,       UpperCAmelCase_	)

							test_all_segments()

							for index, value in test_updates.items():
														lowerCAmelCase__								=		value
														min_segment_tree.update(index, value)
														max_segment_tree.update(index, value)
														sum_segment_tree.update(index, value)
														test_all_segments()









def 					lowerCamelCase_     (							UpperCAmelCase_							:     list	)						->				list:




	'''simple docstring'''




	if len(UpperCAmelCase_	) <= 1:
		return [tuple(UpperCAmelCase_	)]

	_UpperCamelCase   :		List[Any]			=						[]

	def generate(UpperCAmelCase_							:     int							,       UpperCAmelCase_							:     list	):
		_UpperCamelCase   :		Optional[int]			=						[0] * n
		res.append(tuple(UpperCAmelCase_	)	)

		_UpperCamelCase   :		List[Any]			=						0
		while i < n:
			if c[i] < i:
				if i % 2 == 0:
					_UpperCamelCase	,		_UpperCamelCase   :		List[str]			=						arr[i], arr[0]
				else:
					_UpperCamelCase	,		_UpperCamelCase   :		List[str]			=						arr[i], arr[c[i]]
				res.append(tuple(UpperCAmelCase_	)	)
				c[i] += 1
				_UpperCamelCase   :		Tuple			=						0
			else:
				_UpperCamelCase   :		Tuple			=						0
				i += 1

	generate(len(UpperCAmelCase_	)							,       UpperCAmelCase_	)
	return res


if __name__ == "__main__":
							lowerCAmelCase__								=		input("""Enter numbers separated by a comma:\n""").strip()
							lowerCAmelCase__								=		[int(item) for item in user_input.split(""",""")]
							print(heaps(arr))




