Game with Polynomials 2

In this problem:

• For convenience, let $0^0 = 1$.
• Fix $p = 998244353$. This number is prime.

Kipa wanted to set the following interactive problem.

You can call the following function:

• evaluate(x): substitute x into the polynomial $Q(x)$ and return the remainder modulo $p$.

You can call the evaluate function at most $q$ times. Your program receives $n$ as input and must output the coefficients of $Q(x)$ modulo $p$.

While preparing the test cases, however, Kipa realized that evaluating a degree-$n$ polynomial at up to $q$ points in the straightforward way is $O(qn)$! To avoid taking shortcuts as in last year's problem, Kipa asked Kyaryunha, a talented PSer, to somehow write a fast interactor for this problem.

Kyaryunha, in a bind, asks you for help. Let us write the interactor for Kyaryunha!

The first line gives $n$ and $q$.

The second line gives $(n+1)$ integers $a_n, a_{n-1}, \ldots, a_1, a_0$, separated by spaces.

From the third line, $q$ lines give integers $b_1, \ldots, b_q$.

Every integer from the second line onward is between $0$ and $p-1$.

Print one integer per line, for a total of $q$ lines. The integer printed on the $i$-th line must be

$\sum_{k=0}^{n} a_k b_i^k \bmod p$