E. Antisocial Theatergoers
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Laila is going to the theater to see a performance by Clube da Esquina, a celebrated Brazilian musical collective. Unfortunately, something has come up, and she will be the last person to arrive.

The theater has a single row of $$$n$$$ seats, numbered from $$$1$$$ to $$$n$$$, with an aisle at each end. The aisles are represented by positions $$$0$$$ and $$$n+1$$$. The distance between positions $$$i$$$ and $$$j$$$ is $$$|i-j|$$$.

The show is sold out. The $$$n-1$$$ people arriving before Laila enter one at a time and are extremely antisocial: each wants to sit as far as possible from both the people already seated and the aisles.

The comfort of an empty seat is the minimum distance from that seat to any occupied seat or aisle, measured when the person chooses their seat. Each person chooses an empty seat with maximum comfort. If several seats tie, they may choose any of them.

On her way to the theater, Laila can think of only one thing: which seat will be left for her?

For each seat $$$k$$$, from $$$1$$$ to $$$n$$$, determine how many sequences of choices by the $$$n-1$$$ people leave that seat empty. Two sequences are different if the seat chosen at some step differs. Since the answers may be large, print each answer modulo $$$998244353$$$.

Input

The input consists of a single line containing an integer $$$n$$$ ($$$2 \le n \le 10^{5}$$$), the number of seats.

Output

Print $$$n$$$ space-separated integers on a single line. The $$$k$$$-th integer must be the number of valid sequences of choices that leave seat $$$k$$$ as the last available seat, modulo $$$998244353$$$.

Examples
Input
3
Output
1 0 1
Input
4
Output
4 2 2 4
Note

Explanation for example 1

The first person chooses seat $$$2$$$. The second may choose seat $$$1$$$ or $$$3$$$, leaving the other empty. Thus, the answers are $$$1$$$, $$$0$$$, and $$$1$$$.