这是一道模板题。

今有两个数列 $A_0, A_1, A_2, \cdots , A_n$ 和 $B_0, B_1, B_2, \cdots , B_m$，定义数列 $C$ 由 $A, B$ 两个数列计算而成：

$$ \forall i \in [0, N), C_i = \sum_{j=0}^n \sum_{k=0}^m { [j \oplus k = i] A_j B_k } \\ N = \min_{t \in \mathbb{Z}^+, 2^t \ge n, 2^t \ge m} 2^t $$

现给出 $\oplus$ 运算和 $n, m, A, B$，请你求出 $C$。

输入格式

第一行一个正整数 $type$；$type=1$ 表示 $\oplus$ 为 $\mathrm{or}$（按位或）运算，$type=2$ 表示 $\oplus$ 为 $\mathrm{and}$（按位与）运算，$type=3$ 表示 $\oplus$ 为 $\mathrm{xor}$（按位异或）运算。

第二行两个正整数 $n, m$。

第三行 $n+1$ 个整数表示 $A_0, A_1, A_2, \cdots , A_n$。

第四行 $m+1$ 个整数表示 $B_0, B_1, B_2, \cdots , B_m$。

输出格式

$N$ 个整数，分别表示 $C_0, C_1, C_2, \cdots , C_{N-1}$ 对 $998244353$ 取模后的结果。

样例一

input

1
2 3
1 2 3
3 4 1 2

output

3 18 13 26

样例二

input

2
2 3
1 2 3
3 4 1 2

output

39 12 9 0

样例三

input

3
2 3
1 2 3
3 4 1 2

output

14 16 14 16

限制与约定

对于 $100\%$ 的数据，保证 $1 \le type \le 3, 1 \le n, m \le 10^5, 0 \le A_i, B_i < 998244353$。

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$