C1681 [Wannafly冬令营2018Day5]Fast Kronecker Transform

内存限制:256 MB 时间限制:4500 ms

题目描述

给你两个数列$a_0, a_1, \dots, a_n$,$b_0, b_1, \dots, b_m$。

求一个数列$c_k (0\leq k\leq n+m)$,其中$c_k=(\sum_{i+j=k} ij\delta_{a_i, b_j}) \bmod 998244353$,其中$\delta_{a,b}$为Kronecker符号,当$a=b$是$\delta_{a,b}=1$,否则为$0$。

输入格式

第一行输入两个整数$n,m (1\leq n,m\leq 10^5)$。

接下来一行$n+1$个整数$a_0, a_1, \dots, a_n$,接下来一行$m+1$个整数$b_0, b_1, \dots, b_m (1\leq a_i,b_i\leq 10^9)$。

输出

输出$n+m+1$个整数,表示$c_0, c_1, \dots, c_{n+m}$。

样例

样例输入 1

5 5 1 2 1 3 2 2 3 1 2 3 1 2

样例输出 1

0 0 0 4 0 0 30 10 0 20 25

提示