Problem Statement

Takahashi is creating a work schedule for $N$ days by designating each day as a workday or a holiday.

You are given a string $S$ of length $N$ representing the constraints on work days. If the $i$-th character of $S$ is x, day $i$ must be a workday. If it is ., day $i$ can be either a workday or a holiday.

There are $2^q$ valid work schedules satisfying the constraints, where $q$ is the number of . characters in $S$. For each $k=1,2,\dots,N$, solve the following problem:

Among the $2^q$ valid work schedules satisfying the constraints, find the number, modulo $998244353$, of schedules in which the longest consecutive block of holidays is exactly $k$ days.

Constraints

• $N$ is an integer between $1$ and $2 \times 10^5$, inclusive.
• $S$ is a string of length $N$ consisting of ., x.

Input

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

N
S

Output

Output $N$ lines. The $i$-th line should contain the answer for $k=i$.