题目描述

对于长度为 $k$ 的数列 $A_k=\left\{a_1,a_2,\dots,a_k\right\}$ 和正整数 $m$ ，定义 $A_k$ 是 “ $1$ 型数列 ” 当且仅当：

• $\forall 1 \le i <k,a_i\&a_{i+1}\neq 0$
• $\forall 1 \le i \le k,a_i \in \mathbb{N},a_i \le m $

对于长度为 $k$ 的数列 $B_k=\left\{b_1,b_2,\dots,b_k\right\}$ 和正整数 $m$ ，定义 $B_k$ 是 “ $2$ 型数列 ” 当且仅当：

• $\forall 1 \le i \le k,b_i \& b_{\left(i\; \bmod \;k\right) +1} \neq 0$
• $\forall 1 \le i \le k, b_i \in \mathbb{N},b_i\le m$

现在给定正整数 $n,m$ ，对于 $k=1,2,\dots n$ ，求出长度为 $k$ 的本质不同的“$1$型数列”的个数和本质不同的“$2$型数列”的个数，模 $998244353$

两个“$1$型数列” $A_{k}$ 和 $A_{k}^{\prime}$ 被认为是本质不同的，当且仅当 $\exist 1\le i \le k,a_i\neq a_{i}^{\prime}$

两个“$2$型数列” $B_k$ 和 $B_{k}^{\prime}$ 被认为是本质不同的，当且仅当 $\forall 0\le i < k,\exist 1 \le j \le k,b_{j}\neq b_{\left(\left(j+i-1\right)\bmod \;k\right)+1}^{\prime}$ ，即两个数列“旋转”后不相同

输入格式

一行两个正整数 $n$ ，$m$

输出格式

输出两行，每行 $n$ 个数。

第一行第 $i$ 个数 表示长度为 $i$ 的本质不同的 “$1$型数列” 的个数

第二行第 $i$ 个数 表示长度为 $i$ 的本质不同的 “$2$型数列” 的个数

注意：如果输出中前 $n$ 个数是对的，可以获得该测试点 50% 的分数，但是如果程序没有输出 $2n$ 个 $\left[0,998244353\right)$ 中的数，该测试点会被判为答案错误

样例 $1$ 输入

3 4

样例 $1$ 输出

5 8 18
4 6 8

样例 $1$ 解释

长度为 $1$ 的 “$1$ 型数列” 方案：$\left(0\right),\left(1\right),\left(2\right),\left(3\right),\left(4\right)$

长度为 $2$ 的 “$1$ 型数列” 方案：$\left(1,1\right),\left(1,3\right),\left(2,2\right),\left(2,3\right),\left(3,1\right),\left(3,2\right),\left(3,3\right),\left(4,4\right)$

长度为 $3$ 的 “$1$ 型数列” 方案：

$\left(1,1,1\right),\left(1,1,3\right),\left(1,3,1\right),\left(1,3,2\right),\left(1,3,3\right),\left(2,2,2\right),\left(2,2,3\right),\left(2,3,1\right),\left(2,3,2\right),\\\left(2,3,3\right),\left(3,1,1\right),\left(3,1,3\right),\left(3,2,2\right),\left(3,2,3\right),\left(3,3,1\right),\left(3,3,2\right),\left(3,3,3\right),\left(4,4,4\right)$

长度为 $1$ 的 “$2$ 型数列” 方案：$\left(1\right),\left(2\right),\left(3\right),\left(4\right)$

长度为 $2$ 的 “$2$ 型数列” 方案：$\left(1,1\right),\left(1,3\right),\left(2,2\right),\left(2,3\right),\left(3,3\right),\left(4,4\right)$

长度为 $3$ 的 “$2$ 型数列” 方案：

$\left(1,1,1\right),\left(1,1,3\right),\left(1,3,3\right),\left(2,2,2\right),\left(2,2,3\right),\left(2,3,3\right),\left(3,3,3\right),\left(4,4,4\right)$

样例 $2$/$3$/$4$

见下发文件

数据范围

子任务 $1$ ($4\%$)：$n,m \le 7$

子任务 $2$ ($16\%$)：$n,m\le 100$

子任务 $3$ ($20\%$)：$n\le 1000, m< 2^{16}$

子任务 $4$ ($10\%$)：$n \le 50$

子任务 $5$ ($20\%$)：$n\le 1000$

子任务 $6$ ($30\%$) ：无特殊限制

对于 $100\%$ 的数据，$1\le n \le 10^5,1\le m <2^{30}$