Given a positive integer $n$. You are given an $n \times 2 \times 2$ binary array $A_{i,j,k}$, where $i \in [0, n-1], j \in [0, 1], k \in [0, 1]$.

Define a binary operation $f(x, y)$ for $0 \le x, y < 2^n$ ($x, y \in \mathbb{Z}$) as follows:

• Let $x = \sum_{i=0}^{n-1} 2^i a_i$, where $a_i \in \{0, 1\}$.
• Let $y = \sum_{i=0}^{n-1} 2^i b_i$, where $b_i \in \{0, 1\}$.
• Let $z = \sum_{i=0}^{n-1} 2^i A_{i, a_i, b_i}$.
• Then $f(x, y) = z$.

Given two arrays $p$ and $q$ of length $2^n$ (both indexed from $[0, 2^n-1]$), calculate their convolution under the operation $f$. In other words, find the array $res$ (indexed from $[0, 2^n-1]$), where $res_i = \sum_{j=0}^{2^n-1} \sum_{k=0}^{2^n-1} [f(j, k) = i] p_j q_k$.

Input

The first line contains a positive integer $n$.

The second line contains $n$ binary strings of length 4. The $i$-th binary string represents the values of $A_{i-1, 0, 0}, A_{i-1, 0, 1}, A_{i-1, 1, 0}, A_{i-1, 1, 1}$ in order.

The third line contains $2^n$ integers describing the array $p$. The fourth line contains $2^n$ integers describing the array $q$.

Output

Output a single line containing $2^n$ space-separated integers, describing the array $res$.

Examples

Input 1

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

Output 1

0 0 0 0 0 0 0 1

Input 2

2
1100 1101
2 0 2 1
2 0 2 1

Output 2

2 4 3 16

Input 3

1
0000
142857142 857142857
998244353 1755646

Output 3

999999998000000001 0

Input 4

See ex_conv4.in/ex_conv4.ans in the provided files. This example satisfies the constraints of Subtask 1.

Input 5

See ex_conv5.in/ex_conv5.ans in the provided files. This example satisfies the constraints of Subtask 5.

Subtasks

Please note that the total score for this problem is 125 points.

For all data: $n \le 18$, $0 \le p_i \le 10^9$, $0 \le q_i \le 10^9$, $\sum p_i \le 10^9$, and $\sum q_i \le 10^9$.

• Subtask 1 (1 point): $n \le 10$.
• Subtask 2 (1 point): Each binary string is 0001.
• Subtask 3 (4 points): Each binary string is 0110.
• Subtask 4 (5 points): Each binary string is 0001 or 0111.
• Subtask 5 (114 points): No special constraints.