题目描述

给定两个长度为 $2^n$ 的序列 $A,B$，求另一序列 $C$ 使得 $C_k = \displaystyle \sum_{\substack{i \vee j = k\\ i \wedge j = 0}} A_i B_j$。

样例输入

输入的第一行包含一个整数 $n$。

接下来一行，包含 $2^n$ 个整数，描述序列 $A$。

接下来一行，包含 $2^n$ 个整数，描述序列 $B$。

样例输出

输出一行 $2^n$ 个整数，描述序列 $C$。答案取模 $998244353$。

样例数据

样例 1 输入

2
1 2 3 4
5 6 7 8

样例 1 输出

5 16 22 60

样例 2 输入

4
5 8 2 7 1 3 6 4 8 8 1 9 3 3 4 5
8 8 1 6 4 4 3 8 1 9 0 5 3 6 2 7

样例 2 输出

40 104 21 110 28 84 72 189 69 181 18 186 72 178 85 368

子任务

对于 $100\%$ 的数据，$1 \leq n \leq 19, 0 \leq A_i,B_i < 998244353$。