시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 256 MB 1 1 1 100.000%

문제

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.

예제 입력 1

5 10
1 4 9 16 25

예제 출력 1

36 49 64 81 100 121 144 169 196 225

예제 입력 2

3 3
0 0 0

예제 출력 2

0 0 0

예제 입력 3

5 10
1 2 4 8 16

예제 출력 3

31 57 99 163 256 386 562 794 1093 1471

예제 입력 4

3 1
2 1 0

예제 출력 4

998244352

노트

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