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: $|A|<|B|$ and $(A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|})$. 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.