Ternary Trees

Yesterday at school, Jas invented a new game. He drew one large circle at the top of a sheet of paper. Beneath it he drew three smaller circles and joined each of them to the top circle. He then repeated this for every new circle: for each circle he drew three fresh circles below it and connected them to it. After $k$ levels in total, he obtained a complete ternary tree with $(3^k-1)/2$ circles, whose bottom level holds exactly $3^{k-1}$ circles.

The game works like this. Each student fills the bottom row with values that are either $0$ or $1$, one per circle. Every circle on a higher level is then given the value that appears at least twice among its three children (the three circles directly below it) — that is, the majority of its three children.

Once a student has filled the whole tree, the guessing phase begins. Jas repeatedly names a number from $1$ to $3^{k-1}$, identifying one bottom circle, and the student tells him the value written there. Jas wins if he can announce the value in the topmost (largest) circle before every bottom circle has been revealed to him.

Jas claims he has a questioning strategy that always lets him win. You doubt it. To prove that no such strategy exists, you want a program that, given Jas's strategy, produces an assignment of $0$/$1$ values to the bottom circles for which Jas is forced to ask about every bottom circle before he can determine the value of the top circle.

Jas is not naive: if his strategy tells him to ask about circle $x$ but that circle's value is irrelevant — because he already knows the value of one of $x$'s ancestors in the tree — he skips the question. Your assignment must leave him no such shortcut: at the moment he is about to ask about each circle, none of that circle's ancestors may yet be determined.

The first line contains an integer $k$ ($1 \le k \le 12$), the number of levels.

The second line contains a permutation of all integers from $1$ to $3^{k-1}$, giving the order in which Jas asks about the bottom circles.

Jas's questioning order is fixed and known in advance, so many different assignments would force him to ask about every circle. To make the answer unique, output the following canonical forcing assignment.

Define the reveal time of a bottom circle as its position (0-based) in Jas's question order, and the reveal time of any higher circle as the maximum reveal time among the bottom circles in its subtree. Assign the top circle the value $0$. Then, going from the top down, for every non-bottom circle whose assigned value is $v$, look at its three children in increasing order of reveal time and give the earliest-revealed child the value $0$, the middle child the value $1$, and the latest-revealed child the value $v$. This fixes the value of every bottom circle.

Output the $3^{k-1}$ bottom-circle values in the order Jas asks about them, separated by single spaces.