





"""simple docstring"""




import math





def 		UpperCAmelCase__						(	_UpperCAmelCase   ):






  """simple docstring"""





  return sum(int(_UpperCAmelCase   ) for digit in str(_UpperCAmelCase   )   )





def 		UpperCAmelCase__						(	_UpperCAmelCase = 30   ):






  """simple docstring"""





  A_    :			int									=    []
  for digit in range(2					,   100   ):
    for power in range(2					,   100   ):
      A_    :			Any									=    int(math.pow(_UpperCAmelCase					,   _UpperCAmelCase   )   )
      if digit == digit_sum(_UpperCAmelCase   ):
        digit_to_powers.append(_UpperCAmelCase   )

  digit_to_powers.sort()
  return digit_to_powers[n - 1]


if __name__ == "__main__":
   print(solution())






import math





class   lowercase__     :







  def __init__(						self     ,    _lowercase    ):
       lowerCAmelCase_       :							Optional[Any]			 =		len(_lowercase    )
       lowerCAmelCase_       :							Union[str, Any]			 =		[0] * (
           4 * self.N
       )  # approximate the overall size of segment tree with array N
       self.build(1     ,    0     ,    self.N - 1    )







  def 						UpperCAmelCase__		(						self     ,    _lowercase    ):
       return idx * 2







  def 						UpperCAmelCase__		(						self     ,    _lowercase    ):
       return idx * 2 + 1







  def 						UpperCAmelCase__		(						self     ,    _lowercase     ,    _lowercase     ,    _lowercase    ):  # noqa: E741
       if l == r:
            lowerCAmelCase_       :							Dict			 =		A[l]
       else:
            lowerCAmelCase_       :							List[str]			 =		(l + r) // 2
            self.build(self.left(_lowercase    )     ,    _lowercase     ,    _lowercase    )
            self.build(self.right(_lowercase    )     ,    mid + 1     ,    _lowercase    )
            lowerCAmelCase_       :							Dict			 =		max(self.st[self.left(_lowercase    )]     ,    self.st[self.right(_lowercase    )]    )







  def 						UpperCAmelCase__		(						self     ,    _lowercase     ,    _lowercase     ,    _lowercase    ):
       return self.update_recursive(1     ,    0     ,    self.N - 1     ,    a - 1     ,    b - 1     ,    _lowercase    )







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







  def 						UpperCAmelCase__		(						self     ,    _lowercase     ,    _lowercase    ):
       return self.query_recursive(1     ,    0     ,    self.N - 1     ,    a - 1     ,    b - 1    )







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







  def 						UpperCAmelCase__		(						self    ):
       lowerCAmelCase_       :							List[Any]			 =		[]
       for i in range(1     ,    N + 1    ):
            show_list += [self.query(_lowercase     ,    _lowercase    )]
       print(_lowercase    )


if __name__ == "__main__":
      UpperCAmelCase_       : Any							=    [1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
      UpperCAmelCase_       : Optional[Any]							=    15
      UpperCAmelCase_       : List[Any]							=    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()
