你一定见过类似“给定数列，求下一个元素”的谜题。在童年时，它们看起来很符合逻辑，但后来你开始明白，你可以写出任何数字，并用一些巧妙的构造来证明它是合理的。

在本题中，你需要以“最简单的方式”延续数列。这还不够严谨吗？让我们给出一个正式的定义。

设数列 $a_1, a_2, \dots, a_n$ 的“难度”（hardness）为满足以下条件的最小整数 $d$：存在一个次数为 $d$ 的多项式 $p$，使得对于所有 $1$ 到 $n$ 之间的 $x$，都有 $p(x) \equiv a_x \pmod{998\,244\,353}$。对于本题，我们规定零多项式 $p(x) = 0$ 的次数为 $-1$。

给定一个长度为 $n$ 的数列 $a_1, a_2, \dots, a_n$，你的任务是构造一个长度为 $n+m$ 的数列 $b_1, b_2, \dots, 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}, \dots, b_{n+m}$，用空格分隔。

样例

样例输入 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

说明

符号 $u \equiv v \pmod{p}$ 表示 $u$ 和 $v$ 对模 $p$ 同余。