S-트리

변수 집합 $X_n = \{x_1, x_2, \ldots, x_n\}$ 위에서 정의된 S-트리(Strange tree)는 불리언 함수 $f : \{0,1\}^n \to \{0,1\}$ 를 나타내는 이진 트리이다.

S-트리의 모든 경로는 루트에서 시작하며 $n+1$ 개의 노드로 이루어진다. 어떤 노드의 깊이는 그 노드와 루트 사이의 간선 개수이다(따라서 루트의 깊이는 $0$).

• 깊이가 $n$ 보다 작은 노드를 비단말 노드라고 한다. 모든 비단말 노드는 왼쪽 자식과 오른쪽 자식, 정확히 두 개의 자식을 가진다. 각 비단말 노드에는 $X_n$ 의 변수 하나가 표시된다. 같은 깊이의 비단말 노드는 모두 같은 변수로 표시되고, 서로 다른 깊이의 노드는 서로 다른 변수로 표시된다. 그래서 루트(깊이 $0$)에는 변수 $x_{i_1}$, 깊이 $1$ 의 노드에는 $x_{i_2}$, 이런 식으로 대응된다. 수열 $x_{i_1}, x_{i_2}, \ldots, x_{i_n}$ 을 변수 순서라고 부른다.
• 깊이가 $n$ 인 노드를 단말 노드라고 한다. 단말 노드는 자식이 없으며 $0$ 또는 $1$ 로 표시된다.

변수 순서와 단말 노드에 적힌 $0$/$1$ 분포만으로 S-트리를 완전히 기술할 수 있다.

$f(x_1, \ldots, x_n)$ 의 값을 구하려면 루트에서 시작해 다음을 반복한다. 현재 노드가 변수 $x_i$ 로 표시되어 있으면, $x_i = 1$ 이면 오른쪽 자식으로, $x_i = 0$ 이면 왼쪽 자식으로 내려간다. 단말 노드에 도달하면 그 노드의 표시값이 함수값이다.

변수들의 값은 변수값 배정(VVA, Variable Values Assignment) $(x_1 = b_1, x_2 = b_2, \ldots, x_n = b_n)$ 형태로 주어지며 각 $b_k \in \{0,1\}$ 이다. 예를 들어 함수 $f(x_1,x_2,x_3) = x_1 \land (x_2 \lor x_3)$ 에 대해 VVA $(x_1=1, x_2=1, x_3=0)$ 는 $f(1,1,0) = 1 \land (1 \lor 0) = 1$ 이 된다.

하나의 S-트리와 여러 개의 VVA가 주어질 때, 각 VVA에 대한 $f$ 의 값을 구하는 프로그램을 작성하라.

입력은 여러 개의 S-트리 기술로 이루어진다.

각 기술의 첫 줄에는 S-트리의 깊이를 나타내는 정수 $n$ 하나가 주어진다 ($1 \le n \le 7$).

다음 줄에는 변수 순서가 공백으로 구분된 $n$ 개의 문자열 $x_{i_1}\ x_{i_2}\ \ldots\ x_{i_n}$ 로 주어진다($x_1, \ldots, x_n$ 의 한 순열). 예를 들어 $n=3$ 이고 변수 순서가 $x_3, x_1, x_2$ 이면 이 줄은 다음과 같다.

x3 x1 x2

그 다음 줄에는 단말 노드의 표시값이 주어진다. 정확히 $2^n$ 개의 문자(각각 $0$ 또는 $1$)가 가장 왼쪽 단말 노드부터 가장 오른쪽 단말 노드까지의 순서로 나열된다.

그 다음 줄에는 VVA의 개수인 정수 $m$ 이 주어지고, 이어서 $m$ 개의 줄이 온다. 각 줄은 정확히 $n$ 개의 문자(각각 $0$ 또는 $1$)로 이루어진다. 변수 순서와 무관하게 첫 번째 문자는 항상 $x_1$ 의 값, 두 번째 문자는 $x_2$ 의 값, 이런 식이다. 예를 들어 다음 줄은

110

VVA $(x_1 = 1, x_2 = 1, x_3 = 0)$ 를 뜻한다.

입력은 첫 줄이 $n = 0$ 인 기술로 끝난다. 이 마지막 기술은 처리하지 않는다.

$j$ 번째 S-트리에 대해 먼저 S-Tree #j: 한 줄을 출력하고, 그 다음 줄에 주어진 $m$ 개의 VVA에 대한 $f$ 의 값을 주어진 순서대로 구분 기호 없이 한 문자씩 이어서 출력한다.

연속한 두 S-트리의 출력 사이에는 빈 줄 하나를 넣는다.