Hide

Problem G
Number Theoretic Transform

Accepted submissions to this problem will be granted a score of 20
Languages en is

You are given two polynomials. You should simply print their product. This time you have to do it fast though and modulo 998244353.

Input

The first line of input contains two positive integers n,m, the number of coefficients in each polynomial. The next two lines contain one polynomial each. Each polynomial is given as its coefficients in ascending order, that is to say if the input is a0 a1 a2 a3 then that represents the polynomial a0+a1x+a2x2+a3x3. You may assume that n,m105 and that all coefficients ai satisfy 0ai<998244353.

Output

Print the product of the two polynomials in the input in the same format as the polynomials in the input. Print exactly n+m1 coefficients of the output polynomial. Print the coefficients modulo 998244353.

Sample Input 1 Sample Output 1
3 4
1 2 3
4 5 6 7
4 13 28 34 32 21 
Sample Input 2 Sample Output 2
3 3
10000000 10000000 10000000
10000000 10000000 10000000
871938225 745632097 619325969 745632097 871938225 
Hide

Please log in to submit a solution to this problem

Log in