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 4ドルn$ 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ドル$.