身为白俄罗斯国立大学（BSU）的学生是一件值得骄傲的事情。在学习算法理论课程时，你必须在参加期末考试前解决许多具有挑战性的问题。以下是其中之一。

给定一个正整数 $n$ 和 $4n$ 个整数 $c(i, j, k)$，其中 $c(i, j, k) \in \{0, 1\}$（$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 \le n \le 18$)。

第二行包含 $n$ 个 4 位的二进制字符串。第 $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, \dots, q_{2^n-1}$ 组成，分别表示多重集中数字 $0, 1, \dots, 2^n - 1$ 的数量（$q_i \ge 0, \sum q_i \le 10^9$）。多重集中没有其他数字。

输出格式

在一行中输出 $2^n$ 个整数，即结果多重集中数字 $0, 1, \dots, 2^n - 1$ 的数量。

样例

输入 1

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

输出 1

0 0 0 0 0 0 0 1

输入 2

2
1100 1101
2 0 2 1
2 0 2 1

输出 2

2 4 3 16

输入 3

1
0000
142857142 857142857
998244353 1755646

输出 3

999999998000000001 0

说明

在第一个样例中，给定的是 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。