Score: $700$ points

问题陈述

给定整数 $N$ 和 $K$。考虑一个长度为 $K$ 的序列 $a=(a_1,a_2,\dots,a_K)$，它满足以下所有条件：

• $a_i$ 是一个整数，使得 $1 \le a_i \le N$。
• $a$ 中的所有元素都是不同的。

让我们将所有可能的序列 $a$ 按字典序排列，形成一个称为字典 $s$ 的“序列序列”。

给定一个存在于字典 $s$ 中的序列 $P$，对于每个整数 $t=1,2,\dots,N$，回答以下问题：

• 找出满足以下所有条件的序列 $b$ 的数量，对 $998244353$ 取模：
  • 序列 $b$ 存在于字典 $s$ 中。
  • 整数 $t$ 包含在序列 $b$ 中。
  • 序列 $b$ 字典序小于或等于序列 $P$。

序列的字典序是什么？如果满足以下 1. 或 2. 中的任一条件，则序列 $A = (A_1, \ldots, A_{|A|})$ 严格字典序小于 $B = (B_1, \ldots, B_{|B|})$：

1. $|A|<|B|$ 且 $(A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|})$。
2. 存在一个整数 $1\leq i\leq \min\{|A|,|B|\}$，满足以下两个条件：
   • $(A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})$
   • $A_i < B_i$

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given integers $N$ and $K$. Consider a sequence $a=(a_1,a_2,\dots,a_K)$ of length $K$ that satisfies all of the following conditions:

• $a_i$ is an integer such that $1 \le a_i \le N$.
• All elements in $a$ are different.

Let us arrange all possible sequences $a$ in lexicographical order to form a "sequence of sequences" called the dictionary $s$.

Given a sequence $P$ that exists in the dictionary $s$, answer the following question for each integer $t=1,2,\dots,N$:

• Find the number, modulo $998244353$, of sequences $b$ that satisfy all of the following conditions:
  • The sequence $b$ exists in the dictionary $s$.
  • The integer $t$ is contained in the sequence $b$.
  • The sequence $b$ is lexicographically less than or equal to the sequence $P$.

What is lexicographical order for sequences? A sequence $A = (A_1, \ldots, A_{|A|})$ is lexicographically strictly less than $B = (B_1, \ldots, B_{|B|})$ if and only if 1. or 2. below is satisfied:

1. $|A|<|B|$ and $(A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|})$.
2. There is an integer $1\leq i\leq \min\{|A|,|B|\}$ that satisfies both of the following:
   • $(A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})$
   • $A_i < B_i$

Constraints

• All input values are integers.
• $1 \le K \le N \le 3 \times 10^5$
• $P$ satisfies the condition in the problem statement.

Input

The input is given from Standard Input in the following format:

$N$ $K$

$P_1$ $P_2$ $\dots$ $P_K$

Output

Print $N$ lines in total.
The $i$-th line should contain the answer to the problem for $t=i$ as an integer.

Sample Input 1

4 2
3 2

Sample Output 1

5
5
4
2

In this input, $N=4,K=2$.
Here, the dictionary $s$ is $((1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3))$.

Among the sequences in the dictionary $s$ that are lexicographically less than or equal to $(3,2)$,

• five sequences contain $1$: $(1,2),(1,3),(1,4),(2,1),(3,1)$,
• five sequences contain $2$: $(1,2),(2,1),(2,3),(2,4),(3,2)$,
• four sequences contain $3$: $(1,3),(2,3),(3,1),(3,2)$,
• two sequences contain $4$: $(1,4),(2,4)$.

Sample Input 2

18 13
5 13 11 2 18 1 10 15 17 4 12 7 3

Sample Output 2

925879409
905921009
665544804
665544719
783035803
349952762
349952758
349952757
349952757
349921178
212092637
710350150
378895603
129113201
129111892
129098081
129096772
110181652