S-Trees |

A Strange Tree (S-tree) over the variable set
is a binary tree representing a Boolean function
.
Each path of the S-tree begins at the *root* node and consists of *n*+1 nodes. Each of the S-tree's nodes has a *depth*, which is the amount of nodes between itself and the root (so the root has depth 0). The nodes with depth less than *n* are called *non-terminal* nodes. All non-terminal nodes have two children: the *right child* and the *left child*. Each non-terminal node is marked with some variable *x*_{i} from the variable set *X*_{n}. All non-terminal nodes with the same depth are marked with the same variable, and non-terminal nodes with different depth are marked with different variables. So, there is a unique variable *x*_{i1} corresponding to the root, a unique variable *x*_{i2} corresponding to the nodes with depth 1, and
so on. The sequence of the variables
is called the *variable ordering*. The nodes having depth *n* are called *terminal* nodes. They have no children and are marked with either 0 or 1. Note that the variable ordering and the distribution of 0's and 1's on terminal nodes are sufficient to completely describe an S-tree.

As stated earlier, each S-tree represents a Boolean function *f*. If you have an S-tree and values for the variables
,
then it is quite simple to find out what
is: start with the root. Now repeat the following: if the node you are at is labelled with a variable
*x*_{i}, then depending on whether the value of the variable is 1 or 0, you go its right or left child, respectively. Once you reach a terminal node, its label gives the value of the function.

Figure 1: S-trees for the function

On the picture, two S-trees representing the same Boolean function,
,
are shown. For the left tree, the variable ordering is
*x*_{1}, *x*_{2}, *x*_{3}, and for the right tree it is
*x*_{3}, *x*_{1}, *x*_{2}.

The values of the variables
,
are given as a *Variable Values Assignment* (VVA)

with . For instance, (

Your task is to write a program which takes an S-tree and some VVAs and computes as described above.

`x3 x1 x2`

In the next line the distribution of 0's and 1's over the terminal nodes is given. There will be exactly 2^{n} characters (each of which can be 0 or 1), followed by the new-line character.
The characters are given in the order in which they appear in the S-tree, the first character corresponds to the leftmost terminal node of the S-tree, the last one to its rightmost terminal node.

The next line contains a single integer *m*, the number of VVAs, followed by *m* lines describing them. Each of the *m* lines contains exactly *n* characters (each of which can be 0 or 1), followed by a new-line character. Regardless of the variable ordering of the S-tree, the first character always describes the value of *x*_{1}, the second character describes the value of *x*_{2}, and so on. So, the line

`110`

corresponds to the VVA (
*x*_{1} = 1, *x*_{2} = 1, *x*_{3} = 0).

The input is terminated by a test case starting with *n* = 0. This test case should not be processed.

Output a blank line after each test case.

3 x1 x2 x3 00000111 4 000 010 111 110 3 x3 x1 x2 00010011 4 000 010 111 110 0

S-Tree #1: 0011 S-Tree #2: 0011