Jogurt P98569

Un arbol binario completo de $N$ niveles es una estructura jerárquica de nodos, donde hay un nodo (el nodo raíz) que está en nivel 0 y que tiene exactamente dos nodos hijo, que están en nivel 1, y que a su vez cada uno de ellos tiene 2 nodos hijos, que están en nivel 2, etcétera, hasta llegar a un cierto nivel $N$, donde ningún nodo tiene nodos hijo.

Un arbol binario completo de $N$ niveles tiene exactamente $2^N-1$ nodos. En este problema te pedimos que escribas los números del $1$ al $2^N-1$ en los nodos de un árbol binario completo de $N$ niveles, de modo que se cumpla la siguiente propiedad: para cada nodo de nivel $D$, el valor absoluto de la diferencia entre la suma de los números del subárbol izquierdo y la suma de los números del subárbol derecho es $2^D$.

Por ejemplo: para $D=0$, se debe cumplir que la suma del subárbol izquierdo del nodo raíz y la suma del subárbol derecho del nodo raíz tienen que diferir en exactamente $2^0=1$. Para $D=1$, los respectivos subárboles deben diferir en $2^1=2$.

Hay que usar cada número exactamente una vez. La solución no tiene porque ser única.

Entrada

La primera y única línea de la entrada contiene el entero $N$ ($1\le N\le 15$).

Salida

Escribe los $2^N-1$ números separados por espacios en una única línea, en pre-orden: para escribir los números en pre-orden, debes escribir primero el número del nodo raíz, luego el subárbol de la izquierda (de nuevo, en pre-orden) y luego el subárbol de la derecha.