题目描述

给定一个正整数序列 $A=(a_1,a_2,\ldots,a_N)$。
你可以进行以下操作任意次（包括零次）：

• 从 $A$ 中选择一个非空的连续子序列，并将其删除。

对于每个 $x=1,2,\ldots,M$，请解决以下问题：

• 找出使 $A$ 的元素总和恰好等于 $x$ 所需的最小操作次数。如果无论如何操作都无法使 $A$ 的元素总和恰好等于 $x$，则输出 -1。

注意，当 $A$ 为空时，其元素总和被视为 $0$。

输入格式

输入从标准输入按以下格式给出：

N M
$a_1 \ldots a_N$

输出格式

输出 $M$ 行。第 $i$ 行应输出 $x = i$ 时的答案。

输入输出样例 #1

输入 #1

4 5
1 2 3 4

输出 #1

1
2
1
1
1

输入输出样例 #2

输入 #2

1 5
3

输出 #2

-1
-1
0
-1
-1

输入输出样例 #3

输入 #3

12 20
2 5 6 5 2 1 7 9 7 2 5 5

输出 #3

2
1
2
2
1
2
1
2
2
1
2
1
1
1
2
2
1
1
1
1

数据范围

• $1 \leq N, M \leq 3000$
• $1 \leq a_i \leq 3000$
• 输入均为整数

样例解释 #1

以下是操作次数最少的示例：

• x = 1 ：对 $a_2, a_3, a_4$ 执行操作，使总和为 1 。
• x = 2 ：先对 $a_3, a_4$ 执行操作，再对 $a_1$ 执行操作，使总和为 2 。
• x = 3 ：对 $a_3, a_4$ 执行操作，使总和为 3 。
• x = 4 ：对 $a_1, a_2, a_3$ 执行操作，使总和为 4 。
• x = 5 ：对 $a_2, a_3$ 执行操作，使总和为 5 。