7357: ABC275 —— F - Erase Subarrays
[Creator : ]
Description
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).
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.
- 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.
Input
The input is given from Standard Input in the following format:
$N\ M$
$a_1\ \ldots\ a_N$
$N\ M$
$a_1\ \ldots\ a_N$
Output
Print M lines. The ii-th line should contain the answer for x=i.
Constraints
$1≤N,M≤3000$
$1 \leq a_i \leq 3000$
All values in the input are integers.
$1 \leq a_i \leq 3000$
All values in the input are integers.
Sample 1 Input
4 5
1 2 3 4
Sample 1 Output
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 2 Input
1 5
3
Sample 2 Output
-1
-1
0
-1
-1
Sample 3 Input
12 20
2 5 6 5 2 1 7 9 7 2 5 5
Sample 3 Output
2
1
2
2
1
2
1
2
2
1
2
1
1
1
2
2
1
1
1
1