



"""simple docstring"""

from __future__ import annotations

from collections import defaultdict
from dataclasses import dataclass
@dataclass
class 						lowerCAmelCase__	:


	'''simple docstring'''







	_SCREAMING_SNAKE_CASE  :		int
	_SCREAMING_SNAKE_CASE  :		TreeNode | None     	=   None
	_SCREAMING_SNAKE_CASE  :		TreeNode | None     	=   None




def    __snake_case       (  )    ->					TreeNode:






				'''simple docstring'''
				return TreeNode(3       ,		TreeNode(9    )       ,		TreeNode(20       ,		TreeNode(15    )       ,		TreeNode(7    )    )    )
def    __snake_case       (  __A			:	TreeNode    )    ->					list[int]:






				'''simple docstring'''

				def depth_first_search(
				    __A			:	TreeNode | None       ,		__A			:	int       ,		__A			:	list[int]    ) -> None:
								if not root:
												return

								if depth == len(__A    ):
												right_view.append(root.val    )

								depth_first_search(root.right       ,		depth + 1       ,		__A    )
								depth_first_search(root.left       ,		depth + 1       ,		__A    )

				SCREAMING_SNAKE_CASE	:       list 							=    []
				if not root:
								return right_view

				depth_first_search(__A       ,		0       ,		__A    )
				return right_view
def    __snake_case       (  __A			:	TreeNode    )    ->					list[int]:






				'''simple docstring'''

				def depth_first_search(
				    __A			:	TreeNode | None       ,		__A			:	int       ,		__A			:	list[int]    ) -> None:
								if not root:
												return

								if depth == len(__A    ):
												left_view.append(root.val    )

								depth_first_search(root.left       ,		depth + 1       ,		__A    )
								depth_first_search(root.right       ,		depth + 1       ,		__A    )

				SCREAMING_SNAKE_CASE	:       list 							=    []
				if not root:
								return left_view

				depth_first_search(__A       ,		0       ,		__A    )
				return left_view
def    __snake_case       (  __A			:	TreeNode    )    ->					list[int]:






				'''simple docstring'''

				def breadth_first_search(__A			:	TreeNode       ,		__A			:	list[int]    ) -> None:
								SCREAMING_SNAKE_CASE	:       Union[str, Any] 							=    [(root, 0)]
								SCREAMING_SNAKE_CASE	:       str 							=    defaultdict(__A    )

								while queue:
												SCREAMING_SNAKE_CASE	:       Tuple 							=    queue.pop(0    )
												SCREAMING_SNAKE_CASE	:       Optional[Any] 							=    first

												lookup[hd].append(node.val    )

												if node.left:
																queue.append((node.left, hd - 1)    )
												if node.right:
																queue.append((node.right, hd + 1)    )

								for pair in sorted(lookup.items()       ,		key=lambda __A    : each[0]    ):
												top_view.append(pair[1][0]    )

				SCREAMING_SNAKE_CASE	:       list 							=    []
				if not root:
								return top_view

				breadth_first_search(__A       ,		__A    )
				return top_view
def    __snake_case       (  __A			:	TreeNode    )    ->					list[int]:






				'''simple docstring'''
				from collections import defaultdict

				def breadth_first_search(__A			:	TreeNode       ,		__A			:	list[int]    ) -> None:
								SCREAMING_SNAKE_CASE	:       Tuple 							=    [(root, 0)]
								SCREAMING_SNAKE_CASE	:       str 							=    defaultdict(__A    )

								while queue:
												SCREAMING_SNAKE_CASE	:       Optional[Any] 							=    queue.pop(0    )
												SCREAMING_SNAKE_CASE	:       Optional[int] 							=    first
												lookup[hd].append(node.val    )

												if node.left:
																queue.append((node.left, hd - 1)    )
												if node.right:
																queue.append((node.right, hd + 1)    )

								for pair in sorted(lookup.items()       ,		key=lambda __A    : each[0]    ):
												bottom_view.append(pair[1][-1]    )

				SCREAMING_SNAKE_CASE	:       list 							=    []
				if not root:
								return bottom_view

				breadth_first_search(__A       ,		__A    )
				return bottom_view


if __name__ == "__main__":
							import doctest

							doctest.testmod()










"""simple docstring"""

def    __snake_case       (  __A			:	int = 100    )    ->					int:






				'''simple docstring'''
				SCREAMING_SNAKE_CASE	:       Any 							=    1
				SCREAMING_SNAKE_CASE	:       Optional[int] 							=    0
				for i in range(1       ,		num + 1    ):
								fact *= i

				for j in str(__A    ):
								result += int(__A    )

				return result


if __name__ == "__main__":
							print(solution(int(input('Enter the Number: ').strip())))





