Which is Next

Every computer science student is familiar with binary trees. Here is one of the many possible definitions. Binary trees are defined inductively. A binary tree $t$ is either an external node (a leaf) $\circ$, or an ordered pair $t = (t_1, t_2)$ representing an internal node $\bullet$ with a left subtree $t_1$ and a right subtree $t_2$. Under this definition, the number of nodes in any binary tree is always odd.

For an odd integer $n$, let $B(n)$ denote the set of all binary trees with exactly $n$ nodes (internal and external nodes combined). For example, $B(1)$ contains only the single tree $\circ$, $B(3) = {(\circ,\circ)}$, and $B(5) = {(\circ,(\circ,\circ)),\ ((\circ,\circ),\circ)}$. The two trees of $B(5)$ are shown in the figure below.

Let $|t|$ denote the number of nodes in a tree $t$. To every tree $t$ we assign a unique integer identifier $N(t)$ defined by:

• $N(\circ) = 0$
• $N(t_1, t_2) = 2^{|t_1| + |t_2|} + 2^{|t_2|} \cdot N(t_1) + N(t_2)$

For example, $N(\circ, \circ) = 2^{2} + 2^{1} \cdot 0 + 0 = 4$, $N(\circ, (\circ,\circ)) = 2^{4} + 2^{3} \cdot 0 + 4 = 20$, and $N((\circ,\circ), \circ) = 2^{4} + 2^{1} \cdot 4 + 0 = 24$.

Consider the following linear order on all binary trees:

• $\circ \preceq t$ for every tree $t$
• $(t_1, t_2) \preceq (u_1, u_2)$ when $t_1 \prec u_1$, or when $t_1 = u_1$ and $t_2 \preceq u_2$

Under this order a single leaf is the smallest tree. For two non-leaf trees, the smaller one is the tree with the smaller left subtree; if the left subtrees are equal, it is the tree with the smaller right subtree. Thus, for instance, $(\circ,(\circ,\circ)) \prec ((\circ,\circ),\circ)$, because $\circ \prec (\circ,\circ)$.

Now suppose the trees of $B(n)$ are sorted according to $\preceq$. For each tree $t$ in $B(n)$, the successor of $t$ is the tree that immediately follows $t$ in this sorted order. If $t$ is the largest tree in $B(n)$, then its successor is defined to be the smallest tree in $B(n)$. For example, the successor of $(\circ,\circ)$ in $B(3)$ is $(\circ,\circ)$ itself, and the successor of $(\circ,(\circ,\circ))$ in $B(5)$ is $((\circ,\circ),\circ)$.

Given the identifier of a tree $t$, compute the identifier of the successor of $t$ in $B(|t|)$.

Write a program that:

• reads the identifier of a binary tree $t$,
• computes the identifier of the successor of $t$ in $B(|t|)$,
• writes that identifier.

The only line of input contains one integer $n$ ($0 \le n \le 2^{30}$), the identifier of some binary tree $t$. It is guaranteed to be a valid tree identifier.

Print one integer $s$: the identifier of the successor of $t$ in $B(|t|)$.