407973: GYM102956 A 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.

3
0111 0110 0001
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 1 

2
1100 1101
2 0 2 1
2 0 2 1

2 4 3 16 

1
0000
142857142 857142857
998244353 1755646

999999998000000001 0 

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$$$.