Problem Description

Given two sequences $A$ and $B$ of length $2^n$, define

Compute $C$ respectively when $\oplus$ is OR, AND, and XOR.

Input Format

The first line contains an integer $n$.
The second line contains $2^n$ numbers $A_0, A_1, \ldots, A_{2^n-1}$.
The third line contains $2^n$ numbers $B_0, B_1, \ldots, A_{2^n-1}$.

Output Format

Output three lines. Each line contains $2^n$ numbers, representing the values of $C_0, C_1, \ldots, C_{2^n-1}$ when $\oplus$ is OR, AND, and XOR, respectively, taken $\bmod\ 998244353$.

2
2 4 6 8
1 3 5 7

2 22 46 250
88 64 112 56
100 92 68 60

Hint

Data Constraints

• $1 \le n \le 17$
• $0\le a_i,b_i<998244353$

Translated by ChatGPT 5