102755: [AtCoder]ABC275 F - Erase Subarrays

Problem Statement

You are given an integer array $A=(a_1,a_2,\ldots,a_N)$.
You may perform the following operation any number of times (possibly zero).

• Choose a nonempty contiguous subarray of $A$, and delete it from the array.

For each $x=1,2,\ldots,M$, solve the following problem:

• Find the minimum possible number of operations to make the sum of elements of $A$ equal $x$. If it is impossible to make the sum of elements of $A$ equal $x$, print -1 instead.

Note that the sum of elements of an empty array is $0$.

Constraints

• $1 \leq N,M \leq 3000$
• $1 \leq a_i \leq 3000$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print $M$ lines. The $i$-th line should contain the answer for $x=i$.

Sample Input 1

4 5
1 2 3 4

Sample Output 1

1
2
1
1
1

The followings are examples of minimum number of operations that achieve the goal.

• For $x=1$, delete $a_2,a_3,a_4$, and the sum of elements of $A$ becomes $x$.
• For $x=2$, delete $a_3,a_4$, then delete $a_1$, and the sum of elements of $A$ becomes $x$.
• For $x=3$, delete $a_3,a_4$, and the sum of elements of $A$ becomes $x$.
• For $x=4$, delete $a_1,a_2,a_3$, and the sum of elements of $A$ becomes $x$.
• For $x=5$, delete $a_2,a_3$, and the sum of elements of $A$ becomes $x$.

Sample Input 2

1 5
3

Sample Output 2

-1
-1
0
-1
-1

Sample Input 3

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

Sample Output 3

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

问题描述

你被给定一个整数数组 $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