一个满二叉树由按层次结构排列的节点组成。其中一个节点是根节点，称为第 $0$ 层。根节点有两个子节点，位于第 $1$ 层。这些子节点中的每一个在第 $2$ 层都有两个子节点，依此类推。

通常，一个有 $N$ 层的满二叉树有 $2^N-1$ 个节点，除了第 $N-1$ 层的节点外，每个节点都有两个子节点。

每个节点中都可以写入一个数字。将数字 $1$ 到 $2^N-1$ 写入一个有 $N$ 层的满二叉树中，使得对于每个位于第 $D$ 层的节点，其左子树中所有数字之和与右子树中所有数字之和的差的绝对值恰好为 $2^D$。

例如，根节点的左子树之和与右子树之和的差必须为 $1$。第 $1$ 层节点的左子树之和与右子树之和的差必须为 $2$。

每个数字必须恰好使用一次。解可能不唯一。

输入格式

输入的第一行也是唯一的一行包含一个整数 $N$ ($1 \le N \le 15$)，表示树的层数。

输出格式

在单行中输出由空格隔开的 $2^N-1$ 个整数，表示该二叉树的前序遍历。前序遍历首先输出根节点中的数字，然后输出左子树（同样采用前序遍历），最后输出右子树。

样例

输入样例 1

2

输出样例 1

3 1 2

输入样例 2

3

输出样例 2

3 1 7 5 6 2 4