





'''simple docstring'''






from __future__ import annotations

from random import random







class 			lowerCamelCase					:


					def __init__(					self	:  Tuple       ,     __snake_case	:  int | None = None       ):





											'''simple docstring'''





											_snake_case:   Optional[int]  					=		value
											_snake_case:   int  					=		random()
											_snake_case:   Node | None  					=		None
											_snake_case:   Node | None  					=		None


					def __repr__(					self	:  List[Any]       ):





											'''simple docstring'''





											from pprint import pformat

											if self.left is None and self.right is None:
																	return f'''\'{self.value}: {self.prior:.5}\''''
											else:
																	return pformat(
																	    {f'''{self.value}: {self.prior:.5}''': (self.left, self.right)}       ,     indent=1       )




					def __str__(					self	:  str       ):





											'''simple docstring'''





											_snake_case:   Dict  					=		str(self.value       ) + ' '
											_snake_case:   Optional[Any]  					=		str(self.left or ''       )
											_snake_case:   Optional[Any]  					=		str(self.right or ''       )
											return value + left + right





def       lowercase_      (		lowercase__				,  lowercase__						)   ->tuple[Node | None, Node | None]:
						if root is None:  # None tree is split into 2 Nones
												return None, None
						elif root.value is None:
												return None, None
						else:
												if value < root.value:
																		_snake_case					,						_snake_case:   str  					=		split(root.left				,  lowercase__						)
																		return left, root
												else:
																		_snake_case					,						_snake_case:   Any  					=		split(root.right				,  lowercase__						)
																		return root, right





def       lowercase_      (		lowercase__				,  lowercase__						)   ->Node | None:
						if (not left) or (not right):  # If one node is None, return the other
												return left or right
						elif left.prior < right.prior:
												_snake_case:   List[Any]  					=		merge(left.right				,  lowercase__						)
												return left
						else:
												_snake_case:   Any  					=		merge(lowercase__				,  right.left						)
												return right





def       lowercase_      (		lowercase__				,  lowercase__						)   ->Node | None:
						_snake_case:   Optional[Any]  					=		Node(lowercase__						)
						_snake_case					,						_snake_case:   Optional[Any]  					=		split(lowercase__				,  lowercase__						)
						return merge(merge(lowercase__				,  lowercase__						)				,  lowercase__						)





def       lowercase_      (		lowercase__				,  lowercase__						)   ->Node | None:
						_snake_case					,						_snake_case:   Tuple  					=		split(lowercase__				,  value - 1						)
						_snake_case					,						_snake_case:   Dict  					=		split(lowercase__				,  lowercase__						)
						return merge(lowercase__				,  lowercase__						)





def       lowercase_      (		lowercase__						)   ->None:
						if not root:  # None
												return
						else:
												inorder(root.left						)
												print(root.value				,  end=','						)
												inorder(root.right						)





def       lowercase_      (		lowercase__				,  lowercase__						)   ->Node | None:
						for arg in args.split():
												if arg[0] == "+":
																		_snake_case:   Union[str, Any]  					=		insert(lowercase__				,  int(arg[1:]						)						)

												elif arg[0] == "-":
																		_snake_case:   Optional[Any]  					=		erase(lowercase__				,  int(arg[1:]						)						)

												else:
																		print('Unknown command'						)

						return root





def       lowercase_      (		)   ->None:
						_snake_case:   List[str]  					=		None
						print(
						    'enter numbers to create a tree, + value to add value into treap, '
						    '- value to erase all nodes with value. \'q\' to quit. '						)

						_snake_case:   Optional[int]  					=		input()
						while args != "q":
												_snake_case:   str  					=		interact_treap(lowercase__				,  lowercase__						)
												print(lowercase__						)
												_snake_case:   int  					=		input()

						print('good by!'						)


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		main()












'''simple docstring'''






def       lowercase_      (		lowercase__ = 50						)   ->int:
						_snake_case:   Union[str, Any]  					=		[[0] * 3 for _ in range(length + 1						)]

						for row_length in range(length + 1						):
												for tile_length in range(2				,  5						):
																		for tile_start in range(row_length - tile_length + 1						):
																								different_colour_ways_number[row_length][tile_length - 2] += (
																								    different_colour_ways_number[row_length - tile_start - tile_length][
																								        tile_length - 2
																								    ]
																								    + 1
																								)

						return sum(different_colour_ways_number[length]						)


if __name__ == "__main__":
		print(F'{solution() = }')





