本题没有可用的提交语言。

描述

每个计算机科学专业的学生都了解二叉树。以下是二叉树的众多定义之一。二叉树是归纳定义的。二叉树t可以是一个外部节点（叶子）○，也可以是一个有序对$t = (t_1, t_2)$，表示一个内部节点●，并附有两个子树，左子树$t_1$和右子树$t_2$。根据这个定义，任何二叉树的节点数都是奇数。给定一个奇数$n$，用$B(n)$表示所有具有$n$个节点（包括内部节点和外部节点）的二叉树的集合。例如，$B(1)$仅包含一个树○，$B(3) = \{(○,○)\}$，而$B(5) = \{(○, (○,○)), ((○,○), ○)\}$。$B(5)$中的树如下图所示。

用$|t|$表示树$t$的节点数。给定树$t$，我们定义其唯一的整数标识符$N(t)$如下：

$N(○) = 0$

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

例如，$N(○,○) = 2^2 + 2^1 \cdot 0 + 0 = 4$，$N(○, (○,○)) = 2^4 + 2^3 \cdot 0 + 4 = 20$，

$N((○,○), ○) = 2^4 + 2^1 \cdot 4 + 0 = 24$。

考虑以下对所有二叉树的线性序：

1. $○ \leq t$

2. $(t_1, t_2) \leq (u_1, u_2)$，当$t_1 < u_1$，或$t_1 = u_1$且$t_2 \leq u_2$

在这个序中，单个叶子是最小的树，而对于两个非叶子树，较小的树是左子树较小的那个（如果左子树不同），否则是右子树较小的那个。例如，$(○, (○,○)) < ((○,○), ○)$，因为$○ < (○,○)$。假设现在使用关系$\leq$对$B(n)$中的树进行排序。然后，对于$B(n)$中的每个树$t$，我们定义$t$的后继为$B(n)$中紧接在$t$之后的树。如果$t$是$B(n)$中最大的树，则$t$的后继是$B(n)$集合中最小的树。例如，$B(3)$中$(○,○)$的后继是同一个树$(○,○)$，而$B(5)$中$(○, (○,○))$的后继是$((○,○), ○)$。给定某个树$t$的整数标识符，你能给出$B(|t|)$中$t$的后继的标识符吗？

任务

编写一个程序，完成以下任务：

• 读取某个二叉树的标识符，
• 计算$B(|t|)$中$t$的后继的标识符，
• 输出结果。

输入
输入的第一行也是唯一一行包含一个整数$n$（$0 \leq n \leq 2^{30}$）——某个二叉树的标识符。

输出
输出的第一行也是唯一一行应包含一个整数$s$——$B(|t|)$中$t$的后继的标识符。

输入样例1

20

输出样例1

24

来源

中欧 2003