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