题目描述

定义一个随机线段树为一个二叉树，其中每个节点表示一个闭区间 $[l,r]$：

• 如果 $l = r$，则该节点为叶子节点。
• 如果 $l < r$ 且区间的长度 $(r - l + 1)$ 是偶数：设 $x = \lfloor (l + r)/2 \rfloor$。节点的左子节点表示 $[l,x]$，右子节点表示 $[x+1,r]$。
• 如果 $l < r$ 且区间的长度 $(r - l + 1)$ 是奇数：设 $x = (l + r)/2$。以 $1/2$ 的概率，左子节点表示 $[l,x]$，右子节点表示 $[x+1,r]$；以 $1/2$ 的概率，左子节点表示 $[l,x-1]$，右子节点表示 $[x,r]$。

给定一个线段树，定义 $\text{cost}(x,y)$ 如下： 在查询区间 $[x,y]$ 时，从根节点开始，设当前在节点 $[l,r]$，过程如下：

• 如果 $[x,y]$ 包含 $[l,r]$，查询结束。
• 否则，如果左儿子节点与 $[x,y]$ 相交，则查询左儿子节点；如果右儿子节点与 $[x,y]$ 相交，则查询右儿子节点。
• $\text{cost}(x,y)$ 的值是查询过程中访问的节点数量。

给定 $n$，考虑一个随机线段树，其根节点表示 $[1,n]$。对于 $1 \leq i \leq 2 \cdot n$，计算 $\text{cost}(x,y)$ 等于 $i$ 的区间 $[x,y]$ 的期望数量，结果对 $998244353$ 取模。

输入格式

第一行包含一个整数 $n$ ($1 \leq n \leq 10^5$)。

输出格式

输出 $2 \cdot n$ 行。每行包含一个整数，表示答案对 $998244353$ 取模。

3

1
2
2
1
0
0

4

1
2
4
2
1
0
0
0

5

1
2
4
4
499122179
1
499122177
0
0
0