题目描述

在《LIAR GAME》中，小 E 看到了一个有趣的游戏。

这个游戏名叫《走私游戏》。游戏规则大概是这样的：一名玩家扮演走私者，一名玩家扮演检察官。走私者可以将 $x$ 日元（$x$ 为 $[0,n]$ 内的整数，由走私者决定）秘密放入箱子中，而检查官需要猜测箱子中的金额。假设检察官猜了 $y$（$y$ 也必须是整数）。如果 $x=y$，则走私失败，走私者一分钱也拿不到。如果 $x>y$，则走私成功，走私者可以从检查官那里拿走 $x$ 日元。如果 $x<y$，则走私失败，但是由于冤枉检察官需要赔付给走私者 $y/2$ 日元。游戏分有限回合进行。双方轮流做走私者和检察官。

可以证明，最优情况下每个回合走私者会采用同一种策略，检察官也会采用同一种策略。小 E 想知道在一个回合中，双方的最优策略分别是什么。

输入格式

一行一个正整数 $n$。

输出格式

输出两行，每行 $n+1$ 个数，其中第 $i$ 个表示放/猜 $i-1$ 日元的概率。

第一行输出走私者的策略，第二行输出检察官的策略。

你需要保证，在一方的策略不变的情况下，另一方无论如何改变自己的策略，都不能使自己的期望收益比原来多。

可以证明，这样的策略是唯一的。

答案对 $998244353$ 取模。

1

665496236 332748118
332748118 665496236

数据范围与提示

保证 $1\le n \le 400000$。