题目描述

给定 $\mathbb{Z}/998244353\mathbb{Z}$ 上的 $K$ 元多项式 $f(x_1, x_2, ..., x_K)$ 和 $g(x_1, x_2, ..., x_K)$。计算 $f$ 与 $g$ 在模 $(x_1^{N_1}, x_2^{N_2}, ..., x_K^{N_K})$ 意义下的乘积。

约束条件

• $0 \le K \le 18$
• $\prod N_i \le 2^{18}$
• $2 \le N_i$

输入

K
N_1 N_2 ... N_K
f
g

$f, g$ 是长度为 $\prod N_i$ 的整数数组，由 $0$ 到 $998244352$ 之间的整数组成。第 $i = i_1 + i_2 N_1 + ... + i_K N_1 N_2 .... N_{K-1}$ 个元素对应于 $(x_1^{i_1}, x_2^{i_2}, ..., x_K^{i_K})$ 的系数。

输出

fg

$fg$ 是长度为 $\prod N_i$ 的整数数组，由 $0$ 到 $998244352$ 之间的整数组成。与输入格式相同，第 $i = i_1 + i_2 N_1 + ... + i_K N_1 N_2 ... N_{K-1}$ 个元素对应于 $(x_1^{i_1}, x_2^{i_2}, ..., x_K^{i_K})$ 的系数。

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

6 19 40 70 110

2
2 3
1 2 3 4 5 6
7 8 9 10 11 12

7 22 30 80 73 182

0

123
456

56088