Gus Fring 是一个非常谨慎的人。他从不乱来。当他要求某人解决一个问题时，他会给出一个完全正式的陈述。今天，他要求你来解决这个问题。

对于一个正整数 $n$，定义 $highest\_bit(n)$ 为满足 $2^i \le n$ 的最大整数 $i$。同时定义 $highest\_bit(0) = -1$。

给定一个正整数 $X$。求满足以下条件的正整数多重集 $S$ 的数量：

• $S$ 中的所有元素都是 $2$ 的非负整数次幂。
• $S$ 中所有元素的和为 $X$。
• 不存在一种将 $S$ 中的元素划分为两个组的方法，使得 $highest\_bit(S_1) = highest\_bit(S_2)$，其中 $S_1$ 是第一组元素的和，$S_2$ 是第二组元素的和。

对于 $X = 1, 2, \dots, n$ 求解此问题。

由于答案可能非常大，请将结果对 $998244353$ 取模。

输入格式

输入仅包含一行，为一个整数 $n$ ($1 \le n \le 10^6$)。

输出格式

输出 $n$ 个整数：分别为 $X = 1, 2, \dots, n$ 时问题的答案，对 $998244353$ 取模。

样例

样例输入 1

10

样例输出 1

1 1 2 1 1 3 6 1 1 2