P4717 [Template] Fast Möbius / Walsh Transform (FMT / FWT).

Given two sequences $A$ and $B$ of length $2^n$, define $$C_i=\sum_{j\oplus k = i}A_j \times B_k$$ Compute $C$ respectively when $\oplus$ is OR, AND, and XOR.

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

$1 \le n \le 17$. Translated by ChatGPT 5