#P17997. Pluses and Minuses

Pluses and Minuses

Pluses and Minuses

题目描述

Misha 在笔记本里写下了若干个他认为“美丽”的非负整数。

一个仅由 + 和 - 组成的字符串被称为平衡串,当且仅当:

  • 其中 + 和 - 的数量相等;
  • 字符串末尾连续出现的 - 的数量是美丽数。

末尾连续负号的数量必须是恰好这个数;若最后一个字符为 +,则末尾负号数量为 00。这里不要求任意前缀中正号数量不少于负号数量。

请分别求长度为 2,4,…,2n2,4,\ldots,2n 的平衡串数量,答案对 998244353998244353 取模。

输入格式

第一行两个整数 n,mn,m,1≤n,m≤2000001\le n,m\le200000。

第二行包含 mm 个互不相同的整数,均属于 [0,n][0,n],表示所有美丽数。

输出格式

输出 nn 行,第 ii 行表示长度为 2i2i 的平衡串数量模 998244353998244353 的结果。

样例 1

输入

5 3
1 2 3

输出

1
3
10
34
120