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⁰=1. Para D=1, los respectivos subárboles deben diferir en 2¹=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≤ N≤ 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.