题目描述

有一个长度为 $m$ 的一维空间，还有 $n$ 个物品，第 $i$ 个物品的长度为 $a_i$。现在按照编号从小到大的顺序依次将物品放入空间中，对于第 $i$ 个物品：

• 如果当前空间中存在一段连续的长度至少为 $a_i$ 的空余，则你必须将第 $i$ 个物品放入一段连续的长度为 $a_i$ 的空余空间中。
• 否则，第 $i$ 个物品无法被放入，跳过它。

你需要输出：按照编号从小到大的顺序考虑完所有物品后，所有可能的空间占用长度，它的定义是所有被放入空间的物品的长度之和。

输入格式

输入的第一行两个整数 $m,n$，分别表示空间长度和物品个数。

第二行 $n$ 个整数 $a_1,\cdots,a_n$，依次表示每个物品的长度。

输出格式

输出两行，第一行一个整数 $S$，表示可能的空间占用长度的数量。

第二行 $S$ 个整数 $b_1,\ldots,b_S$，从小到大输出所有可能的空间占用长度。

注意，你需要保证 $b_1,\ldots,b_S$ 不重不漏。

8 4
3 4 1 2

4
4 6 7 8

见题目目录下的 2.in 与 2.ans。

见题目目录下的 2.in 与 2.ans。

提示

【样例 1 解释】

下图分别展示了空间占用长度为 $4,6,7,8$ 的一种可能方式：

数据范围

对于所有测试数据，$1\leq m,a_i\leq 10^{16}$，$\ 1\leq n\leq 14$。