Boolean Logic

A proposition is a logical formula built from proposition symbols and connective operators. Propositions are defined recursively by the following rules.

1. Every proposition symbol (here, a single lower-case letter, for example a or z) is a proposition.
2. If $P$ is a proposition, then (!$P$) is a proposition, and $P$ is a direct subformula of it.
3. If $P$ and $Q$ are propositions, then ($P$&$Q$), ($P$|$Q$), ($P$-->$Q$), and ($P$<->$Q$) are propositions, and $P$ and $Q$ are direct subformulas of each of them.
4. Nothing else is a proposition.

The operators !, &, |, -->, and <-> denote negation, conjunction, disjunction, implication, and equivalence, respectively. A proposition $P$ is a subformula of a proposition $R$ if $P = R$, or if $P$ is a direct subformula of some proposition $Q$ and $Q$ is a subformula of $R$.

Now take a proposition $P$ and assign a boolean value ($0$ or $1$) to every proposition symbol that occurs in $P$. This induces a boolean value for every subformula of $P$ according to the standard semantics of the operators:

In this way a value for $P$ is obtained. This value depends on the chosen assignment. If $P$ contains $n$ distinct proposition symbols, there are $2^n$ different assignments. To examine all of them we use a truth table.

A truth table has one line per assignment (that is, $2^n$ lines in total). Each line lists the values of all subformulas under the corresponding assignment. When a subformula is a proposition symbol, its value is aligned with that symbol; otherwise its value is aligned with the center of the operator.

The input contains several test cases, one per line. Each line denotes a proposition and may contain any number of spaces between its characters. The input ends immediately after the newline that follows the last test case.

For each test case, produce a truth table for the given proposition. Begin the truth table by repeating the input line exactly. Then evaluate the proposition and all of its subformulas for every assignment of boolean values to its symbols, and output one line per assignment. Each such line must have the same length as the corresponding input line and may contain only spaces and the characters 0 and 1, with every subformula's value placed in the column described above. Output an empty line after each test case.

Let $s_1, \ldots, s_n$ be the proposition symbols of the given proposition sorted in alphabetical order. Then every assignment that gives $0$ to $s_1$ must come before every assignment that gives $1$ to $s_1$. Within each of those blocks, every assignment that gives $0$ to $s_2$ must come before every assignment that gives $1$ to $s_2$, and so on (so $s_n$ changes fastest).