问题描述

高桥正在制定一个包含 $N$ 天的工作日程，其中每天都被指定为工作日或休息日。

给定一个长度为 $N$ 的字符串 $S$，表示工作日的约束。如果 $S$ 的第 $i$ 个字符是 x，则第 $i$ 天必须是工作日。如果是 .，则第 $i$ 天可以是工作日或休息日。

存在 $2^q$ 种满足这些约束的有效工作日程，其中 $q$ 是 $S$ 中 . 字符的数量。对于每个 $k=1,2,\dots,N$，解决以下问题：

在满足约束的 $2^q$ 种有效工作日程中，找出最长连续休息日块恰好为 $k$ 天的日程数量，结果模 $998244353$。

约束条件

• $N$ 是一个 $1$ 到 $2 \times 10^5$ 之间的整数（含）。
• $S$ 是一个长度为 $N$ 的字符串，由 . 和 x 组成。

输入

输入将从标准输入以以下格式给出：

• $N$
• $S$

输出

输出 $N$ 行。第 $i$ 行应包含当 $k=i$ 时的答案。

5
.x...

9
4
2
0
0

用 o 表示假期，合法的排班方案如下：

• $k=1$: oxxxx, oxoxx, oxoxo, oxxox, oxxxo, xxoxx, xxoxo, xxxox, xxxxo
• $k=2$: oxoox, oxxoo, xxoox, xxxoo
• $k=3$: oxooo, xxooo

7
.......

33
47
27
12
5
2
1

20
.....x...x..........

9359
75312
94664
46840
23680
7168
3072
1280
512
256
0
0
0
0
0
0
0
0
0
0