题目描述

正整数列 $A=(a_1,a_2,\ldots,a_N)$ が与えられます。
あなたは次の操作を $0$ 回以上何度でも繰り返せます。

• $A$ から（空でない）連続する部分列を選び、削除する。

$x=1,2,\ldots,M$ に対し、次の問題を解いてください。

• $A$ の要素の総和をちょうど $x$ にするために必要な操作回数の最小値を求めてください。ただし、どのように操作を行っても $A$ の要素の総和をちょうど $x$ にできない場合は代わりに -1 と出力してください。

なお、$A$ が空である時、$A$ の要素の総和は $0$ であるとします。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$M$ 行出力せよ。$i$ 行目には $x=i$ に対する答えを出力せよ。

题目大意

给出一个长度为 $n$ 的数组，问是否能通过删掉一些子段使剩下的数之和为 $q$。

若可以，求出最小操作次数，否则输出 $-1$。

对于所有的 $q\in[1,m]$ 回答这个问题，第 $i$ 行输出 $q=i$ 时的答案，每个问题互不影响。

样例解释：

在样例 $1$ 中，

$q=1$ 时删去 $a_2,a_3,a_4$，答案为 $1$。

$q=2$ 时先删去 $a_1$，再删去 $a_3,a_4$，答案为 $2$。

$q=3$ 时删去 $a_3,a_4$，答案为 $1$。

$q=4$ 时删去 $a_1,a_2,a_3$，答案为 $1$。

$q=5$ 时删去 $a_2,a_3$，答案为 $1$。

4 5
1 2 3 4

1
2
1
1
1

1 5
3

-1
-1
0
-1
-1

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

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$
• 入力はすべて整数

Sample Explanation 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$ になります。