J. Joining Polynomials
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Pedrinho did not like studying mathematics in school. He already didn't enjoy calculations that only involved numbers, but he had to start studying polynomials, which have several terms in terms of '$$$x$$$' that he never understood. When he began studying composite functions, he really gave up on mathematics for good.

As a homework, he needs to calculate the composite function of two polynomials, that is, given two polynomials $$$p(x)$$$ and $$$q(x)$$$, calculate the coefficients of the polynomial $$$p(q(x))$$$. For example, if $$$p(x) = x^2 + x + 2$$$ and $$$q(x) = x + 1$$$, then $$$p(q(x)) = (x+1)^2 + (x+1) + 2 = x^2 + 3x + 4$$$. Since Pedrinho already gave up on mathematics, he asked for your help to calculate all the coefficients of the resulting polynomial. Since the coefficients can be very large, the teacher asked to calculate the remainders of the coefficients modulo $$$998244353$$$.

Input

The input consists of $$$4$$$ lines.

The first line contains an integer $$$N_1$$$ $$$(1 \le N_1 \le 300)$$$ equal to the degree of polynomial $$$P$$$. The second line contains $$$N_1 + 1$$$ integers $$$P_i$$$ $$$(0 \le P_i \le 10^6)$$$ indicating the coefficients of polynomial $$$P$$$ from the lowest degree $$$0$$$ to the highest degree $$$N_1$$$, that is, polynomial $$$P$$$ is equal to the sum of $$$P_i \cdot x^i$$$ for $$$i$$$ from $$$0$$$ to $$$N_1$$$.

The third line contains an integer $$$N_2$$$ $$$(1 \le N_2 \le 300)$$$ equal to the degree of polynomial $$$Q$$$. The fourth line contains $$$N_2 + 1$$$ integers $$$Q_i$$$ $$$(0 \le Q_i \le 10^6)$$$ indicating the coefficients of polynomial $$$Q$$$ in the same manner as the coefficients of polynomial $$$P$$$, from the lowest degree to the highest. The leading coefficient of both polynomials is different from $$$0$$$.

Output

Print a line with $$$N_1 \cdot N_2 + 1$$$ integers equal to the coefficients of $$$p(q(x))$$$ modulo $$$998244353$$$, in order from the lowest degree to the highest degree.

Examples
Input
2
2 1 1
1
1 1
Output
4 3 1
Input
2
1 1 1
2
1 1 1
Output
3 3 4 2 1
Note

Explanation of example 1:

Example from the statement, $$$p(x) = x^2 + x + 2$$$, $$$q(x) = x + 1 \implies p(q(x)) = x^2 + 3x + 4$$$.