3457번 - Which is Next 다국어

문제

Every computer science student knows binary trees. Here is one of many possible definitions of binary trees. Binary trees are defined inductively. A binary tree t is either an external node (leaf) ○しろまる or an ordered pair t = (t₁, t₂) representing an internal node ●くろまる with two subtrees attached, left subtree t₁ and right subtree t₂. Under this definition the number of nodes in any binary tree is odd. Given an odd integer n let B(n) denote the set of all binary trees with n nodes, both internal and external. For instance B(1) consists of only one tree ○しろまる, B(3) = {(○しろまる,○しろまる)} and B(5) = {(○しろまる, (○しろまる,○しろまる)), ((○しろまる,○しろまる),○しろまる)}. The trees of B(5) are depicted in the figure below.

Denote by |t| the number of nodes in a tree t. Given a tree t we define its unique integer identifier N(t) as follows:

• N(○しろまる) = 0
• N(t₁, t₂) = 2^{|t₁|+|t₂|} + 2^|t₂| · N(t₁) + N(t₂)

For instance, N (○しろまる,○しろまる) = 2² + 2¹ · 0 + 0 = 4, N (○しろまる,(○しろまる,○しろまる)) = 2⁴ + 2³ · 0 + 4 = 20, N ((○しろまる,○しろまる),○しろまる) = 2⁴ + 2¹ · 4 + 0 = 24.

Consider the following linear order on all binary trees:

• ○しろまる ⪯ t
• (t₁, t₂) ⪯ (u₁, u₂) when t₁ ≺ u₁, or t₁ = u₁ and t₂ ⪯ u₂

In this order a single leaf is the smallest tree and given two nonleaf trees, the smaller one is that with the smaller left tree, if the left subtrees are different, and that with the smaller right subtree, otherwise. Hence for instance (○しろまる,(○しろまる,○しろまる)) ≺ ((○しろまる,○しろまる),○しろまる), since we have ○しろまる ≺ (○しろまる,○しろまる). Assume now that the trees in B(n) were sorted using the relation ⪯. Then, for each tree t in B(n) we define the successor of t as the tree that immediately follows t in B(n). If t is the largest one in B(n) then the successor of t is the smallest tree in set B(n). For instance, the successor of (○しろまる,○しろまる) in B(3) is the same tree (○しろまる,○しろまる) and the successor of (○しろまる,(○しろまる,○しろまる)) in B(5) is ((○しろまる,○しろまる),○しろまる).

Given the integer identifier of some tree t can you give the identifier of the successor of t in B(|t|)?

Write a program that:

• reads the identifier of some binary tree t,
• computes the identifier of the successor of t in B(|t|),
• writes the result.

입력

The first and only line of the input contains one integer n (0 ≤ n ≤ 2³⁰) - the identifier of some binary tree

출력

The first and only line of the output should contain one integer s - the identifier of the successor of t in B(|t|).

제한

힌트