给定 F(x)=n−1∑i=0fixi 与 G(x)=n−1∑i=0gixi,其中 g0=0。
求 H(x) = F(G(x)) \pmod{x^{n}} 的各项系数,取模 998\,244\,353。
输入格式
输入的第一行包含一个整数 N。
接下来一行,包含 N 个整数 f_0, f_1, \cdots, f_{n-1}。保证对每个 i 有 0 \leq f_i < 998\,244\,353。
接下来一行,包含 N 个整数 g_0, g_1, \cdots, g_{n-1}。保证有 g_0 = 0,且对每个 i 有 0 \leq g_i < 998\,244\,353。
输出格式
输出一行,包含 N 个整数 h_0, h_1, \cdots, h_{n-1}。
样例数据
样例输入
6
1 1 4 5 1 4
0 9 0 2 2 8
样例输出
1 9 324 3647 6707 238778
子任务
对于所有的数据,我们有 1 \leq N \leq 50\,000。
子任务 | N \leq |
---|---|
1 | 10 |
2 | 1\,000 |
3 | 2\,000 |
4 | 4\,000 |
5 | 7\,000 |
6 | 10\,000 |
7 | 15\,000 |
8 | 20\,000 |
9 | 30\,000 |
10 | 50\,000 |