벨라루스 국립대학교

벨라루스 국립대학교 학생이라는 것은 그 자체로 자랑스러운 일이다. 알고리즘 이론 수업을 듣는 학생은 기말고사에 응시하기 전에 어려운 문제를 많이 풀어야 한다. 다음은 그중 하나다.

양의 정수 $n$과, 각각 0 또는 1일 수 있는 $4n$개의 정수 $c(i, j, k)$가 주어진다 ($0 \le i < n$, $j \in \{0, 1\}$, $k \in \{0, 1\}$).

0 이상 $2^n - 1$ 이하의 두 정수 $x$, $y$를 생각하자. $x = \sum_{i=0}^{n-1} x_i \cdot 2^i$, $y = \sum_{i=0}^{n-1} y_i \cdot 2^i$를 각각의 이진 표현이라 하자 ($x_i, y_i \in \{0, 1\}$). $f(x, y) = \sum_{i=0}^{n-1} c(i, x_i, y_i) \cdot 2^i$로 정의한다. $f(x, y)$ 역시 0 이상 $2^n - 1$ 이하의 정수이다.

두 다중집합 $A$, $B$가 주어졌을 때, $a \in A$, $b \in B$인 모든 쌍 $(a, b)$에 대해 $f(a, b)$ 값들의 다중집합을 구하라.

첫 줄에 정수 $n$ ($1 \leq n \leq 18$)이 주어진다.

둘째 줄에는 4자리 이진 문자열 $n$개가 주어진다. $i$번째 문자열은 $c(i - 1, 0, 0)$, $c(i - 1, 0, 1)$, $c(i - 1, 1, 0)$, $c(i - 1, 1, 1)$의 값을 이 순서대로 담고 있다.

다음 두 줄은 각각 다중집합 $A$와 $B$를 나타낸다. 다중집합은 $2^n$개의 정수 $q_0, q_1, \ldots, q_{2^n - 1}$로 기술되며, $q_i$는 다중집합에 들어 있는 수 $i$의 개수이다 ($q_i \ge 0$, $\sum q_i \leq 10^9$). 다중집합에는 이 외의 수가 없다.

$2^n$개의 정수를 한 줄에 출력하라. 각 정수는 결과 다중집합에서 $0, 1, \ldots, 2^n - 1$ 각 수의 개수이다.

첫 번째 예제에서는 $5$와 $6$이 주어진다. $x_i, y_i \in \{0, 1\}$에 대해 $f(x_0 + 2x_1 + 4x_2, y_0 + 2y_1 + 4y_2) = (x_0 \text{ OR } y_0) + 2 \cdot (x_1 \text{ XOR } y_1) + 4 \cdot (x_2 \text{ AND } y_2)$ 가 성립한다. 따라서 결과 다중집합에 들어 있는 수는 $7$ 하나뿐이다.