Migrated from Lutece 3037 随风摇曳的二叉树

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

maco很喜欢二叉树，尤其是那些随风摇曳、左摆右摆的二叉树。 现在maco有 $n$ 种写着权值的小球，每种小球上都写着它们的权值，两个权值相同的小球被视作是一模一样的小球。每种小球的数量都是充足的，你可以认为每种小球都有无穷多个。 maco想要用一些木杆将这若干个小球串成一颗树，使得这棵树的所有节点的权值之和为 $i \enspace (1≤i≤m)$ ，这颗树必须是一颗二叉树，还必须是那种随风摇曳，左摆右摆的二叉树。

请问什么叫随风摇曳、左摆右摆的二叉树呢？善良的maco马上给出了解释： （1）随风摇曳、左摆右摆的二叉树是有根树。 （2）随风摇曳、左摆右摆的二叉树需要考虑节点之间的布局。

何为布局？善良的maco马上又做出了解释： （1）比如某个父节点 $r$，它的两个不同的儿子（权值不同则视为不同，权值相同则视为相同）是 $s$ 和 $t$ ，“$s$为左儿子，$r$为右儿子”与“$s$为右儿子，$r$为左儿子”被视为两种不同的布局！ （2）但如果某个父节点 $r$ 的两个儿子的权值相同，只交换这两个儿子的位置而不改变其他节点得到的新二叉树被视为与之前的二叉树布局相同。 （3）又比如某个父节点 $r$，它只有一个儿子$s$，“$s$为左儿子”与“$s$为右儿子”被视为两种不同的布局！ （4）再比如，先不关心节点的权值，只关心有根二叉树的形状。两颗二叉树从根节点往下看，完全同构，即便考虑左儿子右儿子的异构情况也完全同构。但如果某些结构位置等效的节点的权值不同，那么这两颗二叉树也被视作布局不同。

随风摇曳、左摆右摆的二叉树需要考虑节点之间的布局，如果两颗随风摇曳、左摆右摆的二叉树的某个细节的布局不同，那么这两颗随风摇曳、左摆右摆的二叉树就是不同的。即使两颗二叉树同构，但只要布局不同，那就是不同。 对于每个 $i∈[1,m]$ ，请回答：有多少种权值和为 $i$ 的随风摇曳、左摆右摆的二叉树？ 答案对 $998244353$ 取模

Input

第一行输入两个正整数 $n,m$ $(1≤n≤10^{5}; 1≤m≤10^{5})$ . 第二行输入 $n$ 个两两不同的正整数 $w_{1},w_{2},...,w_{n}$ . $(1≤w_{i}≤10^{5})$ 其中 $n$ 为小球的种类个数， $m$ 为询问次数，你需要对每个 $i∈[1,m]$ 做出回答。第二行输入的 $n$ 个两两不同的正整数是这 $n$ 种小球的权值。

Output

输出 $m$ 行，每行有一个整数。第 $i$ 行应当含有权值之和恰为 $i$ 的随风摇曳、左摆右摆的二叉树的总数。请输出答案关于 $998244353$ 取模的结果。

Samples

2 3
1 2

1
3
9

3 10
9 4 3

0
0
1
1
0
2
4
2
6
15

5 10
13 10 6 4 15

0
0
0
1
0
1
0
2
0
5

Resources

2023 UESTC ICPC Training for Math