수열 이어가기

“수열이 주어졌을 때 다음 원소를 구하라”는 퍼즐을 본 적이 있을 것이다. 어릴 때는 논리적으로 보이지만, 나중에는 어떤 수든 적고 교묘한 구성으로 정당화할 수 있다는 것을 알게 된다.

이 문제에서는 수열을 “가장 쉬운 방법으로” 이어가야 한다. 아직 엄밀하지 않다고? 형식적인 정의를 내리자.

수열 $a_1, a_2, \ldots, a_n$의 어려움을, $1$부터 $n$까지의 모든 $x$에 대해 $p(x) \equiv a_x \pmod{998\,244\,353}$을 만족하는 차수 $d$의 다항식 $p$가 존재하는 최소 정수 $d$로 정의하자. 이 문제에서는 다항식 $p(x) = 0$의 차수를 $-1$로 본다.

크기 $n$의 수열 $a_1, a_2, ..., a_n$이 주어졌을 때, 다음 조건을 만족하는 크기 $n+m$의 수열 $b_1, b_2, \ldots, b_{n+m}$을 구성하라:

• $1$부터 $n+m$까지의 모든 $i$에 대해 $0 \le b_i < 998\,244\,353$,
• $1$부터 $n$까지의 모든 $i$에 대해 $a_i = b_i$,
• 수열 $b$의 어려움이 가능한 한 작다.

첫째 줄에 두 정수 $n$과 $m$이 주어진다 ($1 \le n \le 10^{5}$, $1 \le m \le 8 \cdot 10^{5}$).

둘째 줄에 $n$개의 정수 $a_i$가 주어진다: 초기 수열 ($0 \le a_i < 998\,244\,353$).

$m$개의 정수 $b_{n+1}, b_{n+2}, \ldots, b_{n+m}$을 공백으로 구분해 출력하라.

표기 $u \equiv v \pmod{p}$는 $u$와 $v$가 $p$에 대해 같은 나머지를 가진다는 뜻이다.