21119번 - Belarusian State University 다국어

Being a student of Belarusian State University (BSU) is an earnest reason for pride. While studying the Theory of Algorithms course, you are obliged to solve many challenging problems before you are admitted to the final exam. Here is one of these problems.

You are given a positive integer $n$ and $4n$ integers $c(i, j, k)$ which can be equal to $0$ or $1$ ($0 \le i < n$, $j \in \left\{0, 1\right\}$, $k \in \left\{0, 1\right\}$).

Consider two integers $x$ and $y$ between $0$ and $2^n - 1$, inclusively. Let $x = \sum\limits_{i = 0}^{n - 1}{x_i\cdot 2^i}$ and $y = \sum\limits_{i = 0}^{n - 1}{y_i \cdot 2^i}$ be their binary representations ($x_i, y_j \in \left\{0, 1\right\}$). Define $f(x, y) = \sum\limits_{i = 0}^{n - 1}{c(i, x_i, y_i)\cdot 2^i}$. Clearly, $f(x, y)$ is also an integer between $0$ and $2^n - 1$.

Given two multisets $A$ and $B$, find the multiset of values $f(a, b)$ over all pairs $(a, b)$, where $a \in A$, $b \in B$.

The first line contains an integer $n$ ($1 \leq n \leq 18$).

The second line contains $n$ binary strings of $4$ digits. The $i$-th string consists of the values of $c(i - 1, 0, 0)$, $c(i - 1, 0, 1)$, $c(i - 1, 1, 0)$, $c(i - 1, 1, 1)$ in this particular order.

The next two lines describe multisets $A$ and $B$, respectively. The description of a multiset consists of $2^n$ integers $q_0, q_1, \ldots, q_{2^n - 1}$ denoting the quantities of the numbers $0, 1, \ldots, 2^n - 1$ in the multiset ($q_i \ge 0$, $\sum q_i \leq 10^9$). There are no other numbers in the multisets.

Print $2^n$ integers in a single line, the quantities of the numbers $0, 1, \ldots, 2^n - 1$ in the resulting multiset.

In the first example, you are given $5$ and $6$. For $x_i, y_i \in \left\{0, 1\right\}$, we have $$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).$$ Thus, the only number in the resulting multiset is $7$.