Convolution of Sequences using Bitwise Operations

You are given two sequences A and B, each of length \(2^n\). For a given bitwise operator \(\oplus\), define the sequence C as follows:

[ C_i = \sum_{j \oplus k = i} A_j \times B_k ]

You are required to compute the sequence C for each of the following bitwise operators:

• OR (\(\vee\)): Use the condition \(j \vee k = i\).
• AND (\(\wedge\)): Use the condition \(j \wedge k = i\).
• XOR (\(\oplus\)): Use the condition \(j \oplus k = i\).

Note: The indices \(j\) and \(k\) range from 0 to \(2^n - 1\). It is guaranteed that the size of each sequence is exactly \(2^n\).

inputFormat

The input consists of three lines:

1. An integer \(n\) (\(n \ge 0\)).
2. \(2^n\) space-separated integers denoting the elements of sequence A.
3. \(2^n\) space-separated integers denoting the elements of sequence B.

outputFormat

Output three lines corresponding to the convolution result of the sequences under the following bitwise operations in order:

1. Bitwise OR convolution: For each \(0 \le i < 2^n\), print \(C_i\) where \(j \vee k = i\).
2. Bitwise AND convolution: For each \(0 \le i < 2^n\), print \(C_i\) where \(j \wedge k = i\).
3. Bitwise XOR convolution: For each \(0 \le i < 2^n\), print \(C_i\) where \(j \oplus k = i\).

Each line should contain \(2^n\) space-separated integers.

sample

1
1 2
3 4

3 18
13 8
11 10