Given integers $n, y$ and an integer sequence $A = \{a_1, a_2, \dots, a_n\}$ of length $n$, it is guaranteed that the sequence $A$ is monotonically non-decreasing or monotonically non-increasing.

Construct a directed graph $G(V, E)$, where $V = \{1, 2, \dots, n\}$ and $E = \{(i, j) \mid 1 \leq i, j \leq n, a_i \geq j\}$. Note that the graph $G$ may contain self-loops.

A subset of edges $T \subseteq E$ is defined as valid if and only if the in-degree and out-degree of every vertex in the graph $G'(V, T)$ are at most $1$. A self-loop contributes $1$ to both the in-degree and out-degree of its corresponding vertex. The weight of a valid edge subset $T$ is defined as $y^{\mathrm{cycle}(T)}$, where $\mathrm{cycle}(T)$ denotes the number of cycles in the graph $G'(V, T)$, and a self-loop is considered a cycle.

Specifically, we define $0^0 = 1$.

For all integers $0 \leq k \leq n$, calculate the sum of weights of all valid edge subsets of size $k$, modulo $998244353$.

Input

The first line contains two integers $n, y$. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ describing the sequence $A$.

Output

Output $n+1$ integers on a single line, where the $i$-th integer represents the sum of weights of all valid edge subsets of size $i-1$, modulo $998244353$.

Examples

Input 1

2 2
2 2

Output 1

1 6 6

Note 1

In graph $G$, there are two vertices and edges $\{(1, 1), (1, 2), (2, 1), (2, 2)\}$.

The only valid edge subset of size $0$ is the empty set, which has a weight of $1$. Thus, the sum of weights for size $0$ is $1$.

The valid edge subsets of size $1$ are $\{(1, 1)\}, \{(2, 2)\}, \{(1, 2)\}, \{(2, 1)\}$, with weights $2, 2, 1, 1$ respectively, for a total sum of $6$.

The valid edge subsets of size $2$ are $\{(1, 1), (2, 2)\}, \{(1, 2), (2, 1)\}$, with weights $4, 2$ respectively, for a total sum of $6$.

Constraints

For $100\%$ of the data, $1 \leq n \leq 10^5$, $0 \leq y < 998244353$, $0 \leq a_i \leq n$. It is guaranteed that the sequence $A$ is monotonically non-decreasing or monotonically non-increasing.

The first $5$ subtasks satisfy the condition that $A$ is monotonically non-decreasing. The special properties and scores are shown in the table below.

The last $4$ subtasks satisfy the condition that $A$ is monotonically non-increasing. Let $b_i = \sum_{j=1}^n [a_j \geq i]$. The special properties and scores are shown in the table below.

Please be aware of the impact of algorithm constants on execution time.