描述

在变量集合 $X_n = \{x_1, x_2, \ldots, x_n\}$ 上的一棵奇特树（S 树）是一棵表示布尔函数 $f: \{0, 1\} \to \{0, 1\}$ 的二叉树。S 树的每条路径都从根节点开始，由 $n + 1$ 个节点组成。S 树的每个节点都有一个深度，深度是指该节点与根节点之间的节点数量（所以根节点的深度为 0）。深度小于 $n$ 的节点被称为非终端节点。所有非终端节点都有两个子节点：右子节点和左子节点。每个非终端节点都用变量集合 $X_n$ 中的某个变量 $x_i$ 进行标记。所有深度相同的非终端节点都用同一个变量标记，而深度不同的非终端节点则用不同的变量标记。因此，存在一个与根节点对应的唯一变量 $x_{i1}$，一个与深度为 1 的节点对应的唯一变量 $x_{i2}$，以此类推。变量 $x_{i1}, x_{i2}, \ldots, x_{in}$ 的序列被称为变量排序。深度为 $n$ 的节点被称为终端节点。它们没有子节点，并且标记为 0 或 1。请注意，变量排序以及终端节点上 0 和 1 的分布足以完整地描述一棵 S 树。

如前所述，每棵 S 树都表示一个布尔函数 $f$。如果你有一棵 S 树以及变量 $x_1, x_2, \ldots, x_n$ 的值，那么找出 $f(x_1, x_2, \ldots, x_n)$ 的值是相当简单的：从根节点开始。然后重复以下操作：如果你所在的节点标记有变量 $x_i$，那么根据该变量的值是 1 还是 0，你分别走向它的右子节点或左子节点。一旦你到达一个终端节点，其标记值就是函数的值。

图 1：表示 $x_1$ 和 $(x_2 \text{ 或 } x_3)$ 函数的 S 树

在图中，展示了两棵表示相同布尔函数 $f(x_1, x_2, x_3) = x_1 \text{ 且 } (x_2 \text{ 或 } x_3)$ 的 S 树。对于左边的树，变量排序是 $x_1, x_2, x_3$，而对于右边的树，变量排序是 $x_3, x_1, x_2$。

变量 $x_1, x_2, \ldots, x_n$ 的值由一个变量值赋值（VVA）给出：

$(x_1 = b_1, x_2 = b_2, \ldots, x_n = b_n)$ 其中 $b_1, b_2, \ldots, b_n$ 取值于 $\{0, 1\}$。例如，对于 $n = 3$，$( x_1 = 1, x_2 = 1, x_3 = 0)$ 是一个有效的 VVA，对于上述示例函数，结果为 $f(1, 1, 0) = 1 \text{ 且 } (1 \text{ 或 } 0) = 1$。相应的路径在图中以粗体显示。

你的任务是编写一个程序，该程序接受一棵 S 树和一些 VVA，并按照上述描述计算 $f(x_1, x_2, \ldots, x_n)$ 的值。

输入

输入包含几棵 S 树及其相关 VVA 的描述，你需要对这些内容进行处理。每个描述都以包含单个整数 $n$（$1 \leq n \leq 7$）的一行开始，$n$ 是 S 树的深度。接下来一行描述 S 树的变量排序。该行的格式为 $x_{i1} x_{i2} \ldots x_{in}$。（将恰好有 $n$ 个不同的以空格分隔的字符串）。因此，对于 $n = 3$ 且变量排序为 $x_3, x_1, x_2$ 的情况，这一行将如下所示： $x_3 x_1 x_2$

在下一行中，给出终端节点上 0 和 1 的分布。将恰好有 $2^n$ 个字符（每个字符可以是 0 或 1），后面跟着换行符。这些字符按照它们在 S 树中出现的顺序给出，第一个字符对应 S 树最左边的终端节点，最后一个字符对应最右边的终端节点。

接下来一行包含单个整数 $m$，即 VVA 的数量，后面跟着 $m$ 行对它们的描述。这 $m$ 行中的每一行都恰好包含 $n$ 个字符（每个字符可以是 0 或 1），后面跟着换行符。无论 S 树的变量排序如何，第一个字符始终描述 $x_1$ 的值，第二个字符描述 $x_2$ 的值，以此类推。因此，这一行： $110$ 对应 VVA $( x_1 = 1, x_2 = 1, x_3 = 0)$。

输入以一个 $n = 0$ 开头的测试用例结束。这个测试用例不应被处理。

输出

对于每棵 S 树，输出一行 “S-Tree #j:”，其中 $j$ 是 S 树的编号。然后打印一行，其中包含对于给定的 $m$ 个 VVA 中每个 VVA 的 $f(x_1, x_2, \ldots, x_n)$ 的值，其中 $f$ 是由 S 树定义的函数。

在每个测试用例之后输出一个空行。

输入示例

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

来源

1999 年中欧中部地区竞赛