题目描述

给定一个整数数组 $A=(a_1,a_2,\ldots,a_N)$。
你可以执行以下操作任意次数（可能为零）：

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

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

• 找到使 $A$ 元素之和等于 $x$ 的最小操作次数。如果无法使 $A$ 元素之和等于 $x$，则输出 -1。

注意，空数组的元素之和为 $0$。

约束条件

• $1 \leq N,M \leq 3000$
• $1 \leq a_i \leq 3000$
• 输入中的所有值都是整数。

输入

输入从标准输入给出，格式如下：

$N$ $M$
$a_1$ $\ldots$ $a_N$

输出

输出 $M$ 行，第 $i$ 行应包含 $x=i$ 对应的答案。

示例输入 1

4 5
1 2 3 4

示例输出 1

1
2
1
1
1

以下是实现目标所需的最小操作次数的示例。

• 对于 $x=1$，删除 $a_2,a_3,a_4$，$A$ 的元素之和变为 $x$。
• 对于 $x=2$，删除 $a_3,a_4$，然后删除 $a_1$，$A$ 的元素之和变为 $x$。
• 对于 $x=3$，删除 $a_3,a_4$，$A$ 的元素之和变为 $x$。
• 对于 $x=4$，删除 $a_1,a_2,a_3$，$A$ 的元素之和变为 $x$。
• 对于 $x=5$，删除 $a_2,a_3$，$A$ 的元素之和变为 $x$。

示例输入 2

1 5
3

示例输出 2

-1
-1
0
-1
-1

示例输入 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