18953번 - Continue the Sequence 다국어

For sure you have seen puzzles like "Given the sequence, find its next element". They seem logical in your childhood, but later you begin to understand that you can write any number and justify it with some tricky construction.

In this problem you have to continue the sequence "in the easiest way". Still not strict enough? Let us give a formal definition.

Let the hardness of the sequence $a_{1}, a_{2}, \ldots, a_{n}$ be the minimum integer $d$ such that there exists a polynomial $p$ of degree $d$ for which $p(x) \equiv a_{x} \pmod{998\,244\,353}$ for all $x$ from $1$ to $n$. For this problem, consider the polynomial $p(x) = 0$ to have degree $-1$.

Given a sequence $a_{1}, a_{2}, ..., a_{n}$ of size $n$, your task is to construct a sequence $b_{1}, b_{2}, \ldots, b_{n+m}$ of size $n+m$ such that:

• $0 \le b_{i} < 998\,244\,353$ for all $i$ from $1$ to $n+m$,
• $a_{i} = b_{i}$ for all $i$ from $1$ to $n$,
• The hardness of the sequence $b$ is as small as possible.

The first line of input contains two integers $n$ and $m$ ($1 \le n \le 10^{5}$, $1 \le m \le 8 \cdot 10^{5}$).

The second line of input contains $n$ integers $a_{i}$: the initial sequence ($0 \le a_{i} < 998\,244\,353$).

Print $m$ integers $b_{n+1}, b_{n+2}, \ldots, b_{n+m}$ separated by spaces.

The notation $u \equiv v \pmod{p}$ means that $u$ and $v$ have the same remainder modulo $p$.